Doubly Linked List Insertion in a the middle in C++

C++ Program to insert in the middle of a Doubly Linked List

We will be writing a C++ Program to insert in the middle of a Doubly Linked List in C++ check below –
nodes

We will look at the following approaches –

  • Approach 1: Global Size Variable for the size of doubly linked list
  • Approach 2: External function get the size of a doubly-linked list
C++ Program for Insertion in the middle of Doubly Linked List

Global Size Variable

  • Method 1: Using External methods
  • Method 2: Using member functions
Run
#include<iostream>
using namespace std;

class Node
{
public:
  int data;
  Node *next;
  Node *prev;
};

int listSize = 0;

void insert(Node **head, int data)
{
  Node *newNode = new Node();
  newNode->data = data;
  newNode->next = *head;
  newNode->prev = NULL;

  if (*head != NULL)
    (*head)->prev = newNode;

  *head = newNode;
  listSize++;
}

void insertMiddle(Node **head, int data)
{
  Node *newNode = new Node();
  newNode->data = data;

  if (*head == NULL)
  {
    insert(head, data);
    return;
  }

  int mid = (listSize % 2 == 0) ? (listSize / 2) : (listSize + 1) / 2;

  if (mid == listSize)
  {
    newNode->next = NULL;
    newNode->prev = *head;
    (*head)->next = newNode;
    listSize++;
    return;
  }

  Node *temp = *head;
  while (--mid)
  {
    temp = temp->next;
  }

  (temp->next)->prev = newNode;
  newNode->prev = temp;
  newNode->next = temp->next;
  temp->next = newNode;

  listSize++;
}

void display(Node *node)
{
  cout << "\n\n";
  Node *end = NULL;
  cout << "\nList in forward direction: ";
  while (node != NULL)
  {
    cout << node->data << " ";
    end = node;
    node = node->next;
  }

  cout << "\nList in backward direction: ";
  while (end != NULL)
  {
    cout << end->data << " ";
    end = end->prev;
  }
}

int main()
{
  Node *head = NULL;
  insert(&head, 120);
  insert(&head, 0);

  display(head);

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

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

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

  return 0;
}

Output

List in forward direction: 0 120 
List in backward direction: 120 0 


List in forward direction: 0 30 120 
List in backward direction: 120 30 0 


List in forward direction: 0 30 60 120 
List in backward direction: 120 60 30 0 


List in forward direction: 0 30 90 60 120 
List in backward direction: 120 60 90 30 0

External function to calculate Size

  • Method 1: Using External methods
  • Method 2: Using member functions
Run
#include<iostream>
using namespace std;

class Node
{
public:
  int data;
  Node *next;
  Node *prev;
};

int getLength (Node * node);

void insert (Node ** head, int data)
{

  Node *newNode = new 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 (Node ** head, int data)
{

  Node *newNode = new 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;
    }

  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 (Node * node)
{
  int len = 0;

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

//function to print the doubly linked list
void display (Node * node)
{
  cout << "\n\n";
  Node *end = NULL;
  cout << "\nList in forward direction: ";
  while (node != NULL)
    {
      cout << node->data << " "; end = node; node = node->next;
    }

  cout << "\nList in backward direction: ";

  while (end != NULL)
    {
      cout << end->data << " "; end = end->prev;
    }
}

int main ()
{
  Node *head = NULL;

  insert (&head, 120);
  insert (&head, 0);

  display (head);

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

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

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

  return 0;
}

Output

List in forward direction: 0 120 
List in backward direction: 120 0 

List in forward direction: 0 30 120 
List in backward direction: 120 30 0 

List in forward direction: 0 30 60 120 
List in backward direction: 120 60 30 0 

List in forward direction: 0 30 90 60 120 
List in backward direction: 120 60 90 30 0

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

Checkout list of all the video courses in PrepInsta Prime Subscription

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

Doubly Linked List