Circular Doubly Linked List in C++
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. This bidirectional linkage allows for efficient traversal in both directions, making it useful for various applications.
The operations that can be performed on a doubly circular linked list are:
- Insertion at any position
- Deletion at any position
Insertion at any position in Circular Doubly Linked List:
Insertion at any position involve inserting a new data at any position of a linked list- at the beginning, at the end or at any position in between the nodes. An example code has been given below:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
};
Node* head = nullptr;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->prev = nullptr;
newNode->next = nullptr;
return newNode;
}
// Function to insert a node at a given position in the circular doubly linked list
void insertAtPosition(int data, int position) {
Node* newNode = createNode(data);
if (head == nullptr) {
head = newNode;
newNode->next = newNode;
newNode->prev = newNode;
} else {
Node* temp = head;
int count = 1;
while (count < position && temp->next != head) {
temp = temp->next;
count++;
}
newNode->next = temp->next;
newNode->prev = temp;
temp->next->prev = newNode;
temp->next = newNode;
}
}
// Function to display the circular doubly linked list
void display() {
if (head == nullptr) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
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;
insertAtPosition(data, i + 1);
}
cout << "The original list is: ";
display();
int newData, position;
cout << "Enter the data to insert: ";
cin >> newData;
cout << "Enter the position to insert (between 1 and " << numElements + 1 << "): ";
cin >> position;
if (position < 1 || position > numElements + 1) {
cout << "Invalid position." << endl;
} else {
insertAtPosition(newData, position);
cout << "The updated list is: ";
display();
}
return 0;
}
Output:
Enter the number of elements in the list: 3
Enter the elements of the list: 1 2 3
The original list is: 1 2 3
Enter the data to insert: 4
Enter the position to insert (between 1 and 4): 4
The updated list is: 1 2 3 4
Deletion at any position Circular Doubly Linked List:
We can delete nodes at any position in a Circular Doubly Linked List. Here's an example code by which we can do so:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
};
Node* head = nullptr;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->prev = nullptr;
newNode->next = nullptr;
return newNode;
}
// Function to insert a node at the end of the circular doubly linked list
void insert(int data) {
Node* newNode = createNode(data);
if (head == nullptr) {
head = newNode;
newNode->next = newNode;
newNode->prev = newNode;
} else {
Node* last = head->prev;
newNode->next = head;
newNode->prev = last;
head->prev = newNode;
last->next = newNode;
}
}
// Function to delete a node at a given position in the circular doubly linked list
void deleteAtPosition(int position) {
if (head == nullptr) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
int count = 1;
while (count < position && temp->next != head) {
temp = temp->next;
count++;
}
if (count != position) {
cout << "Invalid position." << endl;
return;
}
if (temp == head && temp->next == head) {
// Deleting the only node in the list
head = nullptr;
} else if (temp == head) {
// Deleting the head node
head = temp->next;
head->prev = temp->prev;
temp->prev->next = head;
} else {
// Deleting a node other than head
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
}
delete temp;
cout << "Node deleted from position " << position << endl;
}
// Function to display the circular doubly linked list
void display() {
if (head == nullptr) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
cout << "Circular Doubly Linked List: ";
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
int main() {
// Inserting nodes at the end
insert(1);
insert(2);
insert(3);
insert(4);
// Displaying the circular doubly linked list
display();
int position;
cout << "Enter the position to delete (between 1 and the number of elements): ";
cin >> position;
if (position < 1) {
cout << "Invalid position." << endl;
} else {
deleteAtPosition(position);
cout << "The updated list is: ";
display();
}
return 0;
}
Output:
Circular Doubly Linked List: 1 2 3 4
Enter the position to delete (between 1 and the number of elements): 1
Node deleted from position 1
The updated list is: Circular Doubly Linked List: 2 3 4
Advantages of Circular Doubly Linked List:
Efficient Traversal: Since a circular doubly linked list has links in both forward and backward directions, it allows for efficient traversal in both directions.
- Circular Structure: This eliminates the need for special cases when performing operations at the ends of the list, such as inserting or deleting elements. It simplifies the implementation of algorithms that require circular access, such as round-robin scheduling.
2. Easy Reversal: By swapping the prev and next pointers of each node, the entire list can be reversed in a single pass.
3. Tail Manipulation: Having a reference to both the head and tail of the list enables efficient manipulation of the last element. This is beneficial when frequently appending or removing elements at the end of the list, as it eliminates the need to traverse the entire list to reach the last node.
Disadvantages of Circular Doubly Linked List:
- Increased Memory Usage: Compared to singly linked lists, circular doubly linked lists require additional memory to store the prev pointers for each node. This increased memory overhead can be a disadvantage when dealing with large lists or in memory-constrained environments.
2. More Complex Implementation: The circular doubly linked list requires careful management of the prev and next pointers to maintain the circular structure. This complexity can make the implementation more challenging and prone to errors compared to simpler data structures like singly linked lists.
3. Potential for Infinite Loops: If the links in a circular doubly linked list are not correctly maintained or if there are bugs in the implementation, it is possible to encounter infinite loops during traversal or other operations. Debugging such issues can be more challenging compared to singly linked lists.
4. Non-Standard Structure: Circular doubly linked lists are not as commonly used as singly linked lists or arrays, making them less familiar to developers. This lack of familiarity can make the code less readable and understandable to others who are not familiar with the structure.