Circular Linked Lists are data structures that are used to store lists. It is very similar to linked lists but with a few extra features. In this tutorial, we will discuss what a circular linked list is, we will implement it in python and see its output.
Pre-Requisite: Understanding of Linked List
We must first define linked lists before moving on to circular linked lists.
A linked list is a list in which the list items are linked to other list items in a specific way. Different forms of linked lists have different ways of linking objects.
The “singly linked list” or simply “linked list” is the most popular linked list, in which each item links to the next item in the list. So, in order to get to the tenth item, we must first get to the ninth item, which is linked to the tenth item. And once we’ve accessed the tenth item, we’ll be able to access the eleventh item through the tenth item’s connection.
A node is a name given to each object in a linked list. Each node in a singly linked list has two components. The first part contains the node’s data, while the second contains the link to the next node.
Let’s take a look at circular linked lists now.
Circular Linked Lists in Python
A circular linked list is similar to a linked list in that the nodes are connected by links, but the last node is also linked to the first node instead of just linking to nothing. So, after we’ve accessed the last node, we can access the first node through the last node.
The way to do this is just instead of keeping the link of the last node as None, make it point to the first node instead.
The benefit of doing this is that it makes it easier to implement algorithms that have a list of items that come in a circular manner. For example, the round-robin scheduling algorithm, or the player turns in a multiplayer game are circular in nature.
To visualize, a circular linked list looks something like this:
In the above example, you can see that there are four nodes in the list. Each node has some data, and each node links to the next node of the list except the last node which links to the first node of the list.
There’s a head that points to the start of the list which is used to enter the list and iterate through the circular linked list.
Recommended read – Doubly linked lists
Implementing Circular Linked Lists in Python
To create a circular linked list, we create two classes: the first one for nodes and the second one for the linked list that will use the nodes.
Class: Node
For the node class, we have two members. One to store data and the other to store the link to the next node. The class definition will be:
class Node:
def __init__(self, data = None):
self.data = data
self.next = self
So, initially, every new node created will either have or won’t have a data value depending on how it was created, but it will point to itself by default so that it’s like a single item circular linked list.
Class: Circular Linked List
This class will use nodes created by the previous class to implement a circular linked list. It will contain one head node, one count member, and multiple methods for specific tasks.
class CLL:
def __init__(self):
self.head = None
self.count = 0
def __repr__(self):
string = ""
if(self.head == None):
string += "Circular Linked List Empty"
return string
string += f"Circular Linked List:\n{self.head.data}"
temp = self.head.next
while(temp != self.head):
string += f" -> {temp.data}"
temp = temp.next
return string
def append(self, data):
self.insert(data, self.count)
return
def insert(self, data, index):
if (index > self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if self.head == None:
self.head = Node(data)
self.count += 1
return
temp = self.head
for _ in range(self.count - 1 if index - 1 == -1 else index - 1):
temp = temp.next
aftertemp = temp.next #New node goes between temp and aftertemp
temp.next = Node(data)
temp.next.next = aftertemp
if(index == 0):
self.head = temp.next
self.count += 1
return
def remove(self, index):
if (index >= self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if self.count == 1:
self.head = None
self.count = 0
return
before = self.head
for _ in range(self.count - 1 if index - 1 == -1 else index - 1):
before = before.next
after = before.next.next
before.next = after
if(index == 0):
self.head = after
self.count -= 1
return
def index(self, data):
temp = self.head
for i in range(self.count):
if(temp.data == data):
return i
temp = temp.next
return None
def size(self):
return self.count
def display(self):
print(self)
Let us discuss the methods written above.
The __init__ method
In the constructor, we are initializing two members, we are setting the head as None because there are no nodes in the list, and we are setting the count as 0 for the same reason.
The __repr__ method
The string that will print the linked list will be returned by the __repr__ process. So either the list is empty, in which case we print that, or the list isn’t empty, in which case we print each node’s data one by one.
The append and insert method
Nodes can either be appended or inserted at a specified position in this implementation. To append, we simply call the insert method and send the size of the list as the index.
In the insert method, we first check if the specified index is valid or not, if not, we throw a ValueError. After passing the check, if the list is empty, we simply assign the new node to the head, increment the count, and return from the method.
If the list isn’t empty, we first reach the node before the specified index. For example, if the given index is 5, then we reach the node at the 4th index, and because the list is circular, if the given index is 0, then we reach the last node of the list.
Now, we assign the new node to the next of the node before the specified index, and we make the new node’s next link to the node at the specified index. This will make sure that the new node is inserted before the node that was at the specified index, and hence taken its index and pushed it ahead.
Now, if the given index was 0, we have inserted a node after the last node of the list, so we simply make the head point to the new node making it the new head of the list.
The remove method
To remove an item we must specify where the item is to be removed from. If the specified index is out of range, we raise a ValueError. If there’s only one item on the list, we simply make the head None and the count 0, and return from the method.
Otherwise, we have to reach the node before the specified index and the node after the specified index. For example, if the specified index is 4 then we need to reach the 3rd node and the 5th node, and because the list is circular if the specified index is 0, we need to reach the last node (before it) and the 1st node (after it).
After this, we simply assign the node after the specified index to the next of the node before the specified index. This will skip the node at the specified index, hence removing it from the list. If the specified index is 0, then the head has been removed from the list, so we simply have to assign the node that was after the specified index to the head and the list will be restored. Don’t forget to decrement the count of the list.
The index, size and display method
The index method searches for an item in the list. If found, it returns its index, otherwise, it returns None. The size method returns the number of nodes in the list, and the display method prints the list.
The Output
Conclusion
We learned about Circular Linked Lists and how to use them in Python. We began by looking at how a singly linked list works, then moved on to how a circular linked list differs. We wrote the data structure code in Python, discussed how each method works, and then looked at the results of the code.
I hope you had a great time learning, and see you in the next tutorial.