Doubly Linked List in C++

Doubly linked list in C++

What is a doubly linked list in CPP programming?

Doubly linked list in C++ is the advanced and complex type of linked list that allows users to easily navigate through the linked list in both directions, from head to tail as well as from tail to head. The beginning node of the linked list is referred to as the header and the last node is referred to as the tail. Unlike the single-linked list, each node of the double-linked list is divided into three corresponding sections, previous which points the address of previous node , data which stores the value of the node and next which points the next node in the list.

 

Components of a Doubly Linked List in C++

To create a program for a Doubly Linked List, it is important to understand the essential elements of a
Doubly Linked List. These elements include:

  • Node: A single unit in the Doubly Linked List, which consists of data, a previous pointer, and a next pointer.
  • Next Pointer: Holds the memory address of the next node in the list.
  • Previous Pointer: Holds the memory address of the previous node in the list.
  • Data: Stores the value associated with the node.
  • Head: Represents the first node in the Doubly Linked List.

Structure of doubly linked list

Using the following statements in our program we can create a doubly linked list. This set of code will construct a doubly linked list that will store integer type of data.

struct Node 
{
  int Data;
  Struct Node* next;
  Struct Node* prev;
};
Doubly Linked List in Cpp

Why Doubly Linked List?

Saves time

A doubly linked list can be traversed in both the directions hence it saves time when we need to traversed in the list.

Efficient operations on a specific position

Insertion and deletion operations of specific position are more efficient in doubly linked list.

Effective memory utilization

It utilizes memory as we can construct and delete nodes according to our need so wastage of the memory is not there.

Operation on doubly linked list in C++

We can perform following operations on a doubly linked list in C++ programming language.

Doubly Linked List Insertion at Beginning

Algorithm for insertion at beginning in a Doubly Linked List

  • Create a new node.
  • Set the desired data value for the new node.
  • Traverse the list until reaching the nth position, referring to this node as “temp.”
  • Set the next node of the newly created node to the next node of temp.
  • Set the previous node of the newly created node to temp.
  • Set the next node of temp to the newly created node.
Doubly-Linked-List-in-Cpp-beginning-1536x565

C++ Program for insertion in a doubly linked list at the beginning

Run
#include<iostream>
using namespace std;

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

void DlListcreation (int n);
void DlLinsertNodeAtBeginning (int num);
void displayDlList ();

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

  cout << "Enter the number of nodes : ";
  cin >> n;
  DlListcreation (n);
  displayDlList ();
  cout << " Input data for insertion at beginning : ";
  cin >> num1;
  DlLinsertNodeAtBeginning (num1);
  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 : ";	
	      // assigning data in the first node
	      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;	
		        // new node is linking with the previous node
		        fnNode->nextptr = NULL;
		        ennode->nextptr = fnNode;	
		        // previous node is linking with the new node
		        ennode = fnNode;	
		        // assign new node as last node
		     }
	         else
		     {
		        cout << " Memory can not be allocated.";
		        break;
		     }
	      }
	  }
      else
	  {
	     cout << " Memory can not be allocated.";
	  }
    }
}

void DlLinsertNodeAtBeginning (int num)
{
  struct node *newnode;
  if (stnode == NULL)
  {
    cout << " No data found in the list\n";
  } 
  else
  {
    newnode = (struct node *) malloc (sizeof (struct node));
    newnode->num = num;
    newnode->nextptr = stnode;	
    // next address of new node is linking with starting node
    newnode->preptr = NULL;	
    // set previous address field of new node is NULL
    stnode->preptr = newnode;	
    // previous address of starting node is linking with new node
    stnode = newnode;		
    // set the new node as starting node
  }
}

void displayDlList ()
{
  struct node *tmp;
  tmp = stnode;
  int n = 1;
  while (tmp != NULL)
  {
    cout << " node " << n << ": " << tmp->num << "\n";
    n++;
    tmp = tmp->nextptr;
  }
}

Output:

Enter the number of nodes : 4
 Input data for node 1 : 4
 Input data for node 2: 5
 Input data for node 3: 6
 Input data for node 4: 8
 node 1: 4
 node 2: 5
 node 3: 6
 node 4: 8
 Input data for insertion at beginning : 9
 node 1: 9
 node 2: 4
 node 3: 5
 node 4: 6
 node 5: 8

Doubly Linked List Insertion at End

Algorithm for insertion at end in a Doubly Linked List

  • Create a new node.
  • Set the desired data value for the new node.
  • Traverse the Linked List until reaching the last node, referring to this node as “temp”.
  • Set the next node of the newly created node to NULL.
  • Set the previous node of the newly created node to temp.
  • Set the next node of temp to the newly created node.
Doubly-Linked-List-in-Cpp-end

C++ Program for insertion in a doubly linked list at the end

Run
#include< bits/stdc++.h>
using namespace std;
struct node {
    int num;
    struct node * preptr;
    struct node * nextptr;
}*stnode, *ennode;
 
void DlListcreation(int n);
void DlLinsertNodeAtEnd(int num);
void displayDlList();

int main()
{
    int n,num1;
    stnode = NULL;
    ennode = NULL;
    cout<<" Input the number of nodes : "; 
    cin>>n;
    DlListcreation(n); 
    displayDlList();
    cout<<" Input data for the last node : "; 
    cin>>num1;
    DlLinsertNodeAtEnd(num1);
    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: "; 
            // assigning data in the first node
            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;    
                    // new node is linking with the previous node
                    fnNode->nextptr = NULL;
                    ennode->nextptr = fnNode;   
                    // previous node is linking with the new node
                    ennode = fnNode;            
                    // assign new node as last node
                }
                else
                {
                    cout<<" Memory can not be allocated.";
                    break;
                }
            }
        }
        else
        {
            cout<<" Memory can not be allocated.";
        }
    }
}

void DlLinsertNodeAtEnd(int num)
{
    struct node * newnode;
    if(ennode == NULL)
    {
        cout<<" No data found in the list!\n"; 
    } 
    else 
    { 
        newnode = (struct node *)malloc(sizeof(struct node)); 
        newnode->num = num;
        newnode->nextptr = NULL;        
        // set next address field of new node  is NULL
        newnode->preptr = ennode;       
        // previous address of new node is linking with ending node
        ennode->nextptr = newnode;      
        // next address of ending node is linking with new node
        ennode = newnode;               
        // set the new node as ending node  
    }
}

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 : 4
 Input data for node 1: 5
 Input data for node 2: 6
 Input data for node 3: 7
 Input data for node 4: 8
 node 1: 5
 node 2: 6
 node 3: 7
 node 4: 8
 Input data for the last node : 1
 node 1: 5
 node 2: 6
 node 3: 7
 node 4: 8
 node 5: 1

Doubly Linked List Insertion at Specific Position

Algorithm for insertion at specific position in a Doubly Linked List

  • Create a new node.
  • Set the desired data value for the new node.
  • Traverse the Linked List until reaching the nth position, referring to this node as “temp”.
  • Set the next node of the newly created node to the next node of temp.
  • Set the previous node of the newly created node to temp.
  • Set the next node of temp to the newly created node.
Doubly-Linked-List-in-Cpp-position-1536x565

C++ Program for insertion in a doubly linked list at a specific position

Run
#include<bits/stdc++.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

Disadvantages of doubly linked list in C++

  1. Doubly linked list has two pointer so it requires more memory per node.
  2. Insertion and deletion operations are efficient but they requires more time as two pointer need to be maintained.

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