A Circular Doubly Linked List is a linked list where each node contains pointers to both the next and the previous nodes, and the last node points back to the first node, forming a circular structure.
Structure of a Circular Doubly Linked List Node
struct Node {
int data; // Data stored in the node
struct Node* next; // Pointer to the next node
struct Node* prev; // Pointer to the previous node
};
Characteristics of Circular Doubly Linked List
- Bidirectional Traversal: Nodes can be traversed both forward and backward.
- Circular Nature: The next pointer of the last node points to the first node, and the prev pointer of the first node points to the last node.
- Dynamic Size: Can grow or shrink during runtime.
- Efficient Operations: Insertion and deletion are efficient as there is no need to reset pointers to NULL.
Operations on Circular Doubly Linked List
1. Traversal
a. Forward Traversal
void traverseForward(struct Node* head) {
if (head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = head;
do {
printf(“%d -> “, temp->data);
temp = temp->next;
} while (temp != head);
printf(“(back to head)\n”);
}
b. Backward Traversal
void traverseBackward(struct Node* head) {
if (head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = head->prev; // Start from the last node
do {
printf(“%d -> “, temp->data);
temp = temp->prev;
} while (temp != head->prev);
printf(“(back to tail)\n”);
}
2. Insertion
a. Insert at the Beginning
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if (*head == NULL) {
newNode->next = newNode;
newNode->prev = newNode;
*head = newNode;
return;
}
struct Node* tail = (*head)->prev;
newNode->next = *head;
newNode->prev = tail;
(*head)->prev = newNode;
tail->next = newNode;
*head = newNode; // Update head to new node
}
b. Insert at the End
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if (*head == NULL) {
newNode->next = newNode;
newNode->prev = newNode;
*head = newNode;
return;
}
struct Node* tail = (*head)->prev;
newNode->next = *head;
newNode->prev = tail;
tail->next = newNode;
(*head)->prev = newNode;
}
3. Deletion
a. Delete from the Beginning
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
// If there is only one node
if (temp->next == *head) {
free(temp);
*head = NULL;
return;
}
struct Node* tail = temp->prev;
*head = temp->next;
(*head)->prev = tail;
tail->next = *head;
free(temp);
}
b. Delete from the End
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* tail = (*head)->prev;
// If there is only one node
if (tail->next == *head) {
free(tail);
*head = NULL;
return;
}
struct Node* secondLast = tail->prev;
secondLast->next = *head;
(*head)->prev = secondLast;
free(tail);
}
4. Searching
void search(struct Node* head, int value) {
if (head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = head;
int position = 1;
do {
if (temp->data == value) {
printf(“Value %d found at position %d.\n”, value, position);
return;
}
temp = temp->next;
position++;
} while (temp != head);
printf(“Value %d not found in the list.\n”, value);
}
Example Program
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function prototypes
void insertAtEnd(struct Node** head, int value);
void deleteFromBeginning(struct Node** head);
void traverseForward(struct Node* head);
void traverseBackward(struct Node* head);
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf(“Circular Doubly Linked List (Forward Traversal):\n”);
traverseForward(head);
printf(“Circular Doubly Linked List (Backward Traversal):\n”);
traverseBackward(head);
deleteFromBeginning(&head);
printf(“Circular Doubly Linked List after deletion (Forward Traversal):\n”);
traverseForward(head);
return 0;
}
// Function implementations
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if (*head == NULL) {
newNode->next = newNode;
newNode->prev = newNode;
*head = newNode;
return;
}
struct Node* tail = (*head)->prev;
newNode->next = *head;
newNode->prev = tail;
tail->next = newNode;
(*head)->prev = newNode;
}
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
// If there is only one node
if (temp->next == *head) {
free(temp);
*head = NULL;
return;
}
struct Node* tail = temp->prev;
*head = temp->next;
(*head)->prev = tail;
tail->next = *head;
free(temp);
}
void traverseForward(struct Node* head) {
if (head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = head;
do {
printf(“%d -> “, temp->data);
temp = temp->next;
} while (temp != head);
printf(“(back to head)\n”);
}
void traverseBackward(struct Node* head) {
if (head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = head->prev;
do {
printf(“%d -> “, temp->data);
temp = temp->prev;
} while (temp != head->prev);
printf(“(back to tail)\n”);
}
Output Example
Circular Doubly Linked List (Forward Traversal):
10 -> 20 -> 30 -> (back to head)
Circular Doubly Linked List (Backward Traversal):
30 -> 20 -> 10 -> (back to tail)
Circular Doubly Linked List after deletion (Forward Traversal):
20 -> 30 -> (back to head)
Advantages of Circular Doubly Linked List
- Bidirectional Traversal: Allows efficient forward and backward traversal.
- No Null Pointers: Provides a continuous loop, avoiding NULL.
- Efficient Insertions/Deletions: Operations can be performed efficiently at both ends.
Disadvantages of Circular Doubly Linked List
- Memory Overhead: Requires extra memory for prev pointers.
- Complexity: More complex to implement compared to a singly linked list.
Applications of Circular Doubly Linked List
- Data Buffers: Circular buffers in multimedia applications.
- Real-Time Systems: Useful in round-robin scheduling.
- Undo/Redo Operations: In text editors or similar applications.