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.
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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
In a C++ program for insertion in a doubly linked list at the beginning, a new node is created and linked before the head node, making it the new head of the list. This operation efficiently updates both the prev and next pointers to maintain the bidirectional structure of the list.
#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
Explanation
- The program defines a doubly linked list where each node holds data and links to both previous and next nodes.
- It dynamically creates the list by allocating memory for each node and linking them together using preptr and nextptr.
- A new node is inserted at the beginning by adjusting the links so that the new node becomes the new head of the list.
- The display function traverses the list from the start node and prints all node values sequentially.
- The main function controls the flow creating the list, displaying it, inserting a new node at the start, and displaying the updated list again.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Create Doubly Linked List | O(n) | O(n) |
| Insert Node at Beginning | O(1) | O(1) |
| Display List | O(n) | O(1) |
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
In a C++ program for insertion in a doubly linked list at the end, a new node is added after the last node of the list. This operation involves updating the previous pointer of the new node and the next pointer of the current last node to maintain proper linkage.
#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
Explanation:
- The program creates a doubly linked list using dynamic memory allocation, allowing nodes to be connected in both directions (preptr and nextptr).
- The function DlListcreation() takes the number of nodes, allocates memory for each, and connects them sequentially with proper linking.
- The function DlLinsertNodeAtEnd() adds a new node at the end of the list, updating both preptr and nextptr pointers to maintain the structure.
- The function displayDlList() traverses the list from the start node and displays the data of each node sequentially.
- Proper pointer linking ensures that traversal and insertion operations maintain the bidirectional connectivity of the doubly linked list.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Creation of Doubly Linked List | O(n) | O(n) |
| Insertion at End | O(1) | O(1) |
| Traversal (Display) | O(n) | O(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
#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
Explanation:
- The program creates a doubly linked list where each node contains data and pointers to both its previous and next nodes.
- DlListcreation() dynamically allocates memory for n nodes and links them sequentially to form the doubly linked list.
- DlLinsertNodeAtMiddle() traverses the list until the desired position and inserts a new node by updating adjacent node pointers.
- displayDlList() iterates from the start node and prints each node’s data sequentially.
- Proper validation ensures insertion only happens between the first and last nodes to maintain list integrity.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Creation of List | O(n) | O(n) |
| Insertion at Middle | O(n) | O(1) |
| Display List | O(n) | O(1) |
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
To wrap it up:
By mastering the concept of a doubly linked list in C++, you gain a versatile data structure where each node links both to its predecessor and successor offering efficient, bidirectional traversal and dynamic memory usage.
With this understanding under your belt, you’re now equipped to implement robust operations like insertion and deletion at any position, helping you tackle more complex data-structure challenges and elevate your programming toolkit.
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.
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
Login/Signup to comment