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.
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 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.
C++ Program for insertion in a doubly linked list at the end
#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
#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.
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
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
Click Here - Doubly Linked List in –
- Insertion in doubly linked list –
- Insertion at beginning in doubly linked list –
- Insertion at end in doubly linked list –
- Insertion at nth node in doubly linked list –
- Deletion in doubly linked list –
- Deletion from beginning in doubly linked list :
- Deletion from nth in doubly linked list :
- Deletion from end in doubly linked list :
- Insertion and Deletion in a doubly linked list :
- Insertion in the middle in a doubly linked list :
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
- Doubly Linked List in – C | C++ | Java
- Insertion in doubly linked list – C | C++ | Java
- Deletion in doubly linked list – C | C++ | Java
- Insertion and Deletion in doubly linked list – C | C++ | Java
- Insertion in the middle in a doubly linked list – C | C++ | Java
Login/Signup to comment