A Circular Linked List is a variation of the linked list where the last node points back to the first node, forming a circle. It can be:
- Singly Circular Linked List: Each node points to the next node, and the last node points back to the first node.
- Doubly Circular Linked List: Each node has pointers to both the previous and next nodes, and the last node points to the first node in both directions.
Structure of a Circular Linked List Node
For Singly Circular Linked List:
struct Node {
int data; // Data part
struct Node* next; // Pointer to the next node
};
For Doubly Circular Linked List:
struct Node {
int data; // Data part
struct Node* next; // Pointer to the next node
struct Node* prev; // Pointer to the previous node
};
Characteristics of Circular Linked Lists
- The list forms a closed loop.
- It eliminates the NULL pointer by linking the last node back to the first node.
- Traversal can start at any node and continue indefinitely in the loop.
- It is useful in applications where we need to repeatedly cycle through the elements.
Operations on Circular Linked List
1. Traversal
a. Traversal for Singly Circular Linked List
void traverse(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. Traversal for Doubly Circular Linked List
void traverseDoubly(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”);
}
2. Insertion
a. Insert at the Beginning (Singly Circular Linked List)
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; // The only node points to itself
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
*head = newNode;
}
b. Insert at the End (Singly Circular Linked List)
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;
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
}
3. Deletion
a. Delete from the Beginning (Singly Circular Linked List)
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* last = *head;
while (last->next != *head) {
last = last->next;
}
last->next = temp->next;
*head = temp->next;
free(temp);
}
b. Delete from the End (Singly Circular Linked List)
void deleteFromEnd(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* prev = NULL;
while (temp->next != *head) {
prev = temp;
temp = temp->next;
}
prev->next = *head;
free(temp);
}
Example Program
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function prototypes
void insertAtEnd(struct Node** head, int value);
void deleteFromBeginning(struct Node** head);
void traverse(struct Node* head);
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf(“Circular Linked List after insertion:\n”);
traverse(head);
deleteFromBeginning(&head);
printf(“Circular Linked List after deletion:\n”);
traverse(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;
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
}
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* last = *head;
while (last->next != *head) {
last = last->next;
}
last->next = temp->next;
*head = temp->next;
free(temp);
}
void traverse(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”);
}
Output Example
Circular Linked List after insertion:
10 -> 20 -> 30 -> (back to head)
Circular Linked List after deletion:
20 -> 30 -> (back to head)
Advantages of Circular Linked List
- Efficient Traversal: Can traverse continuously without resetting the pointer.
- Useful in Queues: Ideal for applications like buffers and real-time scheduling.
- No NULL Pointer: Eliminates the need to check for the end of the list.
Disadvantages of Circular Linked List
- Complex Implementation: Managing circular connections requires more effort.
- No Direct Access: Requires sequential traversal for access.
- Extra Pointer Overhead: Needs additional memory for circular pointers.
Applications of Circular Linked List
- Music Players: To cycle through playlists.
- Token Passing in Networks: Circular token passing in ring networks.
- Scheduling Algorithms: Useful in round-robin scheduling.