In the world of data structures, a circular linked list with doubly linked nodes offers a unique and powerful way to manage collections of elements. This structure allows you to traverse the list from any node to any other node, making it both versatile and efficient. In this article, we will explore how to implement a circular linked list with doubly linked nodes in C++, using three different approaches. Each approach will be explained with code examples and outputs to help you understand the concepts and their practical applications.
Prerequisites
Before diving into the implementation, you should have:
- A basic understanding of C++ programming.
- Knowledge of pointers and dynamic memory allocation in C++.
- Familiarity with linked lists and doubly linked lists.
Introduction
A circular linked list is a variation of a linked list in which the last node points back to the first node, creating a circular structure. When combined with doubly linked nodes (where each node points to both its previous and next nodes), this data structure becomes a powerful tool for various applications, such as implementing queues, buffers, and more. In this article, we will demonstrate how to implement a circular linked list with doubly linked nodes in C++ through three examples.
1. Basic Implementation of a Circular Doubly Linked List
1.1 Explanation
In this example, we will implement a basic circular doubly linked list where each node has pointers to both its next and previous nodes. We will include functions to insert nodes at the end of the list and to display the list.
1.2 Code Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
class CircularDoublyLinkedList {
Node* head;
public:
CircularDoublyLinkedList() {
head = nullptr;
}
void insertEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) {
head = newNode;
head->next = head;
head->prev = head;
} else {
Node* tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
}
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() {
CircularDoublyLinkedList list;
list.insertEnd(10);
list.insertEnd(20);
list.insertEnd(30);
list.insertEnd(40);
cout << "Circular Doubly Linked List: ";
list.display();
return 0;
}
1.3 Output
Circular Doubly Linked List: 10 20 30 40
2. Inserting Nodes at the Beginning
2.1 Explanation
In this example, we extend the circular doubly linked list to include a function for inserting nodes at the beginning of the list. This adds more flexibility to our list operations.
2.2 Code Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
class CircularDoublyLinkedList {
Node* head;
public:
CircularDoublyLinkedList() {
head = nullptr;
}
void insertEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) {
head = newNode;
head->next = head;
head->prev = head;
} else {
Node* tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
}
void insertBegin(int value) {
Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) {
head = newNode;
head->next = head;
head->prev = head;
} else {
Node* tail = head->prev;
newNode->next = head;
newNode->prev = tail;
tail->next = newNode;
head->prev = newNode;
head = newNode;
}
}
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() {
CircularDoublyLinkedList list;
list.insertEnd(10);
list.insertEnd(20);
list.insertEnd(30);
list.insertBegin(40);
list.insertBegin(50);
cout << "Circular Doubly Linked List: ";
list.display();
return 0;
}
2.3 Output
Circular Doubly Linked List: 50 40 10 20 30
3. Deleting Nodes from the List
3.1 Explanation
In this final example, we will add functionality to delete nodes from the circular doubly linked list. We will implement functions to delete nodes from both the beginning and the end of the list.
3.2 Code Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
class CircularDoublyLinkedList {
Node* head;
public:
CircularDoublyLinkedList() {
head = nullptr;
}
void insertEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) {
head = newNode;
head->next = head;
head->prev = head;
} else {
Node* tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
}
void insertBegin(int value) {
Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) {
head = newNode;
head->next = head;
head->prev = head;
} else {
Node* tail = head->prev;
newNode->next = head;
newNode->prev = tail;
tail->next = newNode;
head->prev = newNode;
head = newNode;
}
}
void deleteBegin() {
if (head == nullptr) {
cout << "List is empty" << endl;
return;
}
Node* tail = head->prev;
if (head->next == head) {
delete head;
head = nullptr;
} else {
Node* temp = head;
head = head->next;
head->prev = tail;
tail->next = head;
delete temp;
}
}
void deleteEnd() {
if (head == nullptr) {
cout << "List is empty" << endl;
return;
}
Node* tail = head->prev;
if (head->next == head) {
delete head;
head = nullptr;
} else {
Node* temp = tail;
tail = tail->prev;
tail->next = head;
head->prev = tail;
delete temp;
}
}
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() {
CircularDoublyLinkedList list;
list.insertEnd(10);
list.insertEnd(20);
list.insertEnd(30);
list.insertBegin(40);
list.insertBegin(50);
cout << "Circular Doubly Linked List: ";
list.display();
list.deleteBegin();
cout << "After deleting from beginning: ";
list.display();
list.deleteEnd();
cout << "After deleting from end: ";
list.display();
return 0;
}
3.3 Output
Circular Doubly Linked List: 50 40 10 20 30
After deleting from beginning: 40 10 20 30
After deleting from end: 40 10 20
Conclusion
In this article, we explored how to implement a circular linked list with doubly linked nodes in C++. We began with a basic implementation, then extended the functionality to include insertion at the beginning and deletion from both ends. Each approach was demonstrated with detailed code examples and outputs to help you understand the underlying concepts. Implementing a circular doubly linked list can be a powerful tool in your programming arsenal, offering flexibility and efficiency for various applications. Whether you’re a student, a professional, or an enthusiast, mastering this data structure will enhance your problem-solving skills and broaden your understanding of data structures