A doubly linked list is a data structure that consists of a collection of nodes, where each node contains two pointers: one pointing to the previous node and one pointing to the next node in the list.
So the three components of a doubly linked list are:
*prev- address of the previous nodedata- data item*next- address of next node
Step by Step Implementation of Doubly Linked List:
1.Create a node:
Node* head = nullptr; // Pointer to the head of the doubly linked list, initially set to nullptr.
class Node {
public:
int data; // Data stored in the node.
Node* prev; // Pointer to the previous node in the doubly linked list.
Node* next; // Pointer to the next node in the doubly linked list.
};
The Node class represents a single node in the doubly linked list, containing the data value as well as pointers to the previous (prev) and next (next) nodes.
2. Insert Data in Node:
Node* head = nullptr; // Pointer to the head of the doubly linked list, initially set to nullptr
void create(int n) {
Node* newNode = new Node(); // Create a new Node object dynamically
newNode->data = n; // Set the data of the new node to the input value 'n'
newNode->prev = nullptr; // Set the 'prev' pointer of the new node to nullptr
newNode->next = nullptr; // Set the 'next' pointer of the new node to nullptr
if (head == nullptr) { // If the doubly linked list is empty
head = newNode; // Assign the new node as the head
} else {
Node* temp = head; // Create a temporary pointer and set it to the head
while (temp->next != nullptr) { // Traverse the list until the last node is reached
temp = temp->next; // Move to the next node
}
temp->next = newNode; // Assign the new node as the 'next' node of the last node
newNode->prev = temp; // Set the 'prev' pointer of the new node to the previous last node
}
}
The given code initializes a pointer named head to nullptr to track the first node of a doubly linked list. The create function creates a new node with a given data value and properly initializes its prev and next pointers. If the list is empty, the new node becomes the head. Otherwise, the function traverses the list to find the last node and adds the new node at the end, updating the necessary pointers to maintain the bidirectional linkage.
3.Display List
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}The display() function iterates through the doubly linked list starting from the head node and prints the data of each node. It uses a temporary pointer temp to traverse the list by moving to the next node until it reaches the end (temp becomes nullptr). During the traversal, it prints the data of each node and adds a space after it. Finally, it prints a new line to separate the output from other text.
Full Implementation
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
};
Node* head = nullptr;
void create(int n) {
Node* newNode = new Node();
newNode->data = n;
newNode->prev = nullptr;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
int n;
cout << "Enter the number of nodes: ";
cin >> n;
cout << "Enter the data for each node: " << endl;
for (int i = 0; i < n; i++) {
int data;
cin >> data;
create(data);
}
cout << "The linked list is: ";
display();
return 0;
}
Output:
Enter the number of nodes: 4
Enter the data for each node:
2
4
5
6
The linked list is: 2 4 5 6
Insertion on a Doubly Linked List:
In a Doubly Linked list, there are three different positions where we can insert elements-
- Insertion at the beginning
- Insertion in-between nodes
- Insertion at the End
Insertion at the beginning:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
};
Node* head = nullptr;
void insertBeginning(int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->prev = nullptr;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
int numElements;
cout << "Enter the number of elements in the list: ";
cin >> numElements;
cout << "Enter the elements of the list: ";
for (int i = 0; i < numElements; i++) {
int data;
cin >> data;
insertBeginning(data);
}
cout << "The original list is: ";
display();
int newData;
cout << "Enter the data to insert at the beginning: ";
cin >> newData;
insertBeginning(newData);
cout << "The updated list is: ";
display();
return 0;
}Output:
Enter the number of elements in the list: 2 3 4 3
Enter the elements of the list: 1 2 3
The original list is: 3 2 1
Enter the data to insert at the beginning: 0
The updated list is: 0 3 2 1
2.Insert at any position:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
};
Node* head = nullptr;
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
void insertAtPosition(int value, int position) {
if (position == 1) {
cout << "Invalid position" << endl;
return;
}
Node* currentNode = head;
int i = 1;
while (i < position - 1 && currentNode != nullptr) {
currentNode = currentNode->next;
i++;
}
if (currentNode == nullptr) {
cout << "Invalid position" << endl;
return;
}
Node* newNode = new Node();
newNode->data = value;
newNode->prev = currentNode;
newNode->next = currentNode->next;
if (currentNode->next != nullptr) {
currentNode->next->prev = newNode;
}
currentNode->next = newNode;
}
int main() {
int numElements;
cout << "Enter the number of elements in the list: ";
cin >> numElements;
cout << "Enter the elements of the list: ";
for (int i = 0; i < numElements; i++) {
int data;
cin >> data;
Node* newNode = new Node();
newNode->data = data;
newNode->prev = nullptr;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
cout << "The original list is: ";
display();
int position, value;
cout << "Enter the position to insert the new value: ";
cin >> position;
cout << "Enter the value to insert: ";
cin >> value;
insertAtPosition(value, position);
cout << "The updated list after inserting at position " << position << " is: ";
display();
return 0;
}
Output:
Enter the number of elements in the list: 4
Enter the elements of the list: 5 6 7 8
The original list is: 5 6 7 8
Enter the position to insert the new value: 4
Enter the value to insert: 9
The updated list after inserting at position 5 is: 5 6 7 9 8 3.Insertion at the End:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
};
Node* head = nullptr;
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
void insertAtEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->prev = nullptr;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
int main() {
int numElements;
cout << "Enter the number of elements in the list: ";
cin >> numElements;
cout << "Enter the elements of the list: ";
for (int i = 0; i < numElements; i++) {
int data;
cin >> data;
insertAtEnd(data);
}
cout << "The original list is: ";
display();
int value;
cout << "Enter the value to insert at the end: ";
cin >> value;
insertAtEnd(value);
cout << "The updated list after inserting at the end is: ";
display();
return 0;
}
Output:
Enter the number of elements in the list: 3
Enter the elements of the list: 5 6 7
The original list is: 5 6 7
Enter the value to insert at the end: 9
The updated list after inserting at the end is: 5 6 7 9
Deletion at any position:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
};
Node* head = nullptr;
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
void insertAtEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->prev = nullptr;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
void deleteAtPosition(int position) {
if (position <= 0 || head == nullptr) {
cout << "Invalid position or empty list" << endl;
return;
}
if (position == 1) {
Node* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
}
delete temp;
return;
}
Node* currentNode = head;
int i = 1;
while (i < position && currentNode != nullptr) {
currentNode = currentNode->next;
i++;
}
if (currentNode == nullptr) {
cout << "Invalid position" << endl;
return;
}
currentNode->prev->next = currentNode->next;
if (currentNode->next != nullptr) {
currentNode->next->prev = currentNode->prev;
}
delete currentNode;
}
int main() {
int numElements;
cout << "Enter the number of elements in the list: ";
cin >> numElements;
cout << "Enter the elements of the list: ";
for (int i = 0; i < numElements; i++) {
int data;
cin >> data;
insertAtEnd(data);
}
cout << "The original list is: ";
display();
int position;
cout << "Enter the position to delete a node: ";
cin >> position;
deleteAtPosition(position);
cout << "The updated list after deleting at position " << position << " is: ";
display();
return 0;
}
Output:
Enter the number of elements in the list: 3
Enter the elements of the list: 1 2 4
The original list is: 1 2 4
Enter the position to delete a node: 2
The updated list after deleting at position 2 is: 1 4 Advantages and Disadvantages of Doubly Linked List:
| Advantages | Disadvantages |
|---|---|
| Allows traversal in both directions (forward and backward) | Requires additional memory for the previous pointer |
| Supports efficient insertion and deletion at both ends (head and tail) | Requires additional operations to maintain the links |
| Enables easy implementation of reverse traversal | Requires additional memory to store the previous pointer |
| Provides flexibility in operations like reversing the list | Requires more time for insertion and deletion compared to a singly linked list |
| Allows efficient deletion of a node given its pointer | Takes up more memory compared to a singly linked list |
| Supports efficient removal of a node given its value | Complexity increases when maintaining consistency between forward and backward links |