All About Circular Linked Lists

All About Circular Linked Lists

19 mins read1.7K Views Comment
clickHere
Updated on Dec 18, 2023 14:03 IST

Have you ever wondered how data structures can efficiently manage cyclic data? A circular linked list offers an elegant solution. Unlike traditional linear linked lists, where the last node points to null, in a circular linked list, it loops back to the first node, creating a continuous, circular chain of nodes. Let's understand more!

A circular linked list is an interesting type of data structure where the last node in the list points back to the first node, creating a loop. This property of circular linked lists distinguishes it from linear linked lists and produces multiple opportunities for effective data organisation and management. This article will explore the construction, functions, benefits, and real-world uses of circular linked lists in computer science and other fields.

Introduction to Linked List in C++
Introduction to Linked List in C++
Have you ever wondered how a data sequence can be managed efficiently without the constraints of physical storage order? In C++, a linked list data structure offers this flexibility, allowing...read more

Table of Content

Types of Circular Linked Lists

There are primarily two types of circular linked lists, as described below.

1. Circular Singly Linked List

 In a circular, singly linked list, each node contains two components, which are data and a pointer to the next node. The key characteristic here is that the last node in the list points back to the first node, creating a circular structure. This type of list doesn't provide direct access to the previous nodes, as there's only a single link to the next node.

2. Circular Doubly Linked List

In a circular doubly linked list, each node contains three components which are data, a pointer to the next node, and a pointer to the previous node. This structure allows for a more flexible traversal of the list, as you can move both forward and backward. Similar to the circular singly linked list, the last node points to the first node (forward link), and the first node points back to the last node (backward link), forming a circular structure.

Note: For the remainder of this article, we will refer to a circular singly liked list as a circular linked list.

 

Implementing a Circular Linked List

A simple node in Python can be represented as below.


 
class Node:
def __init__(self, data):
self.data = data
self.next = None
Copy code

Here, the Node class objects have two properties, namely data and next, that hold the actual information and the address to the next node in the linked list, respectively.

Now, let’s implement a circular linked list with a couple of nodes and explore its inner workings.


 
# Node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
# circular linked list class
class CircularLinkedList:
def __init__(self):
# Initialize an
# empty linked list
self.head = None
# method to insert nodes
# into the linked list
def insert(self, data):
# Create a new node
# with the some data
new_node = Node(data)
# If the list is empty,
# make the new node the
# head and point it to itself
if not self.head:
self.head = new_node
self.head.next = self.head
else:
temp = self.head
# Traverse the list to
# find the last node
while temp.next != self.head:
temp = temp.next
# Make the last node
# point to the new node
temp.next = new_node
# Make the new node point
# back to the head,
# making it circular
new_node.next = self.head
# method to display
# the circular linked list
def display(self):
# If the list is empty,
# print a message
if not self.head:
print("Empty list")
else:
temp = self.head
# Traverse and print the circular
# linked list until we reach
# the head again
while True:
print(temp.data, end=" => ")
temp = temp.next
# Break the loop when
# we reach the head again
if temp == self.head:
break
# Print a new line for
# better formatting
print()
# Creating a circular linked list and inserting nodes
circular_list = CircularLinkedList()
circular_list.insert(10)
circular_list.insert(20)
circular_list.insert(30)
# Displaying the circular linked list
circular_list.display()
Copy code

Output

10 => 20 => 30 => 

In the above implemented circular linked list, the data and addresses are stored as:

  1. 1st Node -> Data = 10, Addresses = 2nd Node
  2. 2nd Node -> Data =20, Address = 3rd Node
  3. 3rd Node -> Data =30, Address = 1st Node

Operations on Circular Linked List

Now that we have familiarised ourselves with the basic structure of a circular linked list. Let’s look at the operations we can perform in a circular linked List.

Insertion of Node in Circular Linked List

We can insert a node in a linked list at the following positions.

  1. Insert Node at the start
  2. Insert Node at the End
  3. Insert Node in-between existing Nodes

Let’s take a look at each one of them in detail.

Insert Node at the Start of Circular Linked List

Algorithm

Step 1: Create a new node with the given data.

Step 2: If the circular linked list is empty (head is None):

  • Set the new node as the head.
  • Make the new node point to itself: new_node.next = new_node

Step 3: Else (circular linked list is not empty):

  • Find the last node in the circular linked list.
  • Set the new node as the new head:
  1. Set new_node.next = head.next
  2.  Update the head pointer: head = new_node
  • Make the last node point to the new head to maintain the circular structure:
  1.  Traverse the list to find the last node.
  2. Set the last_node.next = head

Step 4: Done.

Insert Node at the End of Circular Linked List

Algorithm

Step 1: Create a new node with the given data.

Step 2: If the circular linked list is empty (head is None):

  • Set the new node as the head.
  • Make the new node point to itself: new_node.next = new_node

Step 3: Else (circular linked list is not empty):

  • Find the last node in the circular linked list.
  •  Make the last node point to the new node: last_node.next = new_node
  • Make the new node point back to the head to maintain the circular structure: new_node.next = head

Step 4:  Update the head pointer (if needed) to point to the new node.

Step 5: Done.

Insert Node In-between Existing Nodes of Circular Linked List

Algorithm

Step 1: Create a new node with the given data.

Step 2: If the circular linked list is empty (head is None):

  • Set the new node as the head.
  • Make the new node point to itself: new_node.next = new_node

Step 3: Else (circular linked list is not empty):

  •  Find the node after which the new node will be inserted (position_node).
  • Set the new node's next pointer to the next node of position_node: new_node.next = position_node.next
  • Make position_node point to the new node: position_node.next = new_node

Step 4:  Update the head pointer (if needed) to point to the new node.

Step 5: Done.

Deletion of Node in Circular Linked List

We can delete a node(s) in a circular linked list at the following positions:

  1. Delete Node at the start
  2. Delete Node at the End 
  3. Delete Node in-between existing Nodes

Let’s take a look at each one of them in detail.

Delete Node at the Start of Circular Linked List

Algorithm

Step 1: If the circular linked list is empty (head is None), return empty list.

Step 2:  If there is only one node in the list:

  • Set head to None.

Step 3: Else (more than one node in the list):

  • Find the last node in the circular linked list: last_node
  • Set head.next as the new head: head = head.next
  • Make last_node point to the new head to maintain circular structure: last_node.next = head

Step 4: Done.

Delete Node at the End of Circular Linked List

Algorithm

Step 1: If the circular linked list is empty (head is None), return empty list.

Step 2: If there is only one node in the list:

  • Set head to None.

Step 3: Else (more than one node in the list):

  • Find the second last node in the circular linked list: second_last_node
  • Set second_last_node.next as the new head: second_last_node.next = head

Step 4: Done.

Delete Node In-between Existing Nodes of Circular Linked List

Algorithm

Step 1: If the circular linked list is empty (head is None), return empty list.

Step 2: If there is only one node in the list:

  • Set head to None.

Step 3: Else (more than one node in the list):

  • Find the node after which the node needs to be deleted (position_node).
  • Set the node to be deleted as delete_node: delete_node = position_node.next
  •  Update position_node.next to skip the delete_node: position_node.next = delete_node.next
  • Delete the node by removing its reference: delete_node = None

Step 4: Done.

 

Programs to Insert Nodes in a Circular Linked List

The programs below depict the implementation of functions to perform insertion at the start, end, and in between the nodes of a circular linked list.

Python program to Insert Nodes in a circular Linked List


 
# Node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Circular linked list class
class CircularLinkedList:
def __init__(self):
self.head = None
# Method to insert node at the start of a circular linked list
def insert_start(self, data):
new_node = Node(data)
new_node.next = new_node # New node points to itself initially
if not self.head:
self.head = new_node
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
new_node.next = self.head # New node points to previous head
self.head = new_node # Update the head to the new node
temp.next = new_node # Make last node point to the new node
# Method to insert node at the end of circular linked list
def insert_end(self, data):
new_node = Node(data)
new_node.next = new_node # New node points to itself initially
if not self.head:
self.head = new_node
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node # Make last node point to the new node
new_node.next = self.head # New node points back to the head
# Method to insert nodes in-between existing nodes in a circular linked list
def insert_between(self, data, position_data):
new_node = Node(data)
new_node.next = new_node # New node points to itself initially
if not self.head:
self.head = new_node
else:
temp = self.head
while temp.data != position_data:
temp = temp.next
if temp.next == self.head and temp.data != position_data:
print("Node with data", position_data, "not found")
return
new_node.next = temp.next # Set new node's next to the next of position_node
temp.next = new_node # Set position_node's next to new_node
# Method to display the circular linked list
def display(self):
if not self.head:
print("Empty list")
else:
temp = self.head
while True:
print(temp.data, end=" -> ")
temp = temp.next
if temp == self.head:
break
print()
# Circular linked list object
circular_list = CircularLinkedList()
# Insert at the start
circular_list.insert_start(30)
circular_list.display()
# Insert at the end
circular_list.insert_end(40)
circular_list.display()
# Insert in-between existing nodes
circular_list.insert_between(35, 30)
circular_list.display()
Copy code

Output

30 -> 
30 -> 40 -> 
30 -> 35 -> 40 -> 

C++ program to Insert Nodes in a circular Linked List


 
#include <iostream>
// Node class
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// Circular linked list class
class CircularLinkedList {
private:
Node* head;
public:
CircularLinkedList() {
head = nullptr;
}
// Method to insert node at the start of the circular linked list
void insert_start(int data) {
Node* new_node = new Node(data);
// If list is empty, new node becomes the head
if (head == nullptr) {
head = new_node;
head->next = head;
} else {
Node* temp = head;
// Find the last node
while (temp->next != head) {
temp = temp->next;
}
// Make last node point to the new node
temp->next = new_node;
// New node becomes the head, pointing to previous head
new_node->next = head;
// Update the head to the new node
head = new_node;
}
}
// Method to insert node at the end of the circular linked list
void insert_end(int data) {
Node* new_node = new Node(data);
// If list is empty, new node becomes the head
if (head == nullptr) {
head = new_node;
head->next = head;
} else {
Node* temp = head;
// Find the last node
while (temp->next != head) {
temp = temp->next;
}
// Make last node point to the new node
temp->next = new_node;
// New node points back to the head
new_node->next = head;
}
}
// Method to insert node in-between existing nodes of the circular linked list
void insert_between(int data, int position_data) {
Node* new_node = new Node(data);
// If list is empty, new node becomes the head
if (head == nullptr) {
head = new_node;
head->next = head;
} else {
Node* temp = head;
// Find the node after which to insert
while (temp->data != position_data) {
temp = temp->next;
// If position_data not found
if (temp->next == head && temp->data != position_data) {
std::cout << "Node with data " << position_data << " not found" << std::endl;
return;
}
}
// Set new node's next to the next of position_node
new_node->next = temp->next;
// Set position_node's next to new_node
temp->next = new_node;
}
}
// Method to display the circular linked list
void display() {
if (head == nullptr) {
std::cout << "Empty list" << std::endl;
} else {
Node* temp = head;
do {
std::cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
std::cout << std::endl;
}
}
};
int main() {
CircularLinkedList circular_list;
// Insert at the start
circular_list.insert_start(30);
circular_list.display();
// Insert at the end
circular_list.insert_end(40);
circular_list.display();
// Insert in-between existing nodes
circular_list.insert_between(35, 30);
circular_list.display();
return 0;
}
Copy code

Output

30 -> 
30 -> 40 -> 
30 -> 35 -> 40 -> 

Java program to Insert Nodes in a circular Linked List


 
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
private Node head;
public CircularLinkedList() {
head = null;
}
public void insert_start(int data) {
Node new_node = new Node(data);
if (head == null) {
head = new_node;
head.next = head;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = new_node;
new_node.next = head;
head = new_node;
}
}
public void insert_end(int data) {
Node new_node = new Node(data);
if (head == null) {
head = new_node;
head.next = head;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = new_node;
new_node.next = head;
}
}
public void insert_between(int data, int position_data) {
Node new_node = new Node(data);
if (head == null) {
head = new_node;
head.next = head;
} else {
Node temp = head;
while (temp.data != position_data) {
temp = temp.next;
if (temp.next == head && temp.data != position_data) {
System.out.println("Node with data " + position_data + " not found");
return;
}
}
new_node.next = temp.next;
temp.next = new_node;
}
}
public void display() {
if (head == null) {
System.out.println("Empty list");
} else {
Node temp = head;
do {
System.out.print(temp.data + " -> ");
temp = temp.next;
} while (temp != head);
System.out.println();
}
}
public static void main(String[] args) {
CircularLinkedList circular_list = new CircularLinkedList();
circular_list.insert_start(30);
circular_list.display();
circular_list.insert_end(40);
circular_list.display();
circular_list.insert_between(35, 30);
circular_list.display();
}
}
Copy code

Output

30 -> 
30 -> 40 -> 
30 -> 35 -> 40 -> 

Programs to Delete Node in a Circular Linked List

The programs below depict the implementation of functions to perform deletion of the Nodes at the start, end, and in-between of a circular linked list.

Python program to Delete Nodes in a circular Linked List


 
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def insert_start(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
new_node.next = self.head
self.head = new_node
def delete_start(self):
if not self.head:
print("Empty list, deletion not possible")
return
elif self.head.next == self.head:
self.head = None
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = self.head.next
self.head = self.head.next
def delete_end(self):
if not self.head:
print("Empty list, deletion not possible")
return
elif self.head.next == self.head:
self.head = None
else:
temp = self.head
prev = None
while temp.next != self.head:
prev = temp
temp = temp.next
prev.next = self.head
temp = None
def delete_between(self, position_data):
if not self.head:
print("Empty list, deletion not possible")
return
elif self.head.next == self.head:
if self.head.data == position_data:
self.head = None
else:
print("Node with data", position_data, "not found")
else:
temp = self.head
prev = None
while temp.data != position_data:
prev = temp
temp = temp.next
if temp == self.head:
print("Node with data", position_data, "not found")
return
if temp == self.head:
self.head = self.head.next
prev.next = temp.next
temp = None
def display(self):
if not self.head:
print("Empty list")
else:
temp = self.head
while True:
print(temp.data, end=" -> ")
temp = temp.next
if temp == self.head:
break
print()
# Circular linked list object
circular_list = CircularLinkedList()
# Inserting nodes
circular_list.insert_start(40)
circular_list.insert_start(30)
circular_list.insert_start(20)
circular_list.insert_start(10)
circular_list.display()
# Deleting nodes at start
circular_list.delete_start()
circular_list.display()
# Deleting nodes at end
circular_list.delete_end()
circular_list.display()
# Deleting nodes in between
circular_list.delete_between(30)
circular_list.display()
Copy code

Output

10 -> 20 -> 30 -> 40 -> 
20 -> 30 -> 40 -> 
20 -> 30 -> 
20 -> 

C++ program to Delete Nodes in a circular Linked List


 
#include <iostream>
// Node class
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// Circular linked list class
class CircularLinkedList {
private:
Node* head;
public:
CircularLinkedList() {
head = nullptr;
}
void insert_start(int data) {
Node* new_node = new Node(data);
if (!head) {
head = new_node;
new_node->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = new_node;
new_node->next = head;
head = new_node;
}
}
void delete_start() {
if (!head) {
std::cout << "Empty list, deletion not possible" << std::endl;
return;
} else if (head->next == head) {
delete head; // Free memory
head = nullptr;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = head->next;
delete head; // Free memory
head = temp->next;
}
}
void delete_end() {
if (!head) {
std::cout << "Empty list, deletion not possible" << std::endl;
return;
} else if (head->next == head) {
delete head; // Free memory
head = nullptr;
} else {
Node* temp = head;
Node* prev = nullptr;
while (temp->next != head) {
prev = temp;
temp = temp->next;
}
prev->next = head;
delete temp; // Free memory
}
}
void delete_between(int position_data) {
if (!head) {
std::cout << "Empty list, deletion not possible" << std::endl;
return;
} else if (head->next == head) {
if (head->data == position_data) {
delete head; // Free memory
head = nullptr;
return;
} else {
std::cout << "Node with data " << position_data << " not found" << std::endl;
return;
}
} else {
Node* temp = head;
Node* prev = nullptr;
do {
if (temp->data == position_data) {
if (prev) {
prev->next = temp->next;
}
if (temp == head) {
head = temp->next;
}
delete temp; // Free memory
return;
}
prev = temp;
temp = temp->next;
} while (temp != head);
std::cout << "Node with data " << position_data << " not found" << std::endl;
}
}
void display() {
if (!head) {
std::cout << "Empty list" << std::endl;
} else {
Node* temp = head;
do {
std::cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
std::cout << std::endl;
}
}
};
int main() {
CircularLinkedList circular_list;
// Inserting nodes
circular_list.insert_start(40);
circular_list.insert_start(30);
circular_list.insert_start(20);
circular_list.insert_start(10);
circular_list.display();
// Deleting node at start
circular_list.delete_start();
circular_list.display();
// Deleting node at end
circular_list.delete_end();
circular_list.display();
// Deleting node in-between nodes
circular_list.delete_between(30);
circular_list.display();
return 0;
}
Copy code

Output

10 -> 20 -> 30 -> 40 -> 
20 -> 30 -> 40 -> 
20 -> 30 -> 
20 -> 

Java program to Delete Nodes in a circular Linked List


 
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
private Node head;
public CircularLinkedList() {
head = null;
}
public void insert_start(int data) {
Node new_node = new Node(data);
if (head == null) {
head = new_node;
new_node.next = head;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = new_node;
new_node.next = head;
head = new_node;
}
}
public void delete_start() {
if (head == null) {
System.out.println("Empty list, deletion not possible");
return;
} else if (head.next == head) {
head = null;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = head.next;
head = head.next;
}
}
public void delete_end() {
if (head == null) {
System.out.println("Empty list, deletion not possible");
return;
} else if (head.next == head) {
head = null;
} else {
Node temp = head;
Node prev = null;
while (temp.next != head) {
prev = temp;
temp = temp.next;
}
prev.next = head;
}
}
public void delete_between(int position_data) {
if (head == null) {
System.out.println("Empty list, deletion not possible");
return;
} else if (head.next == head) {
if (head.data == position_data) {
head = null;
return;
} else {
System.out.println("Node with data " + position_data + " not found");
return;
}
} else {
Node temp = head;
Node prev = null;
while (temp.data != position_data) {
prev = temp;
temp = temp.next;
if (temp == head) {
System.out.println("Node with data " + position_data + " not found");
return;
}
}
if (temp == head) { // if the node to delete is the head
head = head.next;
}
prev.next = temp.next;
}
}
public void display() {
if (head == null) {
System.out.println("Empty list");
} else {
Node temp = head;
do {
System.out.print(temp.data + " -> ");
temp = temp.next;
} while (temp != head);
System.out.println();
}
}
public static void main(String[] args) {
CircularLinkedList circular_list = new CircularLinkedList();
circular_list.insert_start(40);
circular_list.insert_start(30);
circular_list.insert_start(20);
circular_list.insert_start(10);
circular_list.display();
circular_list.delete_start();
circular_list.display();
circular_list.delete_end();
circular_list.display();
circular_list.delete_between(30);
circular_list.display();
}
}
Copy code

Output

10 -> 20 -> 30 -> 40 -> 
20 -> 30 -> 40 -> 
20 -> 30 -> 
20 -> 

Applications of Circular Linked List

The below consists of a list of applications of circular linked list:

  1. Manage System Resources: Operating systems use circular linked lists to manage system resources such as memory allocation and CPU scheduling queues and maintain a list of available blocks.
  2. Music Player Design: A playlist in a music player with tracks arranged in a circle such that the last song always loops back to the beginning can be represented by circular linked lists.
  3. Game development: To maintain fairness and sequential play, games employ circular linked lists to arrange player turns cyclically.
  4. Data Buffers:  In networking and hardware devices, circular linked lists are used as buffers for storing incoming/outgoing data packets in a cyclic manner.
  5. Cache Management: Caches in computer systems often use circular linked lists to manage recently used or least recently used data blocks.

What are the Application Of Linked List
What are the Application Of Linked List
Have you ever wondered about the versatile applications of linked lists? These dynamic data structures are pivotal in creating efficient algorithms and complex data management systems, excelling in tasks requiring...read more

Practice Problems of Linked List
Practice Problems of Linked List
LinkedList is a linear data structure and part of the collection framework similar to the ArrayList used to store and manipulate the data points. In this article, we will discuss...read more

Singly Linked Lists
Singly Linked Lists
There are three types of Linked Lists used daily by Engineers, and the most popular of the lot is the Singly Linked Lists. Singly Linked Lists traverse in a single...read more

Linked List Examples in C and Python
Linked List Examples in C and Python
In the previous articles, you have gone through Linked List and their types. In this article, let us discuss the Top 25 operations of Linked Lists and their examples in...read more

Difference Between Array and Linked List
Difference Between Array and Linked List
“Ever wondered why we use arrays in some situations and linked lists in others? Both are ways to store data, but they’re quite different. In this article, we’ll break down...read more

Everything You Need to Know About Doubly Linked List
Everything You Need to Know About Doubly Linked List
Have you ever wondered how applications manage data that needs to be traversed both forwards and backwards with equal ease? A doubly linked list is a data structure that makes...read more

Conclusion

In this article, we have managed to cover the following concepts associated with circular linked lists:

  • Overview of Circular Linked List
  • Types of Circular Linked Lists
  • Inserting Nodes to a circular Linked List
  • Deleting Nodes from a Circular Linked List
  • Implementation of Insertion/Deletion of Nodes from Circular Linked List
  • Applications of Circular Linked List

Article Contributed by: Raju Kumar

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio

Comments