A circular linked list is a variation of a linked list where the last node points back to the first node, forming a closed loop. This allows continuous traversal from any node, which is useful in applications like round-robin scheduling, CPU task management, and buffering. Mastering circular linked lists is essential for implementing operations that require cyclic behavior and strengthens your understanding of advanced data structures.
Understanding the Problem
The main challenge in circular linked lists is maintaining the circular connection when performing insertions, deletions, or updates. Special care must be taken when modifying the head node, as it affects the last node’s pointer that keeps the loop intact. Traversal operations must account for the circular nature to avoid infinite loops, and edge cases such as empty or single-node lists require careful handling.
Program 1: Insertion at End and Display
This program demonstrates how to insert nodes at the end of a circular linked list and display all the nodes. The insertion function ensures that the new node points back to the head to maintain circularity, while the display function uses a do-while loop to traverse the list exactly once, including the head node.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
void display() {
if (!head) {
printf("Circular Linked List is empty\n");
return;
}
Node *temp = head;
printf("Circular List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
display();
return 0;
}This program defines a Node structure with data and next fields. The insertAtEnd function traverses the list to the last node and appends the new node, updating the new node’s pointer to point back to the head. The display function uses a do-while loop to ensure that every node, including the head, is printed exactly once.
Program 2: Insertion at Beginning and Specific Position
This program adds functionality to insert nodes at the beginning or at a specified position. Maintaining circularity is crucial when inserting at the head because the last node’s pointer must always point to the new head.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
void insertAtBeginning(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
newNode->next = head;
temp->next = newNode;
head = newNode;
}
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;
temp->next = newNode;
}
void display() {
if (!head) {
printf("Circular Linked List is empty\n");
return;
}
Node *temp = head;
printf("Circular List: ");
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);
display();
return 0;
}The insertion functions handle both empty and non-empty lists. insertAtBeginning updates the last node’s next pointer to the new head, while insertAtPosition uses traversal to attach the new node at the correct position without breaking circularity.
Program 3: Update a Node
This program updates a node’s value by searching for the old value in the circular linked list. The traversal ensures all nodes, including the head, are checked.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
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);
}
void display() {
if (!head) {
printf("Circular Linked List is empty\n");
return;
}
Node *temp = head;
printf("Circular List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
display();
updateNode(20, 25);
display();
return 0;
}The function traverses the list using a do-while loop to ensure every node is checked. If the node with the specified value is found, its data field is updated. Otherwise, a message is printed. No pointers are modified, preserving the circular structure.
Program 4: Delete a Node
This program deletes a node by value while maintaining the circular nature of the list. It handles deleting the head, middle, or the only node in the list.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode; newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
void deleteNode(int value) {
if (!head) {
printf("List is empty\n");
return;
}
Node *current = head, *prev = NULL;
if (head->data == value) {
if (head->next == head) {
free(head); head = NULL;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = head->next;
Node *del = head;
head = head->next;
free(del);
return;
}
do {
prev = current;
current = current->next;
if (current->data == value) {
prev->next = current->next;
free(current);
return;
}
} while (current != head);
printf("Node with value %d not found\n", value);
}
void display() {
if (!head) {
printf("Circular Linked List is empty\n");
return;
}
Node *temp = head;
printf("Circular List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
display();
deleteNode(20);
display();
deleteNode(10);
display();
deleteNode(30);
display();
return 0;
}Deletion carefully updates pointers to maintain circularity. The function checks for an empty list, single-node list, and head node deletion separately. For other nodes, it traverses until it finds the target, updates the previous node’s pointer, and frees the memory.
Program 5: Delete at Beginning
This program deletes the first node of a circular linked list. It updates the head pointer and ensures the last node points to the new head to maintain circularity.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
void deleteAtBeginning() {
if (!head) {
printf("List is empty\n");
return;
}
if (head->next == head) { // single node
free(head);
head = NULL;
return;
}
Node *temp = head;
Node *last = head;
while (last->next != head) last = last->next;
head = head->next;
last->next = head;
free(temp);
}
void display() {
if (!head) {
printf("Circular Linked List is empty\n");
return;
}
Node *temp = head;
printf("Circular List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
display();
deleteAtBeginning();
display();
return 0;
}This program updates the head to the second node and keeps the last node linked to the new head. Single-node deletion is handled separately.
Program 6: Delete at End
This program deletes the last node of a circular linked list. It traverses to the second-to-last node, updates its next pointer to the head, and frees the last node.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
void deleteAtEnd() {
if (!head) {
printf("List is empty\n");
return;
}
if (head->next == head) { // single node
free(head);
head = NULL;
return;
}
Node *temp = head;
Node *prev = NULL;
while (temp->next != head) {
prev = temp;
temp = temp->next;
}
prev->next = head;
free(temp);
}
void display() {
if (!head) {
printf("Circular Linked List is empty\n");
return;
}
Node *temp = head;
printf("Circular List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
display();
deleteAtEnd();
display();
return 0;
}This program safely removes the last node by keeping track of the previous node. Single-node deletion is treated separately to avoid dangling pointers.
Program 7: Delete at Specific Position
This program deletes a node at a given position (1-based index). It traverses the list to that position, updates the previous node’s next pointer, and frees the target node.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
void deleteAtPosition(int pos) {
if (!head) {
printf("List is empty\n");
return;
}
if (pos == 1) { // delete head
if (head->next == head) {
free(head);
head = NULL;
return;
}
Node *last = head;
while (last->next != head) last = last->next;
Node *temp = head;
head = head->next;
last->next = head;
free(temp);
return;
}
Node *current = head;
Node *prev = NULL;
int count = 1;
do {
prev = current;
current = current->next;
count++;
if (count == pos) break;
} while (current != head);
if (current == head) {
printf("Position out of range\n");
return;
}
prev->next = current->next;
free(current);
}
void display() {
if (!head) {
printf("Circular Linked List is empty\n");
return;
}
Node *temp = head;
printf("Circular List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
display();
deleteAtPosition(3);
display();
return 0;
}This program safely deletes the node at the specified position. Head deletion and out-of-range positions are handled separately.
Program 8: Search in Circular Linked List
This program searches for a node with a given value in a circular linked list. It traverses until the value is found or returns to the head, indicating the value is not present.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
if (!head) {
head = newNode;
newNode->next = head;
return;
}
Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
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 display() {
if (!head) {
printf("Circular Linked List is empty\n");
return;
}
Node *temp = head;
printf("Circular List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
display();
searchValue(20);
searchValue(100);
return 0;
}This program traverses the circular list to find a value. If the value is present, it prints a confirmation; otherwise, it reports that the value is not found.
FAQs
Q1: How do you traverse a circular linked list?
A do-while loop ensures traversal includes the head and stops after one full cycle.
Q2: Can a circular linked list have only one node?
Yes, the single node points to itself, preserving circularity.
Q3: What is the time complexity of insertion, deletion, or update?
O(n) in the worst case, as traversal may be required.
Q4: Does a circular linked list require extra memory?
No, only the nodes themselves are required.
Conclusion
Circular linked lists allow continuous traversal and are ideal for cyclic operations. Proper pointer management during insertion, deletion, and updating ensures the list remains circular. Mastery of this data structure provides a strong foundation for more advanced structures and 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 Linked List in C – Explanation of circular linked list concepts and implementation details.
- Programiz: Data Structures – Circular Linked List – Beginner-friendly guide with examples for insertion, deletion, and traversal.
- 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.
