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

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