Insertion in Linked List | C Program

Insertion in Singly linked list

Singly linked list has two field. first one is data and second field is link that refers to the second node. In a singly linked list, each node stores a reference to an object that is an element of the sequence, as well as a reference to the next node of the list.

Insertion Time Complexity (AVG)Θ(1)
Insertion Time Complexity (Worst)O(1)
Space ComplexityO(1)

There are three possible positions where we can enter a new node in a linked list –

  • Insertion at beginning
  • Insertion after nth position
  • Insertion at end

Generally by definition, if a new node is added it is added at the beginning of the linked list and not the end. So, we do not need to traverse the list every time for insertion

Singly Linked List Definition

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

Insertion at beginning

Imagine our linked list is not necessarily sorted and there is no reason to insert a new node in any special place in the list. Then we have an easiest place to insert the node is at the beginning of the list.  An algorithm that does so follows.

Algorithm of insertion at the beginning

  • Create a new node
  • Assign its data value
  • Assign newly created node’s next ptr to current head reference. So, it points to the previous start node of the linked list address
  • Change the head reference to the new node’s address.
void insertStart(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; 
}
Linked List insertion in C

Program

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

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

void insertStart(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;
}

void insertLast(struct Node** head, int data){

    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

    newNode->data = data;
    newNode->next = NULL;

    //need this if there is no node present in linked list at all
    if(*head==NULL){
        *head = newNode;
        return;
    }

    struct Node* temp = *head;

    while(temp->next!=NULL)
        temp = temp->next;

    temp->next = newNode;
}

void display(struct Node* node){

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

int main()
{
    
    //creating 4 pointers of type struct Node
    //So these can point to address of struct type variable
    struct Node* head = NULL; 
    struct Node* node2 = NULL; 
    struct Node* node3 = NULL; 
    struct Node* node4 = NULL; 

    // allocate 3 nodes in the heap 
    head =  (struct Node*)malloc(sizeof(struct Node)); 
    node2 = (struct Node*)malloc(sizeof(struct Node)); 
    node3 = (struct Node*)malloc(sizeof(struct Node)); 
    node4 = (struct Node*)malloc(sizeof(struct Node)); 

   
    head->data = 15; // data set for head node 
    head->next = node2; // next pointer assigned to address of node2 

    node2->data = 10; 
    node2->next = node3; 

    node3->data = 12;
    node3->next = node4; 

    node4->data = 3;
    node4->next = NULL;
    
    printf("Linklist : ");
    display(head);

    // Need '&' i.e. address as we need to change head
    insertStart(&head,25);
    
    insertLast(&head,11);
    
    printf("\nAfter Inserting Element\n");
    printf("\nLinklist : ");
    // no need for '&' as head need not be changed
    // only doing traversal
    display(head); 
    return 0; 
}

Output

20 16 12

Insertion at ending

To insert element in linked list last we would use the following steps to insert a new Node at the last of the doubly linked list.

  • Create a new node
  • Assign its data value
  • Assign its next node to NULL as this will be the last(tail) node
  • Check if the list is empty
    • Change the head node to the new node
  • If not then traverse till the last node
  • Assign the last node’s next pointer to this new node
  • Now, the new node has become the last node.
insertion at ending
#include<stdio.h>
#include<stdlib.h>

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

void insertStart(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;
}

void insertLast(struct Node** head, int data){

    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

    newNode->data = data;
    newNode->next = NULL;

    //need this if there is no node present in linked list at all
    if(*head==NULL){
        *head = newNode;
        return;
    }

    struct Node* temp = *head;

    while(temp->next!=NULL)
        temp = temp->next;

    temp->next = newNode;
}

void display(struct Node* node){

    //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,12);
    insertStart(&head,16);
    insertStart(&head,20);

    insertLast(&head,10);
    insertLast(&head,14);
    insertLast(&head,18);
    insertLast(&head,11);

    // no need for '&' as head need not be changed
// only doing traversal display(head); return 0; }

Output

20 16 12 10 14 18 11 

Insertion at After nth position node

First we will create a new node named by newnode and put the position where u want to insert the node.

Now give the address of the new node in previous node means link the new node with previous node.

After this, give the address of current node in new node.Means link your new node also with current node.

singly at mid

Final Code for all three and insert After nth Node

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

struct Node{
    int data;
    struct Node *next;
};
int calcSize(struct Node* node){
    int size=0;

    while(node!=NULL){
        node = node->next;
        size++;
    }
    return size;
}

void insertPosition(int pos, int data, struct Node** head)
{
    int size = calcSize(*head);

    //If pos is 0 then should use insertStart method
    //If pos is less than 0 then can't enter at all
    //If pos is greater than size then bufferbound issue
    if(pos < 1 || size < pos) 
{
printf("Can't insert, %d is not a valid position\n",pos);
}
else
{
struct Node* temp = *head;
struct Node* newNode = (struct Node*)
malloc(sizeof(struct Node));
newNode->data = data; newNode->next = NULL; while(--pos) { temp=temp->next; } //(25)->next = 10 as 12->next is 10 newNode->next= temp->next; // (12)->next = 25 temp->next = newNode; //new node added in b/w 12 and 10 } } void insertStart(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; } void insertLast(struct Node** head, int data){ struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; //need this if there is no node present in linked list at all if(*head==NULL){ *head = newNode; return; } struct Node* temp = *head; while(temp->next!=NULL) temp = temp->next; temp->next = newNode; } void display(struct Node* node){ //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,12); insertStart(&head,16); insertStart(&head,20); insertLast(&head,10); insertLast(&head,14); insertLast(&head,18); insertLast(&head,11); //Inserts after 3rd position insertPosition(3,25,&head); // no need for '&' as head need not be changed
// only doing traversal display(head); return 0; }

Output

20 16 12 25 10 14 18 11 
Linked Lists insertion in C meme