Circular Linked List in Data Structure – A Complete Guide
Basics of Python
5 Hrs. duration
9 Modules
1800+ Learners
Start Learning
A Circular Linked List (CLL) is a type of linked list where the last node’s next pointer points to the first node creating a circular structure. Due to this structure, some applications have the advantages of traversing continuously and making circular queues easy to implement. Circular linked lists, in particular, allow for efficient scheduling and managing of playlists and help here enable rapid switching between these tasks.
This guide will cover the circular linked lists in data structure and concepts related to it such as types, representation, operations, benefits and drawbacks and various usage will be discussed as well. Also, we will explain how to implement this software structure in C++ and Java programming with examples and explanations for certain parts of the code.
What is a Linked List?
A linked list is a collection of nodes that, when arranged one after another, will have all the nodes connected to form a list. Each node in a linked list has data stored in it and a pointer that refers to the next unit of a linked list. Various types of linked lists are as follows:
Single Linked List
Doubly Linked List
Circular Linked List
What is a Circular Linked List?
A circularly linked list is a type of linked list in which the last node’s next pointer points to the head node thus making it circular. It consists of two parts: data which is stored in the node and a pointer which points towards the next node. As a result, it is possible to traverse the list continuously without having to look for a NULL reference.
A typical node in a circular linked list can be defined as follows:
Data: It stores the value of the node.
Next: It is a reference pointer pointing to the next node in the linked list.
Types of Circular Linked Lists
There are two types of Circular linked lists in the data structure.
Circular Singly Linked List
In a Circular Singly Linked List, each node points to the next node also known as the `Next` pointer, and the last node points back to the first node. In this type of linked list, traversal can only be done in one direction i.e., in the forward direction.
Circular Doubly Linked List
In a Circular Doubly Linked List, each node contains two pointers: `Next`, pointing to the next node, and `Previous` pointing to the previous node. This linked list allows the traversal in both directions i.e., forward and backward.
Representation of Circular Linked List in Data Structures
In programming, circular linked lists are represented by a head pointer that points to the list’s initial node. To keep the circular structure intact, the next pointer from the last node needs to point back to the head node.
C++ Syntax:
class Node {
public:
int value;
Node* next; // Pointer to the next node
// Constructor
Node(int val) : value(val), next(nullptr) {}
};
Java Syntax:
class Node {
int value;
Node next; // Reference to the next node
// Constructor
public Node(int value) {
this.value = value;
this.next = null;
}
}
Note: From now onwards we will be working on a Circular Singly Linked List to write different examples in this guide.
Operations on Circular Linked List in Data Structure
In a Circular Linked List data structure, we can perform various operations such as:
Insertion
Deletion
Search
We will now see each operation of the circular linked list in a data structure in detail. We will see the C++ and Java code examples.
Insertion
Insertion in a circular linked list data structure makes it possible to insert data items as in a normal linked list, but the only difference is that we have to make the last node point to the head. There are mainly three insertion methods for circular linked lists:
Insertion at the Beginning: Allocate memory to create a new node and set the next part of this new node to the head part of the list. A pointer from the last element is redirected to point to the new element and the new element becomes the head of the list.
Insertion at the End: A new node is created and the linked list is traversed to the last pointer of the list. This is the pointer which points to the head node of the list and all next pointer nodes are adjusted to point to the new node, such that it appears after the last node.
Insertion at a Specific Position: Traverse the list to the specified position, then adjust pointers to insert the new node at that position.
C++ Example:
Insertion operation of a circular linked list with methods to insert nodes at the end, at the start, and at a specific position in C++.
#include <iostream>
using namespace std;
// Node structure for the circular linked list
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// Circular Linked List class
class CircularLL {
private:
Node* head;
public:
CircularLL() {
head = nullptr;
}
// Function to insert a new node at the end of the list
void insertNodeAtEnd(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
newNode->next = head; // Point to itself
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
// Function to insert a new node at the beginning of the list
void insertNodeAtBeginning(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
newNode->next = head; // Point to itself
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
head = newNode; // Update head
}
}
// Function to insert a new node at a specific position
void insertAtPosition(int value, int position) {
Node* newNode = new Node(value);
if (position == 0) {
insertNodeAtBeginning(value);
return;
}
Node* temp = head;
for (int i = 0; i < position - 1 && temp->next != head; ++i) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Function to print the circular linked list
void printList() {
if (head == nullptr) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};
// Main function to test the CircularLL class
int main() {
CircularLL ls;
ls.insertNodeAtBeginning(10);
ls.insertNodeAtBeginning(20);
ls.insertNodeAtBeginning(30);
ls.printList();
ls.insertAtPosition(34, 3);
ls.insertAtPosition(38, 4);
ls.printList();
ls.insertNodeAtEnd(40);
ls.insertNodeAtEnd(50);
ls.insertNodeAtEnd(60);
ls.printList();
return 0;
}
Output:
30 20 10
30 20 10 34 38
30 20 10 34 38 40 50 60
Java Example: Insertion operation of a circular linked list with methods to insert nodes at the end, at the start, and at a specific position in Java.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLL {
private Node head;
public CircularLL() {
head = null;
}
public void insertNodeAtEnd(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
newNode.next = head; // Point to itself
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}
}
// Insert at the beginning
public void insertNodeAtBeginning(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
newNode.next = head; // Point to itself
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
head = newNode; // Update head
}
}
// Insert at the position
public void insertAtPosition(int value, int position) {
Node newNode = new Node(value);
if (position == 0) {
insertNodeAtBeginning(value);
return;
}
Node temp = head;
for (int i = 0; i < position - 1 && temp.next != head; ++i) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
}
public void printList() {
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();
}
}
public class Main {
public static void main(String[] args) {
CircularLL ls = new CircularLL();
ls.insertNodeAtBeginning(10);
ls.insertNodeAtBeginning(20);
ls.insertNodeAtBeginning(30);
ls.printList();
ls.insertAtPosition(34, 3);
ls.insertAtPosition(38, 4);
ls.printList();
ls.insertNodeAtEnd(40);
ls.insertNodeAtEnd(50);
ls.insertNodeAtEnd(60);
ls.printList();
}
}
Output:
30 20 10
30 20 10 34 38
30 20 10 34 38 40 50 60
Deletion
Deletion operation in a circular linked list data structure allows us to delete any data items from the linked list. It can be complex in the case of a circular linked list. Deletion operations in a circular linked list can be performed in three main ways:
Deletion at the Beginning: Update the head pointer to the next node, and adjust the last node’s next pointer to point to the new head. If the list becomes empty (only one node), set the head to null.
Deletion at the End: Traverse the list to find the second-to-last node (the one pointing to the head), and update its next pointer to point to the head. If the list becomes empty (only one node), set the head to null.
Deletion at a Specific Position: Traverse the list to the designated position, move the pointers to avoid the node that has to be removed, and free its memory.
C++ Example:
Deletion of nodes in a circular linked list with methods such as deleting the first node, last node, and at a specific position in C++.
#include <iostream>
using namespace std;
// Node structure for the circular linked list
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// Circular Linked List class
class CircularLL {
private:
Node* head;
public:
CircularLL() {
head = nullptr;
}
// Function to insert a new node at the end of the list
void insertNode(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
newNode->next = head; // Point to itself
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
// Function to delete the first node
void deleteFirstNode() {
if (head == nullptr) return; // Empty list
Node* temp = head;
if (temp->next == head) {
head = nullptr; // Only one node
delete temp;
} else {
while (temp->next != head) {
temp = temp->next;
}
temp->next = head->next; // Bypass head
Node* toDelete = head; // Store node to delete
head = head->next; // Update head
delete toDelete; // Delete old head
}
}
// Function to delete the last node
void deleteLastNode() {
if (head == nullptr) return; // Empty list
Node* temp = head;
if (temp->next == head) {
head = nullptr; // Only one node
delete temp;
} else {
Node* prev = nullptr;
while (temp->next != head) {
prev = temp;
temp = temp->next;
}
prev->next = head; // Bypass last node
delete temp; // Delete the last node
}
}
// Function to delete a node at a given position
void deleteAtPosition(int position) {
if (head == nullptr) return; // Empty list
if (position == 0) {
deleteFirstNode();
return;
}
Node* temp = head;
Node* prev = nullptr;
for (int i = 0; temp->next != head && i < position; i++) {
prev = temp;
temp = temp->next;
}
if (temp == head) return; // Node not found
prev->next = temp->next; // Bypass the node
delete temp; // Delete the node
}
// Function to print the circular linked list
void printList() {
if (head == nullptr) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};
int main() {
CircularLL ls;
ls.insertNode(20);
ls.insertNode(30);
ls.insertNode(40);
ls.insertNode(50);
ls.insertNode(60);
cout << "Initial list: ";
ls.printList();
ls.deleteFirstNode();
cout << "After deleting the first node: ";
ls.printList();
ls.deleteLastNode();
cout << "After deleting the last node: ";
ls.printList();
ls.deleteAtPosition(2);
cout << "After deleting the node at position 2: ";
ls.printList();
return 0;
}
Output:
Initial list: 20 30 40 50 60
After deleting the first node: 30 40 50 60
After deleting the last node: 30 40 50
After deleting the node at position 2: 30 40
Java Example:
Deletion of nodes in a circular linked list with methods such as deleting the first node, last node, and at a specific position in Java.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLL {
private Node head;
public CircularLL() {
head = null;
}
public void insertNode(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
newNode.next = head; // Point to itself
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}
}
public void deleteFirstNode() {
if (head == null) return; // Empty list
Node temp = head;
if (temp.next == head) {
head = null; // Only one node
} else {
while (temp.next != head) {
temp = temp.next;
}
temp.next = head.next; // Bypass head
head = head.next; // Update head
}
}
public void deleteLastNode() {
if (head == null) return; // Empty list
Node temp = head;
if (temp.next == head) {
head = null; // Only one node
} else {
Node prev = null;
while (temp.next != head) {
prev = temp;
temp = temp.next;
}
prev.next = head; // Bypass last node
}
}
public void deleteAtPosition(int position) {
if (head == null) return; // Empty list
if (position == 0) {
deleteFirstNode();
return;
}
Node temp = head;
Node prev = null;
for (int i = 0; temp.next != head && i < position; i++) {
prev = temp;
temp = temp.next;
}
if (temp == head) return; // Node not found
prev.next = temp.next; // Bypass the node
}
public void printList() {
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();
}
}
public class Main {
public static void main(String[] args) {
CircularLL ls = new CircularLL();
ls.insertNode(1);
ls.insertNode(2);
ls.insertNode(3);
ls.insertNode(4);
ls.insertNode(5);
ls.printList();
ls.deleteFirstNode();
ls.printList();
ls.deleteLastNode();
ls.printList();
ls.deleteAtPosition(2);
ls.printList();
}
}
Output:
1 2 3 4 5
2 3 4 5
2 3 4
2 3
Searching
Searching can be done in a circular linked list data structure. To search for a node, start at the head node, and proceed through the list, comparing the value of each node to the desired value. If the value is located, return the position, otherwise, the node is not present.
C++ Example:
Searching operation of items in a circular linked list using C++.
#include <iostream>
using namespace std;
// Node structure for the circular linked list
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// Circular Linked List class
class CircularLL {
private:
Node* head;
public:
CircularLL() {
head = nullptr;
}
// Function to insert a new node at the end of the list
void insertNode(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
newNode->next = head; // Point to itself
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
// Function to search for a node with a given value
void searchNode(int value) {
if (head == nullptr) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
int index = 0;
do {
if (temp->data == value) {
cout << "Node with value " << value << " found at position " << index << "." << endl;
return;
}
temp = temp->next;
index++;
} while (temp != head);
cout << "Node with value " << value << " not found." << endl;
}
// Function to print the circular linked list
void printList() {
if (head == nullptr) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};
int main() {
CircularLL ls;
ls.insertNode(1);
ls.insertNode(2);
ls.insertNode(3);
ls.insertNode(4);
ls.insertNode(5);
cout << "Initial list: ";
ls.printList();
ls.searchNode(3);
ls.searchNode(5);
ls.searchNode(6);
return 0;
}
Output:
Initial list: 1 2 3 4 5
Node with value 3 found at position 2.
Node with value 5 found at position 4.
Node with value 6 not found.
Java Example:
Searching operation of items in a circular linked list using Java.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLL {
private Node head;
public CircularLL() {
head = null;
}
public void insertNode(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
newNode.next = head; // Point to itself
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}
}
public void searchNode(int value) {
if (head == null) {
System.out.println("List is empty.");
return;
}
Node temp = head;
int index = 0;
do {
if (temp.data == value) {
System.out.println("Node with value " + value + " found at position " + index + ".");
return;
}
temp = temp.next;
index++;
} while (temp != head);
System.out.println("Node with value " + value + " not found.");
}
public void printList() {
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();
}
}
public class Main {
public static void main(String[] args) {
CircularLL ls = new CircularLL();
ls.insertNode(1);
ls.insertNode(2);
ls.insertNode(3);
ls.insertNode(4);
ls.insertNode(5);
ls.printList();
ls.searchNode(3);
ls.searchNode(5);
ls.searchNode(6);
}
}
Output:
1 2 3 4 5
Node with value 3 found at position 2.
Node with value 5 found at position 4.
Node with value 6 not found.
Advantages and Disadvantages of Circular Linked List
Advantages
No Null Pointers: The last node points towards the first node itself and as a result null pointers are never required in a circular linked list. This ensures that there is always a valid node to traverse to, which simplifies the logic for traversal and operations like insertion and deletion.
Resource Sharing: Useful in a round-robin algorithm as this method can coordinate the allocation of the resources/tasks in a circular list/cycle through the tasks in a repetitive manner.
Easy Traversal: Circular linked lists simplify if there is a bi-directional (two-sided) pointer whatever it may be at the end that connects back or jumps back to the start. This unique property encourages the use of circular linked lists in cases where there is a need to keep going around.
Improved Performance: The performance gets improved in game development or any other task utilising a circular linked list.
Simplified Operations: Insertion and deletion operations are said to be easier as there is no overhead needed to always look for nulls when one is changing the structure of the list. Whichever one is required at a given time and the place is known, both may be undertaken in constant time O(1).
Disadvantages
Complex Implementation: An instance of a complex structure that breaks down in two or more structured outfits is known as a circular linked list. However, the viral structure of a circular linked list is not as easy to implement as that of a singly linked list, or a doubly linked list.
Overhead in Traversing: To avoid infinite loop issues, care must be taken when stopping the traversal of the list. To avoid such problems, it is imperative to maintain track of the starting point.
Problems with Debugging: Because linked lists are circular, debugging can be more difficult because standard techniques for navigating them might not work.
Memory Usage: In contexts with limited memory, each node in a doubly circular linked list consumes extra memory for the backward connection.
Lack of Direct Access: Circular linked lists do not support direct access to nodes (as in arrays). Traversing the list to find a specific element may lead to increased time complexity O(n) in the worst case.
Applications of Circular Linked List
Round Robin Scheduling: Circular Linked lists are heavily used in operating systems when scheduling processes. The round-robin allocation synchronising algorithm makes use of a circular list and distributes time slices among processes in a repetitive and fair method.
Multiplayer Games: Multiplayer gaming applications also use circular linked lists to prevent any potential wastage of player turn management. As soon as a player completes their turn, the control is passed to the next player in a loop without much thought making the game easy to feed to players.
Music Playlists: Some applications such as the music player that requires a user to play the songs for eternity are perfectly supported by circular linked lists. When one reaches the last song, there is another song waiting which is the first one if the user has decided to continue.
Implementation of Circular Queues: Circular queues may be implemented using circular linked lists. This space-efficient structure helps in using memory space effectively as it does not waste space due to running out of length.
Computer Networking: Networking applies circular linked lists such as in the case of token ring networks in which all the computers on the network get the turn to send out data in a progressive circular fashion.
Conclusion
Circular linked lists in the data structure are a flexible and powerful data structure that offers advantages beyond the scope of traditional linear structures for some particular applications. In this guide, we have discussed circular linked lists in detail, their types, ways of representing them, various operations with the help of many code examples, and various applications.
Overall, circular linked lists are one of the very important core learnings and implementations for any C++ programmer either a beginner or a professional, as they form the base of knowledge of handling data structures and algorithms. By using the characteristics of circular linked lists, an application can be made to feature improved efficiency and responsiveness in a wide range of domains. Want to study data structure in depth? Consider enrolling in the Certificate Program in Application Development at Hero Vired.
FAQs
What is a Circular Linked List?
A circular linked list is another version of a linked list in which all nodes are connected in two ways. Unlike a traditional linked list that ends with a null pointer, the last node in a circular linked list points back to the first node, creating a loop.
What differentiates a circular linked list from a normal linked list?
The 'next' pointer of the final node in a regular linked list points to null. However, in a circular linked list, the head (first element) of the list is pointed to by the 'next' pointer of the final node.
How many types of Circular Linked Lists are there?
There are two types of circular linked lists:
Circular Singly Linked List: It is a linked list where a node has only a next pointer but the last node points to the first node.
Circular Doubly Linked List: It is a linked list where a node has two pointers, one of them points to the next node, and the other one points to the previous node.
Does a circular linked list have a head?
Yes, essentially circular linked lists also have a head pointer (or reference) pointing to the first node in the list. But in contrast with traditional linked lists, even if the list is empty, this head need not be null; it could very well be pointing to the last node, which in turn points back to itself, showing that the list is empty.
How do you count the number of elements in the circular linked list?
In a circular linked list, you can count the elements by starting at the head node and counting the nodes you visit as you work your way down the list. When you get back to the head node, you stop as the list is circular. See the following example code:
Example:
int countElements() {
if (head == nullptr) return 0; // Empty list
int cnt = 0;
Node* current = head;
do {
cnt++;
current = current->next; // Move to the next node
} while (current != head); // Stop when we reach the head again
return cnt;
}
Deploying Applications Over the Cloud Using Jenkins
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
