Insertion in between the nodes in doubly linked list in C++

How to insert element in between the nodes in doubly linked list in C++?

Doubly Linked List is a improved version of singly linked list which has two pointer variables and a single data variable, the two pointer variables help us in storing the address of the next node as well as the previous node, which thus helps us in traversing in both the directions in a doubly linked list. Here, in this article we will be learning how to code a C++ Program for inserting an element in the end of the Doubly Linked List.

Insertion at nth specific position in doubly linked list in C++

Definition of doubly linked list in C++

struct Node 
{
  int Data;
  Struct Node* next;
  Struct Node* prev;
};

Steps to insert element in between the nodes in doubly linked list in C++

1.) Allocate node.

2.) Put the data.

3.) Make next of new node as next of previous node

4.) Make the next of previous node as new node

5.) Make previous node as previous of new node

6.) Change previous of new node as next node

Insertion in between the nodes in doubly linked list in C++

Algorithm for insertion in between the nodes in doubly linked list in C++

  •  IF PTR = NULL
  • SET NEW_NODE = PTR
  •  SET PTR = PTR -> NEXT
  • SET NEW_NODE -> DATA = VAL
  •  SET TEMP = START
  •  SET I = 0
  • REPEAT 8 to 10 until I
  •  SET TEMP = TEMP -> NEXT
  •  IF TEMP = NULL
  •  WRITE “LESS THAN DESIRED NO. OF ELEMENTS”
  • SET NEW_NODE -> NEXT = TEMP -> NEXT
  • SET NEW_NODE -> PREV = TEMP
  • SET TEMP -> NEXT = NEW_NODE
  • SET TEMP -> NEXT -> PREV = NEW_NODE
  • EXIT

Program for insertion in between the nodes in doubly linked list in C++

Run
#include<iostream>
#include<stdlib.h>
using namespace std;

struct node
{
  int num;
  struct node *preptr;
  struct node *nextptr;
} *stnode, *ennode;

void DlListcreation (int n);
void DlLinsertNodeAtMiddle (int num, int pos);
void displayDlList ();

int main ()
{
  int n, num1, a, insPlc;
  stnode = NULL;
  ennode = NULL;

  cout << "Input the number of nodes: ";
  cin >> n;
  DlListcreation (n);
  displayDlList ();

  cout << "Input the position (2 to " << n - 1 << ") to insert a new node: ";
  cin >> insPlc;

  if (insPlc <= 1 || insPlc >= n)
    {
      cout << "Invalid position\n";
    }
  else
    {
      cout << "Input data for the position " << insPlc << ": ";
      cin >> num1;
      DlLinsertNodeAtMiddle (num1, insPlc);
      displayDlList ();
    }
  return 0;
}

void DlListcreation (int n)
{
  int i, num;
  struct node *fnNode;

  if (n >= 1)
    {
      stnode = (struct node *) malloc (sizeof (struct node));

      if (stnode != NULL)
	{
	  cout << "Input data for node 1: ";
	  cin >> num;

	  stnode->num = num;
	  stnode->preptr = NULL;
	  stnode->nextptr = NULL;
	  ennode = stnode;

	  for (i = 2; i <= n; i++)
	    {
	      fnNode = (struct node *) malloc (sizeof (struct node));

	      if (fnNode != NULL)
		{
		  cout << "Input data for node " << i << ": ";
		  cin >> num;
		  fnNode->num = num;
		  fnNode->preptr = ennode;
		  fnNode->nextptr = NULL;
		  ennode->nextptr = fnNode;
		  ennode = fnNode;
		}
	      else
		{
		  cout << "Memory cannot be allocated.";
		  break;
		}
	    }
	}
      else
	{
	  cout << "Memory cannot be allocated.";
	}
    }
}

void DlLinsertNodeAtMiddle (int num, int pos)
{
  int i;
  struct node *newnode, *tmp;
  if (ennode == NULL)
    {
      cout << "No data found in the list!\n";
    }
  else
    {
      tmp = stnode;
      i = 1;
      while (i < pos)
	{
	  tmp = tmp->nextptr;
	  i++;
	}
      if (tmp != NULL)
	{
	  newnode = (struct node *) malloc (sizeof (struct node));
	  newnode->num = num;
	  newnode->nextptr = tmp->nextptr;
	  newnode->preptr = tmp;
	  if (tmp->nextptr != NULL)
	    {
	      tmp->nextptr->preptr = newnode;
	    }
	  tmp->nextptr = newnode;
	}
      else
	{
	  cout << "The position you entered is invalid.\n";
	}
    }
}

void displayDlList ()
{
  struct node *tmp;
  tmp = stnode;
  int n = 1;
  while (tmp != NULL)
    {
      cout << " node " << n << ": " << tmp->num << "\n";
      n++;
      tmp = tmp->nextptr;	// current pointer moves to the next node
    }
}
Output:
 Input the number of nodes : 5
 Input data for node 1: 11
 Input data for node 2: 22
 Input data for node 3: 33
 Input data for node 4: 44
 Input data for node 5: 55

 Data entered in the list are :
 node 1: 11
 node 2: 22
 node 3: 33
 node 4: 44
 node 5: 55
 Input the position ( 2 to 4) to insert a new node : 3
 Input data for the position 3 : 66

 After insertion the new list are :
 node 1: 11
 node 2: 22
 node 3: 66
 node 4: 33
 node 5: 44
 node 6: 55

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