Doubly Linked List Node Insertion in the middle in C

February 16, 2023

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
Insertion in Middle Doubly Linked List in C

Basic Structure of a Doubly Linked List in C

struct Node{
    int data;
    struct Node *next;
    struct Node *prev;
};
DSA desktop gif
DSA mobile gif

Singly Linked List in C

Deletion in singly Linked List

Doubly Linked List in C

Deletion in Doubly Linked List

Circular Linked List in C

Insert in the middle of a Doubly Linked in C

Run 
#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
Run 
#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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

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