A circular doubly linked list (CDLL) is a linked list where each node points to both its previous and next nodes, and the last node links back to the head. This bidirectional circular structure allows traversal in both directions continuously. CDLLs are useful in applications like round-robin scheduling, playlists, and buffering systems. Mastering them strengthens your understanding of pointers, dynamic memory management, and cyclic data structures.
with hands-on learning.
get the skills and confidence to land your next move.
Understanding the Problem
The main challenge in CDLLs is ensuring both next and prev pointers maintain circularity during insertions, deletions, and updates. Special attention is required when modifying the head or tail nodes. Traversal loops must account for the circular nature to avoid infinite loops, and empty or single-node lists must be handled carefully.
Program 1: Insertion at End and Display
This program inserts nodes at the end of a CDLL and displays all nodes in forward and backward directions. Both next and prev pointers are updated to maintain bidirectional circularity.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = newNode->prev = head;
return;
}
Node *tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
void displayForward() {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
void displayBackward() {
if (!head) {
printf("List is empty\n");
return;
}
Node *tail = head->prev;
Node *temp = tail;
printf("Backward: ");
do {
printf("%d ", temp->data);
temp = temp->prev;
} while (temp != tail);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayForward();
displayBackward();
return 0;
}Insertion links the new node to both head and tail. Forward and backward display functions verify bidirectional traversal.
Program 2: Insertion at Beginning and Specific Position
This program demonstrates inserting a node at the beginning or at a specific position. Pointer updates preserve circularity and bidirectional links.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = newNode->prev = head;
return;
}
Node *tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
void insertAtBeginning(int value) {
insertAtEnd(value);
head = head->prev; // move head to the new node
}
void insertAtPosition(int value, int pos) {
if (pos < 1) {
printf("Invalid position\n");
return;
}
if (pos == 1) {
insertAtBeginning(value);
return;
}
Node *temp = head;
int count = 1;
while (count < pos - 1 && temp->next != head) {
temp = temp->next; count++;
}
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = temp->next;
newNode->prev = temp;
temp->next->prev = newNode;
temp->next = newNode;
}
void displayForward() {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtBeginning(5);
insertAtPosition(15, 3);
displayForward();
return 0;
}The program maintains circular links even for head or middle insertions. Pointer adjustments guarantee both forward and backward traversal remain valid.
Program 3: Update a Node
This program searches for a node by value and updates it. Traversal ensures all nodes are checked without breaking circularity.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = newNode->prev = head;
return;
}
Node *tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
void updateNode(int oldValue, int newValue) {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
do {
if (temp->data == oldValue) {
temp->data = newValue;
printf("Node updated from %d to %d\n", oldValue, newValue);
return;
}
temp = temp->next;
} while (temp != head);
printf("Node with value %d not found\n", oldValue);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
updateNode(20, 25);
updateNode(50, 60);
return 0;
}Every node is checked using a do-while loop. Updating preserves all pointers, keeping the CDLL intact.
Program 4: Delete a Node
This program deletes a node by value while maintaining circularity. It handles head, middle, or single-node deletions safely.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = newNode->prev = head;
return;
}
Node *tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
void deleteNode(int value) {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
do {
if (temp->data == value) {
if (temp->next == temp) {
free(temp);
head = NULL;
return;
} // single node
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
if (temp == head) head = temp->next;
free(temp);
return;
}
temp = temp->next;
} while (temp != head);
printf("Node with value %d not found\n", value);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
deleteNode(20);
deleteNode(10);
deleteNode(30);
return 0;
}Deletion updates both next and prev pointers. Head or single-node deletions are handled separately to avoid breaking circularity.
Program 5: Delete at Beginning
This program deletes the first node while maintaining CDLL links. The head is updated to the next node, and the last node’s next and prev pointers are updated.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = newNode->prev = head;
return;
}
Node *tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
void deleteAtBeginning() {
if (!head) {
printf("List is empty\n");
return;
}
if (head->next == head) {
free(head);
head = NULL;
return;
}
Node *tail = head->prev;
Node *temp = head;
head = head->next;
tail->next = head;
head->prev = tail;
free(temp);
}
void displayForward() {
if (!head) { printf("List is empty\n"); return; }
Node *temp = head;
printf("Forward: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayForward();
deleteAtBeginning();
displayForward();
return 0;
}The program carefully updates the head and tail pointers. Single-node lists are handled separately to maintain circularity.
Program 6: Delete at End
This program deletes the last node of a CDLL. The second-to-last node becomes the new tail, maintaining both forward and backward links.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = newNode->prev = head;
return;
}
Node *tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
void deleteAtEnd() {
if (!head) {
printf("List is empty\n");
return;
}
if (head->next == head) {
free(head); head = NULL;
return;
}
Node *tail = head->prev;
Node *newTail = tail->prev;
newTail->next = head;
head->prev = newTail;
free(tail);
}
void displayForward() {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayForward();
deleteAtEnd();
displayForward();
return 0;
}The program ensures circular links remain intact after deleting the last node. Single-node lists are handled as a special case.
Program 7: Delete at Specific Position
This program deletes a node at a specified position in a CDLL. The pointers of neighboring nodes are updated to maintain circularity.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = newNode->prev = head;
return;
}
Node *tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
void deleteAtBeginning() {
if (!head) {
printf("List is empty\n");
return;
}
if (head->next == head) {
free(head);
head = NULL;
return;
}
Node *tail = head->prev;
Node *temp = head;
head = head->next;
tail->next = head;
head->prev = tail;
free(temp);
}
void deleteAtPosition(int pos) {
if (!head) {
printf("List is empty\n");
return;
}
if (pos < 1) {
printf("Invalid position\n");
return;
}
Node *temp = head;
int count = 1;
if (pos == 1) {
deleteAtBeginning();
return;
}
do {
if (count == pos) {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
return;
}
temp = temp->next;
count++;
} while (temp != head);
printf("Position out of range\n");
}
void displayForward() {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
displayForward();
deleteAtPosition(3);
displayForward();
return 0;
}The program handles head deletion separately. Out-of-range positions are reported to prevent invalid memory access.
Program 8: Search in Circular Linked List
This program searches for a value in a CDLL. It traverses the list fully in a circular manner, confirming presence or absence.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = newNode->prev = head;
return;
}
Node *tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
void searchValue(int value) {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
do {
if (temp->data == value) {
printf("Value %d found\n", value);
return;
}
temp = temp->next;
} while (temp != head);
printf("Value %d not found\n", value);
}
void displayForward() {
if (!head) {
printf("List is empty\n"); return;
}
Node *temp = head;
printf("Forward: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayForward();
searchValue(20);
searchValue(100);
return 0;
}Traversal continues until either the value is found or the list completes a full cycle. Circular and bidirectional links are preserved throughout.
FAQs
Q1: How is traversal done in a CDLL?
A do-while loop starting from head ensures that all nodes are visited once, respecting circularity.
Q2: Can a CDLL have only one node?
Yes, the single node’s next and prev point to itself, preserving circularity.
Q3: What is the time complexity for operations?
Insertion, deletion, search, and update are O(n) in the worst case.
Q4: Does a CDLL require extra memory?
Only for the prev pointer in addition to the node data and next pointer.
Conclusion
Circular doubly linked lists allow continuous bidirectional traversal and are ideal for cyclic operations. Proper management of next and prev pointers ensures list integrity during insertions, deletions, updates, and searches. Mastery of CDLLs provides a strong foundation for advanced data structures and efficient cyclic algorithms.
References & Additional Resources
The following books and online resources provide both theoretical foundations and practical examples to help you understand more on the topic.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference on C fundamentals, including pointers and memory, critical for linked list operations.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of linked lists, dynamic memory allocation, and related algorithms.
- GeeksforGeeks: Circular Doubly Linked List – Comprehensive explanation and implementation examples.
- Tutorialspoint: What is Dynamic Memory Allocation in C? – Explanation of
malloc(),calloc(),realloc(), andfree()functions for memory management. - C Standard Library Documentation – Memory Management – Official reference for memory allocation and deallocation functions in C.
