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; };
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.
- Insertion
- Deletion
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.
C++ Program for insertion in a doubly linked list at the beginning
#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 position in a Doubly Linked List
- Create a new node with the given value, and set its next and prev to NULL.
- Check if the list is empty (head == NULL):
→ If yes, set head = newNode and return. - Traverse to the last node of the list using a temporary pointer (temp).
- Link the new node to the end:
→ Set temp->next = newNode and newNode->prev = temp. - Insertion complete, the node is now added at the end of the list.
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.
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++
- Doubly linked list has two pointer so it requires more memory per node.
- Insertion and deletion operations are efficient but they requires more time as two pointer need to be maintained.
Deletion in Doubly Linked List
- Deleting from Beginning of the list
- Deleting from End of the list.
- Deleting a Specific Node from the list
Deleting from the Beginning of the List
Steps:
- Check if the list is empty. If it is, simply display a message that the list is already empty and stop the process.
- Create a temporary pointer to store the address of the first node.
- Move the head pointer to the second node in the list.
- If the new head is not empty, set its previous pointer to null so that it becomes the new starting point.
- Delete the original first node and release its memory.
For more information about Deleting from Beginning of the list, click here
Deleting from the End of the List
Steps:
- Check if the list is empty. If it is, display a message and exit.
- Use a temporary pointer to go through the list and reach the last node.
- If the list contains only one node, set the head pointer to null and delete that single node.
- Otherwise, update the second last node so that its next pointer becomes null, breaking the link to the last node.
- Delete the last node and free up its memory.
For more information about Deleting from Beginning of the list, click here
Deleting a Specific Node from the List
Steps:
- Start by checking if the list is empty. If it is, inform the user and end the operation.
- Traverse the list using a temporary pointer to find the node that needs to be deleted based on its value or position.
- If the node to delete is the first node, update the head pointer to point to the second node. Also, if the new head exists, set its previous pointer to null.
- If the node is somewhere in the middle or at the end, adjust the previous node’s next pointer to skip the node to be deleted. Also, if there is a node after the one being deleted, set its previous pointer to link back to the node before the deleted one.
- Finally, delete the selected node and release the memory it was using.
For more information about Deleting from Beginning of the list, click here
FAQs
A Doubly Linked List (DLL) allows traversal in both directions (forward and backward) because each node contains two pointers: prev (to the previous node) and next (to the next node). In contrast, a Singly Linked List only supports forward traversal using a single next pointer.
- Dynamic memory usage (no fixed size)
- Easier insertion and deletion at both ends
- No shifting of elements is needed like in arrays
- Bi-directional traversal
These advantages make DLLs ideal for applications like undo-redo functionality, navigation systems, and dynamic data structures.
Choose a Doubly Linked List when:
- You need to traverse the list in both directions
- Deletion of a node (especially from the middle or end) needs to be efficient
- You want better control over navigation and backward iteration
Yes, DLLs consume more memory because each node stores an extra pointer (prev). However, this trade-off is acceptable in scenarios that require flexible navigation and frequent insertions/deletions, as the performance benefits often outweigh the extra memory cost.
While C++ STL doesn’t provide a direct DoublyLinkedList class, the std::list container is implemented as a doubly linked list under the hood. You can use std::list for most operations like insertion, deletion, and traversal without manually managing pointers.
Login/Signup to comment