Circular Linked List
A circular linked list is a data structure where each node contains a reference to the next node in the list, and the last node in the list points back to the first node. This creates a circular loop that can be traversed infinitely.
This structure allows for continuous traversal through the elements, providing unique features compared to linear linked lists. In a singly linked list, the last node points to NULL, but in a circular linked list, the last node points back to the first node.
Representation of a Circular Linked List
A circular linked list is a type of linked list in which the last node of the list points back to the first node, creating a circular structure. In a traditional linear linked list, the last node points to null, indicating the end of the list. However, in a circular linked list, the last node's next reference points back to the first node, forming a loop. Key concepts of circular linked lists:
- Node : The basic building block containing data and a reference to the next node.
- Head : The starting point of the list, representing the first node.
- Tail : The last node in the list, where the next reference points back to the head.
Uses of Circular Linked List
Circular linked lists find applications in various scenarios where the cyclic nature of the structure is advantageous. Here are some common use cases where circular linked lists are particularly useful:- Task Scheduling Algorithms : Circular linked lists are employed in task scheduling algorithms where a set of tasks needs to be continuously processed in a cyclic manner. Each node represents a task, and the circular structure ensures that tasks are processed in a loop.
- Circular Buffers and Queues : Circular linked lists are suitable for implementing circular buffers or queues, where data is continuously added and processed in a loop. This is common in scenarios where a fixed-size buffer is used to store and retrieve data.
- Rotational Systems : In rotational systems such as round-robin scheduling in operating systems, circular linked lists are used to manage the order in which tasks or processes are executed. Each node represents a task, and tasks are processed in a cyclic order.
- Music Playlist with Looping : Circular linked lists are employed in music playlist implementations where users want the playlist to loop continuously. Each node represents a song, and the circular structure ensures that the playlist seamlessly repeats.
- Game Development - Animation Sequences : In game development, circular linked lists can be used to represent animation sequences. Each node represents a frame of animation, and the circular structure allows for looping through the frames in a continuous manner.
- Clockwise and Anticlockwise Navigation : Circular linked lists are suitable for scenarios where navigation needs to occur in both clockwise and anticlockwise directions. This is applicable in applications like image galleries or circular menus.
Advantages and Limitations of Circular Linked List
Advantages
- Circular linked lists facilitate continuous traversal, and any node can be the starting point, providing flexibility in accessing elements.
- Insertion and deletion operations at the beginning of the list can be performed in constant time.
- Circular linked lists are well-suited for scenarios where operations need to cycle through elements continuously, such as in certain scheduling algorithms.
Limitations
- Implementing circular linked lists can be more complex than linear linked lists due to the need to handle circular references.
- Each node in a circular linked list requires an additional reference, contributing to increased memory usage compared to linear lists.
- If not implemented correctly, traversing a circular linked list can lead to infinite loops if not properly handled.
Common Circular Linked List Operations
Add a Node to Circular Linked List
To add a node to a circular linked list, we need to create a new node and set its next field to point to the first node in the list. Then we set the next field of the last node in the list to point to the new node. Finally, we update the head pointer to point to the new node.
Traverse a Circular Linked List
To traverse a circular linked list, we start at the head node and follow the next pointers until we reach the head node again.
Delete a Node from Circular Linked List
To delete a node from a circular linked list, we need to update the next field of the previous node to point to the node after the one we want to delete. Then we can free the memory allocated to the node we want to delete. If we are deleting the first node in the list, we also need to update the head pointer.
Search an Element in Circular Linked List
To search for an element in a circular linked list, we start at the head node and follow the next pointers until we find the node containing the element we are looking for, or we reach the head node again.
Circular Linked List Operations Time Complexity
- To add a node at the end of a circular linked list: O(1)
- Traverse a circular linked list: O(n)
- Delete a node from circular linked list: O(n)
- Search an element in circular linked list: O(n)
Circular Linked List Implementation Program
Here's an example program that demonstrates how to implement a circular linked list in C.
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct node {
int data;
struct node* next;
};
// Add node to circular linked list
void addNode(struct node** head_ref, int new_data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
struct node* last = *head_ref;
new_node->data = new_data;
new_node->next = *head_ref;
if (*head_ref == NULL) {
*head_ref = new_node;
new_node->next = new_node;
printf("Node added : %d \n", new_data);
return;
}
while (last->next != *head_ref) {
last = last->next;
}
last->next = new_node;
*head_ref = new_node;
printf("Node added : %d \n", new_data);
}
// Traverse the circular linked list
void traverseList(struct node* head) {
struct node* temp = head;
printf("Circular Linked List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
// Delete a node from the circular linked list
void deleteNode(struct node** head_ref, int key) {
if (*head_ref == NULL) {
return;
}
struct node* curr = *head_ref, *prev;
while (curr->data != key) {
if (curr->next == *head_ref) {
return;
}
prev = curr;
curr = curr->next;
}
if (curr->next == *head_ref && curr == *head_ref) {
*head_ref = NULL;
free(curr);
return;
}
if (curr == *head_ref) {
prev = *head_ref;
while (prev->next != *head_ref) {
prev = prev->next;
}
*head_ref = (*head_ref)->next;
prev->next = *head_ref;
free(curr);
} else if (curr->next == *head_ref) {
prev->next = *head_ref;
free(curr);
} else {
prev->next = curr->next;
free(curr);
}
printf("Node deleted : %d \n", key);
}
// Search for an element in the circular linked list
int searchList(struct node* head, int key) {
struct node* current = head;
int count = 0;
if (head == NULL) {
return -1;
}
do {
count++;
if (current->data == key) {
return count;
}
current = current->next;
} while (current != head);
return -1;
}
// Main function
int main() {
struct node* head = NULL;
// Add nodes to circular linked list
addNode(&head, 1);
addNode(&head, 2);
addNode(&head, 3);
addNode(&head, 4);
addNode(&head, 5);
traverseList(head);
// Delete a node from the circular linked list
deleteNode(&head, 3);
traverseList(head);
// Search for an element in the circular linked list
int key = 4;
int pos = searchList(head, key);
if (pos == -1) {
printf("%d not found in the list\n", key);
} else {
printf("%d found at position %d\n", key, pos);
}
// Traverse the circular linked list
traverseList(head);
return 0;
}
Output
Node added : 1 Node added : 2 Node added : 3 Node added : 4 Node added : 5 Circular Linked List: 5 4 3 2 1 Node deleted : 3 Circular Linked List: 5 4 2 1 4 found at position 2 Circular Linked List: 5 4 2 1
Conclusion
Circular linked lists provide a unique structure with continuous traversal capabilities, making them suitable for certain scenarios. Understanding the basic operations, implementation details, and best practices empowers developers to leverage circular linked lists effectively. The choice of using a circular linked list should be based on the specific requirements of the application, considering both the advantages and limitations associated with this data structure. By incorporating best practices, developers can ensure robust implementations and harness the benefits of circular linked lists in their programs.