Published: 13 Dec 2024 | Reading Time: 6 min read
A linked list is a linear data structure containing nodes where each node has a value and reference such as links to the next node of the list. A circular linked list is a loop of the data structure where the last node in the list connects to the first node. This article delves into the concept, implementation, and applications of circular linked lists.
A Circular Linked List (CLL) is a data structure in which a group of nodes are connected to form a circle, where the last node points back to the first node. This means that there is no terminating null pointer at the end of the list.
The two main types of circular linked lists are:
In a Circular Singly Linked List, each node points to the next node, and the last node points back to the first node. It allows one-way traversal, i.e., you can traverse the list from the head node to the last node and back to the head.
A Circular Doubly Linked List is more advanced as each node contains two pointers where one pointing to the next node and another pointing to the previous node. The last node points to the head, and the head points to the last node, forming a circle.
Here are the basic operations performed on the circular linked list:
Traverse all nodes starting from a given node and looping back to the start.
Find a specific node in the circular linked list.
Here is the implementation of a circular linked list in data structures in C, C++, and Java:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data; struct Node* next;
};
struct Node* head = NULL;
// Function to insert at the beginning
void insertAtBeginning(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (head == NULL) {
newNode->next = newNode; // Point to itself if it's the only node
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != head)
temp = temp->next;
temp->next = newNode;
newNode->next = head;
head = newNode;
}
}
// Function to insert at the end
void insertAtEnd(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (head == NULL) {
newNode->next = newNode;
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != head)
temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
}
// Function to display the circular linked list
void displayList() {
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("(head)\n");
}
int main() {
insertAtBeginning(10);
insertAtBeginning(20);
insertAtEnd(30);
insertAtEnd(40);
displayList(); // Output: 20 -> 10 -> 30 -> 40 -> (head)
return 0;
}
#include <iostream>
using namespace std;
class CircularLinkedList {
public:
struct Node {
int data;
Node* next;
};
Node* head;
CircularLinkedList() {
head = nullptr;
}
// Function to insert at the beginning
void insertAtBeginning(int data) {
Node* newNode = new Node();
newNode->data = data;
if (!head) {
newNode->next = newNode;
head = newNode;
} else {
Node* temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
head = newNode;
}
}
// Function to insert at the end
void insertAtEnd(int data) {
Node* newNode = new Node();
newNode->data = data;
if (!head) {
newNode->next = newNode;
head = newNode;
} else {
Node* temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
}
// Function to display the circular linked list
void displayList() {
if (!head) {
cout << "List is empty.\n";
return;
}
Node* temp = head;
do {
cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
cout << "(head)" << endl;
}
};
int main() {
CircularLinkedList cll;
cll.insertAtBeginning(10);
cll.insertAtBeginning(20);
cll.insertAtEnd(30);
cll.insertAtEnd(40);
cll.displayList(); // Output: 20 -> 10 -> 30 -> 40 -> (head)
return 0;
}
class CircularLinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head = null;
// Insert at the beginning
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
newNode.next = newNode;
head = newNode;
} else {
Node temp = head;
while (temp.next != head)
temp = temp.next;
temp.next = newNode;
newNode.next = head;
head = newNode;
}
}
// Insert at the end
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
newNode.next = newNode;
head = newNode;
} else {
Node temp = head;
while (temp.next != head)
temp = temp.next;
temp.next = newNode;
newNode.next = head;
}
}
// Display the list
public void displayList() {
if (head == null) {
System.out.println("List is empty.");
return;
}
Node temp = head;
do {
System.out.print(temp.data + " -> ");
temp = temp.next;
} while (temp != head);
System.out.println("(head)");
}
public static void main(String[] args) {
CircularLinkedList cll = new CircularLinkedList();
cll.insertAtBeginning(10);
cll.insertAtBeginning(20);
cll.insertAtEnd(30);
cll.insertAtEnd(40);
cll.displayList(); // Output: 20 -> 10 -> 30 -> 40 -> (head)
}
}
Here are the advantages and disadvantages of a circular linked list in data structures:
Continuous Traversal: A circular linked list allows for continuous traversal from any node, without encountering a null value or reaching the end of the list.
Efficient Operations: Insertion and deletion operations can be performed efficiently, as the last node's next pointer points back to the first node, eliminating the need to traverse the entire list.
Easy Loop Control: Finding the end of the list or loop control is easier, as there are no null values to mark the beginning and end.
Round-Robin Scheduling: Circular linked lists are suitable for Round-Robin scheduling algorithms, where processes are queued circularly.
Fibonacci Heaps: Circular linked lists can be used to implement Fibonacci heaps, a specialized data structure for priority queues.
Increased Complexity: Circular linked lists are more complex than singly linked lists, as they require additional logic to handle the circular structure.
Difficult Reversal: Reversing a circular linked list is more challenging than reversing a singly or doubly linked list, as it requires careful handling of the circular structure.
Infinite Loop Risk: If not handled correctly, circular linked lists can lead to infinite loops during traversal or insertion/deletion operations.
Harder End Detection: Finding the end of the list or loop control can be harder than in a singly linked list, as there are no explicit null values to mark the beginning and end.
No Direct Access: Circular linked lists do not support direct access to elements, as the next pointer of each node only points to the next node in the circular sequence.
Here are the applications that use circular linked lists in real life:
Circular Linked Lists are used in scheduling algorithms like round-robin scheduling, where each process is allocated a fixed time slot in a cyclic manner.
In memory management systems, Circular Linked Lists are used to manage memory blocks in a circular fashion, which allows efficient memory reuse.
In games, Circular Linked Lists are used to manage players cyclically. For example, in a multiplayer game, the turn of players can be managed using a Circular Linked List.
Circular Linked Lists are often used in buffering data in networking applications where the buffer is reused circularly.
In conclusion, a circular linked list is a flexible data structure with practical applications in real life. It offers insertion and deletion operations, efficient memory utilization, and suitable applications in multi-programming operating systems and games with multiple players. However, they also require more complex algorithms and can be error-prone if not implemented correctly.
To insert a new node at the beginning, create a new node and make it point to the current head (which is the tail->next). Once this is done, update the current tail's next node to point to the new one. As a final step, update the head reference to point to the new node.
Yes, Circular Linked Lists can be implemented using either singly linked lists or doubly linked lists. The main difference is that the last node in a circular linked list points back to the first node, whereas in a regular linked list, the last node points to NULL.
When implementing Circular Linked Lists, it's essential to handle errors and edge cases, such as inserting a new node at an invalid position, deleting a non-existent node, or traversing an empty list. Proper error handling and boundary checking can help prevent bugs and ensure the reliability of your implementation.
Source: NxtWave (CCBP.in)
Contact: [email protected] | +919390111761 (WhatsApp only)