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.

Methods Discussed

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

Basic Structure of a Doubly Linked List in C

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

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

Method 1

Method 2

Method 1

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

Method 2

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Doubly Linked List

Introduction to Doubly Linked list in Data Structure
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 n^th node in doubly linked list – C | C++ | Java
Deletion in doubly linked list – C | C++ | Java
- Deletion from beginning in doubly linked list : C | C++ | Java
- Deletion from nth in doubly linked list : C | C++ | Java
- Deletion from end in doubly linked list : C | C++ | Java
Insertion and Deletion in doubly linked list – C | C++ | Java
Insertion in the middle in a doubly linked list – C | C++ | Java

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 n^th node in doubly linked list –
C | C++ | Java
Deletion in doubly linked list –
C | C++ | Java
Deletion from beginning in doubly linked list :
C | C++ | Java
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