Doubly Linked List (DLL) Implementation in C++
Introduction
A Doubly Linked List (DLL) is a type of linked list where each node contains three components:
- Data – Stores the actual value.
- Next Pointer – Points to the next node in the list.
- Previous Pointer – Points to the previous node in the list.
Unlike a Singly Linked List (SLL), a DLL allows traversal in both forward and backward directions, making it more versatile for operations like deletion and insertion.
This article presents a C++ program to implement a doubly linked list, featuring insertion, deletion, and both forward and backward traversal functionalities.
Program Explanation
The program defines a Node structure with the following attributes:
rno(Roll Number) – Integer value representing student ID.name– String to store the student’s name.next– Pointer to the next node.prev– Pointer to the previous node.
A class dll (Doubly Linked List) is created, which provides the following functions:
insert()– Adds a new node at the end of the list.del()– Deletes a node based on the student’s name.forwarddisplay()– Displays the linked list from head to tail.backwarddisplay()– Displays the linked list from tail to head.
The main() function provides a menu-driven interface for the user to interact with the linked list.
//Program for Student Details
#include<iostream>
using namespace std;
// Structure for a Doubly Linked List node
struct Node {
int rno;
string name;
Node *next;
Node *prev;
} *head, *tail;
class dll {
public:
// Constructor to initialize an empty list
dll() {
head = NULL;
tail = NULL;
}
// Function to insert a new node at the end
void insert() {
Node *newnode = new Node;
cout << "Enter Roll number and Name to Insert: ";
cin >> newnode->rno;
cin >> newnode->name;
newnode->next = NULL;
newnode->prev = NULL;
if (head == NULL) { // If the list is empty
head = newnode;
tail = head;
} else {
newnode->prev = tail;
tail->next = newnode;
tail = newnode;
}
}
// Function to delete a node by name
void del() {
if (head == NULL) {
cout << "List is empty\n";
return;
}
string stuname;
cout << "Enter Name to delete: ";
cin >> stuname;
// Case 1: If the node to be deleted is the head
if (head->name == stuname) {
cout << "The deleted element is " << head->name << endl;
if (head->next != NULL) {
head = head->next;
head->prev = NULL;
} else { // If there's only one node
head = NULL;
tail = NULL;
}
return;
}
// Case 2: Deleting an intermediate or last node
Node *current = head;
while (current != NULL) {
if (current->name == stuname) {
current->prev->next = current->next;
if (current->next != NULL) {
current->next->prev = current->prev;
} else { // If deleting the last node
tail = current->prev;
}
delete current;
cout << "Deleted: " << stuname << endl;
return;
}
current = current->next;
}
cout << "No item found\n";
}
// Function to display the list in forward direction
void forwarddisplay() {
Node *current = head;
if (current == NULL) {
cout << "DLL is empty\n";
return;
}
while (current != NULL) {
cout << "|" << current->rno << ", " << current->name << "|| ---> ";
current = current->next;
}
cout << "NULL\n";
}
// Function to display the list in backward direction
void backwarddisplay() {
Node *current = tail;
if (current == NULL) {
cout << "DLL is empty\n";
return;
}
while (current != NULL) {
cout << "|" << current->rno << ", " << current->name << "|| ---> ";
current = current->prev;
}
cout << "NULL\n";
}
};
int main() {
dll s;
int ch;
while (1) {
cout << "\n1. Insert\n";
cout << "2. Delete\n";
cout << "3. Forward Display\n";
cout << "4. Backward Display\n";
cout << "5. Exit\n";
cout << "Enter Choice: ";
cin >> ch;
switch (ch) {
case 1: s.insert(); break;
case 2: s.del(); break;
case 3: s.forwarddisplay(); break;
case 4: s.backwarddisplay(); break;
case 5: exit(0);
default: cout << "Invalid Choice\n";
}
}
}
Program Features & Explanation
1. Insertion (insert())
- A new node is created dynamically.
- If the list is empty, the new node becomes both head and tail.
- Otherwise, the new node is linked at the end of the list.
2. Deletion (del())
- The function searches for a node based on the student’s name.
- If the node is found:
- If it’s the head, the
nextnode becomes the new head. - If it’s an intermediate node, it is bypassed in the linked list.
- If it’s the last node, the tail is updated.
- If it’s the head, the
- If the name is not found, a message is displayed.
3. Forward Display (forwarddisplay())
- Traverses the list from head to tail, printing each node.
4. Backward Display (backwarddisplay())
- Traverses the list from tail to head, printing each node.
5. Menu-Driven Interface (main())
- Provides options to insert, delete, display in both directions, or exit.
- Uses a while-loop to keep the menu active until the user exits.
This program provides a basic implementation of a Doubly Linked List (DLL) in C++. It allows:
✅ Efficient bidirectional traversal
✅ Easy insertion and deletion
✅ Dynamic memory allocation
This implementation is useful for Data Structures & Algorithms (DSA) and forms the foundation for advanced variations like Circular Doubly Linked Lists.
good work
ReplyDelete