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++
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

## 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 = NoneCopy 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 classclass Node: def __init__(self, data): self.data = data self.next = None # circular linked list classclass 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 nodescircular_list = CircularLinkedList()circular_list.insert(10)circular_list.insert(20)circular_list.insert(30) # Displaying the circular linked listcircular_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:
• 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:

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

• Find the last node in the circular linked list: last_node
• 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:

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

• Find the second last node in the circular linked list: second_last_node

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:

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 classclass Node: def __init__(self, data): self.data = data self.next = None # Circular linked list classclass 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 objectcircular_list = CircularLinkedList() # Insert at the startcircular_list.insert_start(30)circular_list.display() # Insert at the endcircular_list.insert_end(40)circular_list.display() # Insert in-between existing nodescircular_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 classclass Node {public: int data; Node* next; Node(int data) { this->data = data; this->next = nullptr; }}; // Circular linked list classclass 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 objectcircular_list = CircularLinkedList() # Inserting nodescircular_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 startcircular_list.delete_start()circular_list.display() # Deleting nodes at endcircular_list.delete_end()circular_list.display() # Deleting nodes in betweencircular_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 classclass Node {public: int data; Node* next; Node(int data) { this->data = data; this->next = nullptr; }}; // Circular linked list classclass 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
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

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

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
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
“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

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

• 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