C Program to Insert a Node at the middle of a Linked List

Insertion in the middle of a Linked List in C

We will look at different methods to do insertion in the middle of a Singly Linked list in C

link

We will look at two different methods –

  • Method 1: Uses additional size variable to keep track of Linked List Size
  • Method 2: No additional variable, we calculate the size in realtime
Insertion in the middle of a Linked List in C

Run

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

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

int size = 0;

void insertMiddle(struct Node** head, int data){
    
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    
    // if the LL was empty
    if(*head == NULL){
        newNode->data = data;
        newNode->next = *head;
        *head = newNode;
        size++;
        return;
    }
    
    // otherwise
    struct Node* temp = *head;
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
    size++;
    
}

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\n");
}

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

    // allocate 3 nodes in the heap 
    head =  (struct Node*)malloc(sizeof(struct Node)); 
    node2 = (struct Node*)malloc(sizeof(struct Node));
   
    head->data = 10; // data set for head node 
    head->next = node2; // next pointer assigned to address of node2 

    node2->data = 50; 
    node2->next = NULL;
    
    size = 2;

    display(head);

    insertMiddle(&head, 20);
    display(head); 

    insertMiddle(&head, 40);
    display(head); 
    
    insertMiddle(&head, 30);
    display(head); 

    return 0; 
}

Output

Linked List : 
10 50 

Linked List : 
10 20 50 

Linked List : 
10 20 40 50 

Linked List : 
10 20 30 40 50

Run

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

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

int getCurrSize(struct Node* node){
    int size=0;

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

void insertMiddle(struct Node** head, int data){
    
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    
    // if the LL was empty
    if(*head == NULL){
        newNode->data = data;
        newNode->next = *head;
        *head = newNode;
        return;
    }
    
    // otherwise
    struct Node* temp = *head;
    
    int size = getCurrSize(*head);
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
    
}

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\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;

    // allocate 3 nodes in the heap 
    head =  (struct Node*)malloc(sizeof(struct Node)); 
    node2 = (struct Node*)malloc(sizeof(struct Node));
   
    head->data = 10; // data set for head node 
    head->next = node2; // next pointer assigned to address of node2 

    node2->data = 50; 
    node2->next = NULL;

    display(head); 

    insertMiddle(&head, 20);
    display(head); 

    insertMiddle(&head, 40);
    display(head); 
    
    insertMiddle(&head, 30);
    display(head); 

    return 0; 
}

Output

Linked List : 
10 50 

Linked List : 
10 20 50 

Linked List : 
10 20 40 50 

Linked List : 
10 20 30 40 50

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • Linked List in –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++Java
  • Insertion at nth position in singly Linked List  –
    C | C++Java
  • Insertion at end in singly Linked List  –
    C | C++Java
  • Deletion in singly Linked List  –
    C | C++Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • Linked List Insertion and Deletion –
    C | C++Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++Java
  • Reverse a linked list by changing links between nodes –
    C | C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Insertion in the middle Singly Linked List –
    C | C++Java
  • Insertion in a Sorted Linked List –
    C | C++Java
  • Delete alternate nodes of a Linked List –
    C | C++Java
  • Find middle of the linked list –
    C | C++Java
  • Reverse a linked list in groups of given size –
    C | C++Java
  • Find kth node from end of the linked list –
    C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list –
    C | C++Java
  • Check whether linked list is palindrome or not –
    C | C++Java
  • Fold a Linked List –
    C | C++Java
  • Insert at given Position –
    C | C++Java
  • Deletion at given Position –
    C | C++Java

Singly Linked List

  • Introduction to Linked List in Data Structure
  • Linked List in – C | C++ | Java
  • Singly Linked List in – C | C++ | Java
  • Insertion in singly Linked List – C | C++ | Java
    • Insertion at beginning in singly Linked List  – C | C++Java
    • Insertion at nth position in singly Linked List  – C | C++Java
    • Insertion at end in singly Linked List  – C | C++Java
  • Deletion in singly Linked List  – C | C++Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end in singly linked list : C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
  • Linked List Insertion and Deletion – C | C++Java
  • Reverse a linked list by changing links between nodes – C | C++Java
  • Linked List insertion in the middle – C | C++Java
  • Print reverse of a linked list without actually reversing – C |C++ | Java
  • Search an element in a linked list – C | C++Java
  • Insertion in a Sorted Linked List – C | C++Java
  • Delete alternate nodes of a Linked List – C | C++Java
  • Find middle of the linked list – C | C++Java
  • Reverse a linked list in groups of given size – C | C++Java
  • Find kth node from end of the linked list – C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list – C | C++Java
  • Check whether linked list is palindrome or not – C | C++Java
  • Fold a Linked List – C | C++Java
  • Insert at a given position – C | C++Java
  • Delete at a given position – C | C++Java