A circular linked list is a data structure where the last node connects back to the first, forming a loop. This structure allows for continuous traversal without any interruptions. Circular linked lists are especially helpful for tasks like scheduling and managing playlists, this allowing for smooth navigation. In this tutorial, we’ll cover the basics of circular linked lists, how to work with them, their advantages and disadvantages, and their applications.
A circular linked list is a special type of linked list where all the nodes are connected to form a circle. Unlike a regular linked list, which ends with a node pointing to NULL , the last node in a circular linked list points back to the first node. This means that you can keep traversing the list without ever reaching a NULL value.
We can create a circular linked list from both singly linked lists and doubly linked lists . So, circular linked list are basically of two types:
In Circular Singly Linked List , each node has just one pointer called the “ next ” pointer. The next pointer of last node points back to the first node and this results in forming a circle. In this type of Linked list we can only move through the list in one direction.
Representation of Circular Singly Linked List
In circular doubly linked list, each node has two pointers prev and next, similar to doubly linked list. The prev pointer points to the previous node and the next points to the next node. Here, in addition to the last node storing the address of the first node, the first node will also store the address of the last node .
Representation of Circular Doubly Linked List
Note: In this article, we will use the circular singly linked list to explain the working of circular linked lists.
Let’s take a look on the structure of a circular linked list.
Representation of a Circular Singly Linked List
Syntax to Declare a Circular Linked List in Different Languages:
Java
JavaScript
In the code above, each node has data and a pointer to the next node. When we create multiple nodes for a circular linked list, we only need to connect the last node back to the first one.
Example of Creating a Circular Linked List
Here’s an example of creating a circular linked list with three nodes (2, 3, 4):
Created a circular linked list with 3 nodes
Java
Python
JavaScript
In the above code, we have created three nodes first, second, and last having values 2, 3, and 4 respectively.
- After creating three nodes, we have connected these node in a series.
- Connect the first node “ first” to “ second” node by s toring the address of “ second” node into first’s next
- Connect the second node “ second” to “ second” node by s toring the address of “ third ” node into second’s next
- After connecting all the nodes, we reach the key characteristic of a circular linked list: linking the last node back to the first node . Therefore, we store the address of the “ first ” node in the “ last ” node.
Why have we taken a pointer that points to the last node instead of the first node?
For the insertion of a node at the beginning, we need to traverse the whole list. Also, for insertion at the end, the whole list has to be traversed. If instead of the start pointer, we take a pointer to the last node, then in both cases there won’t be any need to traverse the whole list. So insertion at the beginning or at the end takes constant time, irrespective of the length of the list.
Operations on the Circular Linked list:
We can do some operations on the circular linked list similar to the singly and doubly linked list which are:
- Insertion
- Insertion at the empty list
- Insertion at the beginning
- Insertion at the end
- Insertion at the given position
- Delete the first node
- Delete the last node
- Delete the node from any position
Note: We will be using the circular singly linked list to represent the working of the circular linked list.
Insertion in the circular linked list:
Insertion is a fundamental operation in linked lists that involves adding a new node to the list. The only extra step is connecting the last node to the first one. In the circular linked list mentioned below, we can insert nodes in four ways:
1. Insertion in an empty List in the circular linked list
To insert a node in empty circular linked list, creates a new node with the given data, sets its next pointer to point to itself, and updates the last pointer to reference this new node .
Insertion in an empty List
<span after insertion: " Java
<span after insertion: " Python
<span after insertion: " JavaScript
Output
List after insertion: 1
2. Insertion at the beginning in circular linked list
To insert a new node at the beginning of a circular linked list, we first create the new node and allocate memory for it. If the list is empty (indicated by the last pointer being NULL ), we make the new node point to itself. If the list already contains nodes then we set the new node’s next pointer to point to the current head of the list (which is last->next ), and then update the last node’s next pointer to point to the new node . This maintains the circular structure of the list.
Insertion at the beginning in circular linked list
Java
Python
JavaScript
Output
Original list: 2 3 4 List after inserting 5 at the beginning: 5 2 3 4
3. Insertion at the end in circular linked list
To insert a new node at the end of a circular linked list, we first create the new node and allocate memory for it. If the list is empty (mean, last or tail pointer being NULL ), we initialize the list with the new node and making it point to itself to form a circular structure. If the list already contains nodes then we set the new node’s next pointer to point to the current head (which is tail->next ), then update the current tail’s next pointer to point to the new node . Finally, we update the tail pointer to the new node. This will ensure that the new node is now the last node in the list while maintaining the circular linkage.
Insertion at the end in circular linked list
Java
Python
JavaScript
Output
Original list: 2 3 4 List after inserting 5 and 6: 2 3 4 5 6
4. Insertion at specific position in circular linked list
To insert a new node at a specific position in a circular linked list, we first check if the list is empty. If it is and the position is not 1 then we print an error message because the position doesn’t exist in the list. If the position is 1 then we create the new node and make it point to itself. If the list is not empty, we create the new node and traverse the list to find the correct insertion point. If the position is 1 , we insert the new node at the beginning by adjusting the pointers accordingly. For other positions, we traverse through the list until we reach the desired position and inserting the new node by updating the pointers. If the new node is inserted at the end, we also update the last pointer to reference the new node, maintaining the circular structure of the list.
Insertion at specific position in circular linked list
if the new node is inserted at the end <span after insertions: " Java
if the new node is inserted at the <span after insertions: " Python
if the new node is inserted at the end span after insertions: " JavaScript
Output
Original list: 2 3 4 List after insertions: 2 5 3 4
Deletion from a Circular Linked List
Deletion involves removing a node from the linked list. The main difference is that we need to ensure the list remains circular after the deletion. We can delete a node in a circular linked list in three ways:
1. Delete the first node in circular linked list
To delete the first node of a circular linked list, we first check if the list is empty. If it is then we print a message and return NULL . If the list contains only one node (the head is the same as the last ) then we delete that node and set the last pointer to NULL . If there are multiple nodes then we update the last->next pointer to skip the head node and effectively removing it from the list. We then delete the head node to free the allocated memory. Finally, we return the updated last pointer, which still points to the last node in the list.
Delete the first node in circular linked list
Java
Python
JavaScript
Output
Original list: 2 3 4 List after deleting first node: 3 4
2. Delete a specific node in circular linked list
To delete a specific node from a circular linked list, we first check if the list is empty. If it is then we print a message and return nullptr . If the list contains only one node and it matches the key then we delete that node and set last to nullptr . If the node to be deleted is the first node then we update the next pointer of the last node to skip the head node and delete the head . For other nodes, we traverse the list using two pointers: curr (to find the node) and prev (to keep track of the previous node). If we find the node with the matching key then we update the next pointer of prev to skip the curr node and delete it. If the node is found and it is the last node, we update the last pointer accordingly. If the node is not found then do nothing and tail or last as it is. Finally, we return the updated last pointer.
Delete a specific node in circular linked list
Java
Python
JavaScript
Output
Original list: 2 3 4 List after deleting node 3: 2 4
3. Deletion at the end of Circular linked list
To delete the last node in a circular linked list, we first check if the list is empty. If it is, we print a message and return nullptr . If the list contains only one node (where the head is the same as the last ), we delete that node and set last to nullptr . For lists with multiple nodes, we need to traverse the list to find the second last node . We do this by starting from the head and moving through the list until we reach the node whose next pointer points to last . Once we find the second last node then we update its next pointer to point back to the head, this effectively removing the last node from the list. We then delete the last node to free up memory and return the updated last pointer, which now points to the last node.
Deletion at the end of Circular linked list
Java
Python
JavaScript
Output
Original list: 2 3 4 List after deleting last node: 2 3
Searching in Circular Linked list
Searching in a circular linked list is similar to searching in a regular linked list. We start at a given node and traverse the list until you either find the target value or return to the starting node. Since the list is circular, make sure to keep track of where you started to avoid an infinite loop.
To search for a specific value in a circular linked list, we first check if the list is empty. If it is then we return false . If the list contains nodes then we start from the head node (which is the last->next ) and traverse the list. We use a pointer curr to iterate through the nodes until we reach back to the head . During traversal, if we find a node whose data matches the given key then we return true to indicating that the value was found. After the loop, we also check the last node to ensure we don’t miss it. If the key is not found after traversing the entire list then we return false .
Java
Python
JavaScript
Output
Original list: 2 3 4 Value 3 found in the list.
Advantages of Circular Linked Lists
- In circular linked list, the last node points to the first node. There are no null references, making traversal easier and reducing the chances of encountering null pointer exceptions.
- We can traverse the list from any node and return to it without needing to restart from the head, which is useful in applications requiring a circular iteration.
- Circular linked lists can easily implement circular queues, where the last element connects back to the first, allowing for efficient resource management.
- In a circular linked list, each node has a reference to the next node in the sequence. Although it doesn’t have a direct reference to the previous node like a doubly linked list, we can still find the previous node by traversing the list.
Disadvantages of Circular Linked Lists
- Circular linked lists are more complex to implement than singly linked lists.
- Traversing a circular linked list without a clear stopping condition can lead to infinite loops if not handled carefully.
- Debugging can be more challenging due to the circular nature, as traditional methods of traversing linked lists may not apply.
Applications of Circular Linked Lists
- It is used for time-sharing among different users, typically through a Round-Robin scheduling mechanism.
- In multiplayer games, a circular linked list can be used to switch between players. After the last player’s turn, the list cycles back to the first player.
- Circular linked lists are often used in buffering applications, such as streaming data, where data is continuously produced and consumed.
- In media players, circular linked lists can manage playlists, this allowing users to loop through songs continuously.
- Browsers use circular linked lists to manage the cache. This allows you to navigate back through your browsing history efficiently by pressing the BACK button.
Related Article:
- Circular Linked List meaning in DSA
- Singly Linked List Tutorial
- Doubly Linked List Tutorial
