All About Circular Linked Lists
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.
Read LaterBest-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
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
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()
Output
10 => 20 => 30 =>
In the above implemented circular linked list, the data and addresses are stored as:
- 1st Node -> Data = 10, Addresses = 2nd Node
- 2nd Node -> Data =20, Address = 3rd Node
- 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.
- Insert Node at the start
- Insert Node at the End
- 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:
- Set new_node.next = head.next
- Update the head pointer: head = new_node
- Make the last node point to the new head to maintain the circular structure:
- Traverse the list to find the last node.
- 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:
- Delete Node at the start
- Delete Node at the End
- 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 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()
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;}
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(); }}
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()
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;}
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(); }}
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:
- 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.
- 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.
- Game development: To maintain fairness and sequential play, games employ circular linked lists to arrange player turns cyclically.
- Data Buffers: In networking and hardware devices, circular linked lists are used as buffers for storing incoming/outgoing data packets in a cyclic manner.
- Cache Management: Caches in computer systems often use circular linked lists to manage recently used or least recently used data blocks.
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
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
Top Picks & New Arrivals
