Doubly Linked List in C++ with Real-Time Examples | Complete Guide (Insertion, Deletion, Traversal)
Introduction
A Doubly Linked List (DLL) is a type of linear data structure where each node contains:
-
Data
-
Pointer to the previous node
-
Pointer to the next node
Unlike a singly linked list, it allows bidirectional traversal, making operations more flexible.
Objective
This lab session helps you understand and implement:
-
Creation of a doubly linked list
-
Insertion operations
-
Deletion operations
-
Traversal of nodes
DS LAB 02: Singly Linked List in C++ | Data Structures Lab with Objectives and Operations
Structure of a Node
struct Node {
int data;
Node* prev;
Node* next;
};
Complete C++ Implementation
1. Creation of Doubly Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
Node* head = NULL;
Node* createNode(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
2. Insertion Operations
Inset at Beginning
void insertAtBeginning(int value) {
Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
} else {
head->prev = newNode;
newNode->next = head;
head = newNode;
}
}
Insert at End
void insertAtEnd(int value) {
Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
Insert at Specific Position
void insertAtPosition(int value, int pos) {
if (pos == 1) {
insertAtBeginning(value);
return;
}
Node* newNode = createNode(value);
Node* temp = head;
for (int i = 1; i < pos - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Position not found\n";
return;
}
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != NULL)
temp->next->prev = newNode;
temp->next = newNode;
}
3. Deletion Operations
Delete from Beginning
void deleteFromBeginning() {
if (head == NULL) return;
Node* temp = head;
head = head->next;
if (head != NULL)
head->prev = NULL;
delete temp;
}
Delete from End
void deleteFromEnd() {
if (head == NULL) return;
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
if (temp->prev != NULL)
temp->prev->next = NULL;
else
head = NULL;
delete temp;
}
Delete Specific Value
void deleteValue(int value) {
if (head == NULL) return;
Node* temp = head;
while (temp != NULL && temp->data != value) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Value not found\n";
return;
}
if (temp->prev != NULL)
temp->prev->next = temp->next;
else
head = temp->next;
if (temp->next != NULL)
temp->next->prev = temp->prev;
delete temp;
}
4. Traversal of Nodes
Forward Traversal
void displayForward() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " <-> ";
temp = temp->next;
}
cout << "NULL\n";
}
Backward Traversal
void displayBackward() {
Node* temp = head;
if (temp == NULL) return;
while (temp->next != NULL) {
temp = temp->next;
}
while (temp != NULL) {
cout << temp->data << " <-> ";
temp = temp->prev;
}
cout << "NULL\n";
}
Main Function (Testing)
int main() {
insertAtBeginning(10);
insertAtBeginning(5);
insertAtEnd(20);
insertAtPosition(15, 3);
cout << "Forward: ";
displayForward();
cout << "Backward: ";
displayBackward();
deleteFromBeginning();
deleteFromEnd();
deleteValue(15);
cout << "After Deletion: ";
displayForward();
return 0;
}
Advantages of Doubly Linked List
✔ Traversal in both directions
✔ Easier deletion compared to singly linked list
✔ Efficient for navigation systems
Disadvantages
❌ Extra memory required for prev pointer
❌ More complex implementation
Conclusion
A Doubly Linked List is a powerful data structure that allows efficient insertion, deletion, and traversal in both directions. It is widely used in real-world applications such as:
-
Music players
-
Browser history
-
Navigation systems
Understanding its implementation in C++ helps build a strong foundation in Data Structures and Algorithms.
Lab Tasks (For Students)
-
Insert 5 nodes and display forward and backward
-
Delete a node from the middle
-
Implement search operation
-
Reverse the doubly linked list
