A circular doubly list is a combination of doubly and circular lists; it inherits the properties of both the data structures. Consequently, this makes circular doubly quite complex. Similar to a circular linked list, performing traversing in the circular doubly linked list could lead to an infinite loop. Thus, you need to be extra careful while writing the traversal operation for this data structure.
As it contains the properties of doubly linked list DS, the Circular Doubly linked list has two pointers, namely pre and next, that point to the previous and next node respectively. Unlike a simple doubly linked list, the last node next pointer of the Circular linked list points to the head of the circular doubly linked list DS.
If we compare circular doubly linked lists to other linked list data structures, it emerges as the most expensive data structure for space and basic operations. However, it provides an easy approach for pointer manipulation, and searching becomes two times more efficient.
Advantages and Disadvantages of Using Circular Doubly Linked List
Advantages
- We can traverse back and forth using the next and pre-pointers.
- As the last element is linked with the head, we can easily jump from the tail to the head of the data structure.
- It is an ideal choice for implementing complex data structures.
Disadvantages
- As the circular doubly list needs two pointers for each node, it occupies extra space.
- The pointers must point to the right data or object and no do not point to the Null value. In case the pointers point towards the Null value, it will result in the loss of the data.
Supported Operations
We can perform various operations on the Circular doubly list. Like other data structures , there are some standard and basic operations that we can perform on this data structure, which are listed as follows:
- Insertion at the beginning
- Insertion at the end
- Traversal
- Deletion at the beginning
- Deletion at the end.
Implementation of Circular Doubly Linked List in Python :
Here's a sample code that highlights the implementation of a circular doubly list in Python:
using namespace std;
struct Node {
int data;
struct Node* next;
struct Node* pre;
};
void insert(struct Node** Head, int data)
{
if (*Head == NULL) {
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = new_node->pre = new_node;
*Head = new_node;
return;
}
Node* last = (*Head)->pre;
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = *Head;
(*Head)->pre = new_node;
new_node->pre = last;
last->next = new_node;
}
void remove(struct Node** Head, int key)
{
if (*Head == NULL)
return;
struct Node *curr = *Head, *pre_1 = NULL;
while (curr->data != key) {
if (curr->next == *Head) {
printf("\nList doesn't have node with data = %d", key);
return;
}
pre_1 = curr;
curr = curr->next;
}
if (curr->next == *Head && pre_1 == NULL) {
(*Head) = NULL;
free(curr);
return;
}
if (curr == *Head) {
pre_1 = (*Head)->pre;
*Head = (*Head)->next;
pre_1->next = *Head;
(*Head)->pre = pre_1;
free(curr);
}
else if (curr->next == *Head) {
pre_1->next = *Head;
(*Head)->pre = pre_1;
free(curr);
}
else {
struct Node* temp = curr->next;
pre_1->next = temp;
temp->pre = pre_1;
free(curr);
}
}
void traversal(struct Node* Head)
{
struct Node* temp = Head;
while (temp->next != Head)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
}
int main()
{
struct Node* Head = NULL;
insert(&Head, 1);
insert(&Head, 2);
insert(&Head, 3);
insert(&Head, 4);
insert(&Head, 5);
traversal(Head);
return 0;
}
Conclusion
We hope that this post helped you develop a basic understanding of the Doubly Circular Linked List. To make sure you remember, we would like to repeat that it is a data structure that has properties of both the doubly and circular linked lists.
Also, if you want to add more information about this data structure or you have a query, feel free to share them in the comments section below.
People are also reading:
Leave a Comment on this Post