Doubly Linked List Node Insertion in the middle in C

C Program to Insert in the middle of a Doubly Linked List

We will look at different ways of insertion in the middle for Doubly Linked list in C Program.
Deletion at the end of the Singly Linked List using C

Methods Discussed

  • Method 1: Using Global Size variable
  • Method 2: Using an extra function to calculate real-time size

Insert in the middle of a Doubly Linked in C

#include<stdio.h>
#include<stdlib.h> struct Node{ int data; struct Node *next, *prev; }; int size = 0; void insert(struct Node** head, int data){ struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); newNode->data = data; newNode->next = *head; newNode->prev = NULL; //If the linked list already had atleast 1 node if(*head !=NULL) (*head)->prev = newNode; // changing the new head to this freshly entered node *head = newNode; 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){ // using insert function to insert at start insert(head,data); return; } // otherwise // find correct insertion position for middle int mid = (size % 2 == 0) ? (size/2) : (size+1)/2; // will only happen when there is one node in Doubly Linked List // we will have to insert at the last, // inserting 2nd node at the last // Example size = 1 will result in mid = 1 so entering after 1st node // where size itself is 1 so entering last node if(mid == size){ newNode->next = NULL; newNode->prev = *head; (*head)->next = newNode; size++; return; } struct Node* temp = *head; // traverse to current mid position while(--mid){ temp = temp->next; } // (mid+1)th node prev to this newNode (temp->next)->prev = newNode; // newNode's prev to this current middle node newNode->prev = temp; // newNode's next to (mid+1)th node newNode->next = temp->next; // current mid node's next becomes this newNode temp->next = newNode; // this new inserted after the middle node successfully size++; } //function to print the doubly linked list void display(struct Node* node) { printf("\n\n"); struct Node *end = NULL; printf("List in Forward direction: "); while (node != NULL) { printf(" %d ", node->data); end = node; node = node->next; } printf("\nList in backward direction: "); while (end != NULL) { printf(" %d ", end->data); end = end->prev; } } int main() { struct Node* head = NULL; insert(&head,500); insert(&head,100); display(head); insertMiddle(&head, 200); display(head); insertMiddle(&head, 400); display(head); insertMiddle(&head, 300); display(head); return 0; }

Output

List in Forward direction:  100  500 
List in backward direction:  500  100 

List in Forward direction:  100  200  500 
List in backward direction:  500  200  100 

List in Forward direction:  100  200  400  500 
List in backward direction:  500  400  200  100 

List in Forward direction:  100  200  300  400  500 
List in backward direction:  500  400  300  200  100 
#include<stdio.h>
#include<stdlib.h> struct Node{ int data; struct Node *next, *prev; }; int getLength(struct Node* node); void insert(struct Node** head, int data){ struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); newNode->data = data; newNode->next = *head; newNode->prev = NULL; //If the linked list already had atleast 1 node if(*head !=NULL) (*head)->prev = newNode; // changing the new head to this freshly entered node *head = newNode; } 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){ // using insert function to insert at start insert(head,data); return; } // otherwise int size = getLength(*head); // find correct insertion position for middle int mid = (size % 2 == 0) ? (size/2) : (size+1)/2; // will only happen when there is one node in Doubly Linked List // we will have to insert at the last, // inserting 2nd node at the last // Example size = 1 will result in mid = 1 so entering after 1st node // where size itself is 1 so entering last node if(mid == size){ newNode->next = NULL; newNode->prev = *head; (*head)->next = newNode; return; } struct Node* temp = *head; // traverse to current mid position while(--mid){ temp = temp->next; } // (mid+1)th node prev to this newNode (temp->next)->prev = newNode; // newNode's prev to this current middle node newNode->prev = temp; // newNode's next to (mid+1)th node newNode->next = temp->next; // current mid node's next becomes this newNode temp->next = newNode; // this newNode inserted after the middle node successfully } int getLength(struct Node* node){ int len = 0; while(node!=NULL){ node = node->next; len++; } return len; } //function to print the doubly linked list void display(struct Node* node) { printf("\n\n"); struct Node *end = NULL; printf("List in Forward direction: "); while (node != NULL) { printf(" %d ", node->data); end = node; node = node->next; } printf("\nList in backward direction: "); while (end != NULL) { printf(" %d ", end->data); end = end->prev; } } int main() { struct Node* head = NULL; insert(&head,500); insert(&head,100); display(head); insertMiddle(&head, 200); display(head); insertMiddle(&head, 400); display(head); insertMiddle(&head, 300); display(head); return 0; }

Output

List in Forward direction:  100  500 
List in backward direction:  500  100 

List in Forward direction:  100  200  500 
List in backward direction:  500  200  100 

List in Forward direction:  100  200  400  500 
List in backward direction:  500  400  200  100 

List in Forward direction:  100  200  300  400  500 
List in backward direction:  500  400  300  200  100 

Doubly Linked List

Doubly Linked List

  • Introduction to Doubly Linked list in Data Structure
    Click Here
  • Doubly Linked List in –
    C | C++ | Java
  • Insertion in doubly linked list –
    C | C++ | Java
  • Insertion at beginning in doubly linked list –
    C | C++ | Java
  • Insertion at end in doubly linked list –
    C | C++ | Java
  • Insertion at nth node in doubly linked list –
    C | C++ | Java
  • Deletion in doubly linked list  –
    C | C++ | Java
  • Deletion from beginning in doubly linked list :
  • Deletion from nth in doubly linked list :
    C | C++ | Java
  • Deletion from end in doubly linked list :
    C | C++ | Java
  • Insertion and Deletion in a  doubly linked list :
    C | C++ | Java
  • Insertion in the middle in a  doubly linked list :
    C | C++ | Java