Exploring the Circular Singly Linked List in Python
Exploring the Circular Singly Linked List in Python
If you’re new to data structures, the concept of a circular singly linked list might sound like a mouthful. But don’t worry! In this guide, we’ll break down everything you need to know about this fascinating structure, using simple language and clear examples. By the end, you’ll understand how to implement and manipulate these lists in Python.
What is a Circular Singly Linked List?
A circular singly linked list is a variation of the linked list in which the last item points back to the first item. This creates a circular structure that allows us to loop through the list indefinitely, which can be very handy in applications where the end of the list naturally connects back to the beginning (like in a round-robin scheduler).
Each element in the list is called a node, and it contains:
Value: The data stored in the node.
Next: A reference (or pointer) to the next node in the list.
Breaking Down the Implementation
Let’s dive into the Python implementation and explore each part of our circular singly linked list class, named CSLinkedList.
1. The Node Class
First things first: we need a way to store data and the link to the next node. That’s where our Node class comes in:
class Node:
def __init__(self, value):
self.value = value # Data part of the node.
self.next = None # Pointer to the next node; initially None.
def __str__(self):
return str(self.value) # Helps to print the node's value easily.2. The CSLinkedList ClassNow, let’s build our linked list class that uses these nodes:
class CSLinkedList:
def __init__(self):
self.head = None # Start of the list.
self.tail = None # End of the list.
self.length = 0 # How many items are in the list.Initialization
The __init__ method sets up an empty list. Initially, there are no nodes, so both the head and tail are set to None, and the length is zero.
String Representation
To make our list human-readable:
def __str__(self):
result = ''
temp_node = self.head
while temp_node:
result += str(temp_node) + ' -> '
temp_node = temp_node.next
if temp_node == self.head:
break
return result.rstrip(' -> ')This method helps to print the list, showing each node’s value and visually depicting the list’s structure.
Append
Adding a new element to the end of the list:
def append(self, value):
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
new_node.next = new_node # Points to itself, making the list circular.
else:
self.tail.next = new_node # Link the old last node to the new node.
new_node.next = self.head # Complete the circle by pointing back to the head.
self.tail = new_node # Update the tail to the new node.
self.length += 1Prepend
Adding a new element at the beginning of the list:
def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
new_node.next = new_node
else:
new_node.next = self.head
self.head = new_node
self.tail.next = new_node
self.length += 1Insert
Inserting a new element at a specific position:
def insert(self, index, value):
if index < 0 or index > self.length:
raise Exception("Index out of range")
if index == 0:
self.prepend(value)
elif index == self.length:
self.append(value)
else:
temp_node = self.head
for _ in range(index - 1):
temp_node = temp_node.next
new_node = Node(value)
new_node.next = temp_node.next
temp_node.next = new_node
self.length += 1After understanding how to add nodes to our list, let’s delve into how we can search for, access, update, and remove nodes, as well as how to clear the entire list.
Searching for Values
To find a value in the list, we use the search method:
def search(self, target):
current = self.head
index = 0
while current:
if current.value == target:
return index # Found the value, return its index
current = current.next
index += 1
if current == self.head:
break
return -1 # Value not foundThis method loops through the list, checking each node’s value against the target. If it finds a match, it returns the index of the node. If it doesn’t find the target by the time it returns to the head, it concludes the target isn’t present.
Accessing a Node by Index
To access a node at a specific index, we use the get method:
def get(self, index):
if index == -1:
return self.tail # Quick access to the tail node
elif index < 0 or index >= self.length:
return None # Index out of valid range
current = self.head
for _ in range(index):
current = current.next
return current # Return the node at the specified indexThis function checks if the index is valid, then traverses the list to the desired position and returns the node at that index. If the index is -1, it directly returns the tail, which is a convenient feature for circular lists.
Updating a Node’s Value
Updating the value of a node can be accomplished with the set_value method:
def set_value(self, index, value):
temp = self.get(index)
if temp:
temp.value = value
return True
return FalseThis method first retrieves the node at the specified index using get. If the node exists, it updates its value. This is useful for modifying the contents of the list after it's been created.
Removing Nodes
Removing nodes from the list can be done in several ways, depending on whether you want to remove the first node, the last node, or a node at a specific index.
Removing the First Node (Pop First)
def pop_first(self):
if self.length == 0:
return None
popped_node = self.head
if self.length == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.tail.next = self.head
self.length -= 1
return popped_nodeThis method removes the first node from the list and adjusts the head and tail pointers to maintain circularity, especially when the list contains more than one node.
Removing the Last Node (Pop)
def pop(self):
if self.length == 0:
return None
if self.length == 1:
return self.pop_first()
temp = self.head
while temp.next != self.tail:
temp = temp.next
popped_node = self.tail
self.tail = temp
self.tail.next = self.head
self.length -= 1
return popped_nodeSimilar to pop_first, but for the last node. It finds the second-to-last node, updates it to be the new tail, and ensures it points back to the head.
Removing a Node at a Specific Index
def remove(self, index):
if index < 0 or index >= self.length:
return None
if index == 0:
return self.pop_first()
if index == self.length - 1:
return self.pop()
prev_node = self.get(index - 1)
popped_node = prev_node.next
prev_node.next = popped_node.next
self.length -= 1
return popped_nodeThis function removes a node anywhere in the list by first finding the node just before the one to be removed, then adjusting pointers to skip over the removed node.
Clearing the List
Finally, to clear the entire list, we use the delete_all method:
def delete_all(self):
self.tail.next = None # Break the circular link to help with garbage collection
self.head = None
self.tail = None
self.length = 0This method resets the list to its initial state, effectively removing all nodes and breaking the circular link to avoid potential issues with memory.
By now, you should have a solid understanding of how circular singly linked lists work and how to implement them in Python. These lists are powerful tools in programming, especially in scenarios where a circular, repeating data structure can simplify logic and improve performance. Whether you’re managing round-robin schedulers, implementing complex algorithmic challenges, or just exploring new data structures, the circular singly linked list offers a robust and intriguing option.
If you found them helpful:
Show some love with a 50-clap
Drop a comment.
Share your favorite part!
Discover more in my online courses at AppMillers 🚀
Connect on LinkedIn: Elshad Karimov
Follow on X (Twitter): Elshad Karimov
Subscribe to our Newsletter for recent Technological advancements: Newsletter by Elshad Karimov