Singly Linked List in C

Singly Linked List in C

Singly Linked List in C is one of the simplest linear data structures, that we use for storing our data in an easy and efficient way.  Linked List in C comprises nodes like structures, which can further be divided into 2 parts in the case of a singly linked list. These two parts are-:

  • Node – for storing the data.
  • Pointer – for storing the address of the next node.

In a Singly linked list there is only one pointer type variable, that contains the address of the next node.

Implementation of Singly Linked List in C

We implement Linked List  using user defined data type, with the help of structure or struct. Since Singly linked list has only 1 pointer type value, which means it can store the address of only one node, which will be  the next to it. As a result, we can only move in one direction in a Singly Linked List i.e; from head to tail, which makes traversing a linked list more difficult. Implementing  linked list  rather than using array is better, since the insertion and deletion operations in  Linked List are less complicated and less time consuming in comparison with arrays.

Singly Linked Lists in C

How to Construct a Singly Linked List in C ?

For constructing a singly linked list in C we make use of the structure keyword(struct), for creating user-defined data types, which can store various different types of data in the nodes of the singly linked list.

Each linked list has two parts –

  • One for storing the desired data
  • The other is a pointer type variable, which stores the address of the next node.

The syntax for creating a node

struct Node {
  int Data;
  Struct Node* next;
};

This code will create a data type Node, which  will be able to store two values-:

  1. int value – data
  2. pointer value – address of the next node

Insertion of a node

void insert(struct Node** head, int data){
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

  newNode->data = data;
  newNode->next = *head;

 
 //changing the new head to this freshly entered node
  *head = newNode; 
}
Singly Linked List Insertion

Deletion of a node

void deleteStart(struct Node** head){
    struct Node* temp = *head;
  
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        printf("Linked List Empty, nothing to delete");
        return;
    }
    
    // move head to next node
    *head = (*head)->next;
    free(temp);
}

Traversal in a Singly Linked List

void display(struct Node* node)
{
    printf("Linked List: ");
    
    // as linked list will end when Node is Null
    while(node!=NULL){
        printf("%d ",node->data);
        node = node->next;
    }
    
    printf("\n");
}

Code for Implementing Single Linked List in C

Run
#include<stdlib.h>
#include<stdio.h>

struct Node{
    int data;
    struct Node *next;
};

void deleteStart(struct Node** head){
    struct Node* temp = *head;
  
    // If head is NULL it means Singly Linked List is empty
    if(*head == NULL){
        printf("Impossible to delete from empty Singly Linked List");
        return;
    }
    
    // move head to next node
    *head = (*head)->next;
    printf("Deleted: %d\n", temp->data);
    free(temp);
}

void insertStart(struct Node** head, int data){
    
    // dynamically create memory for this newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = newNode;
    printf("Inserted %d\n",newNode->data);
}

void display(struct Node* node){
    printf("\nLinked List: ");
    // as linked list will end when Node is Null
    while(node!=NULL){
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
}

int main()
{
    struct Node* head = NULL;

    // Need '&' i.e. address as we need to change head
    insertStart(&head,100);
    insertStart(&head,80);
    insertStart(&head,60);
    insertStart(&head,40);
    insertStart(&head,20);
    
    // No Need for '&' as not changing head in display operation
    display(head);
    
    deleteStart(&head);
    deleteStart(&head);
    display(head);
    
    return 0; 
}

Output

Inserted 100
Inserted 80
Inserted 60
Inserted 40
Inserted 20

Linked List: 20 40 60 80 100 
Deleted: 20
Deleted: 40

Linked List: 60 80 100
Linked list in C meme 2