The circular linked list a variant of the singly linked list where the last Node links to the head rather than None. Since the list contains a circular reference to the Head, we can navigate a circular linked list starting at any index rather than starting at the head node.
Here is the code for a circular linked list implementation with unit tests. We won’t dicuss the unit tests in this post, but we will go over the linked list implementation.
from enum import Enum
class NodeConstants(Enum):
FRONT_NODE = 1
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
def __str__(self):
if self.element:
return self.element.__str__()
else:
return 'Empty Node'
def __repr__(self):
return self.__str__()
class CircularLinkedList:
def __init__(self):
self.head = Node(element=NodeConstants.FRONT_NODE)
self.head.next_node = self.head
def size(self):
count = 0
current = self.head.next_node
while current != self.head:
count += 1
current = current.next_node
return count
def insert_front(self, data):
node = Node(element=data, next_node=self.head.next_node)
self.head.next_node = node
def insert_last(self, data):
current_node = self.head.next_node
while current_node.next_node != self.head:
current_node = current_node.next_node
node = Node(element=data, next_node=current_node.next_node)
current_node.next_node = node
def insert(self, data, position):
if position == 0:
self.insert_front(data)
elif position == self.size():
self.insert_last(data)
else:
if 0 < position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position - 1:
current_pos += 1
current_node = current_node.next_node
node = Node(data, current_node.next_node)
current_node.next_node = node
else:
raise IndexError
def remove_first(self):
self.head.next_node = self.head.next_node.next_node
def remove_last(self):
current_node = self.head.next_node
while current_node.next_node.next_node != self.head:
current_node = current_node.next_node
current_node.next_node = self.head
def remove(self, position):
if position == 0:
self.remove_first()
elif position == self.size():
self.remove_last()
else:
if 0 < position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position - 1:
current_node = current_node.next_node
current_pos += 1
current_node.next_node = current_node.next_node.next_node
else:
raise IndexError
def fetch(self, position):
if 0 <= position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position:
current_node = current_node.next_node
current_pos += 1
return current_node.element
else:
raise IndexError
import unittest
from random import randint
class TestCircularLinkedList(unittest.TestCase):
names = ['Bob Belcher',
'Linda Belcher',
'Tina Belcher',
'Gene Belcher',
'Louise Belcher']
def test_init(self):
dll = CircularLinkedList()
self.assertIsNotNone(dll.head)
self.assertEqual(dll.size(), 0)
def test_insert_front(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_front(name)
self.assertEqual(dll.fetch(0), TestCircularLinkedList.names[4])
self.assertEqual(dll.fetch(1), TestCircularLinkedList.names[3])
self.assertEqual(dll.fetch(2), TestCircularLinkedList.names[2])
self.assertEqual(dll.fetch(3), TestCircularLinkedList.names[1])
self.assertEqual(dll.fetch(4), TestCircularLinkedList.names[0])
def test_insert_last(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
for i in range(len(TestCircularLinkedList.names) - 1):
self.assertEqual(dll.fetch(i), TestCircularLinkedList.names[i])
def test_insert(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
pos = randint(0, len(TestCircularLinkedList.names) - 1)
dll.insert('Teddy', pos)
self.assertEqual(dll.fetch(pos), 'Teddy')
def test_remove_first(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
for i in range(dll.size(), 0, -1):
self.assertEqual(dll.size(), i)
dll.remove_first()
def test_remove_last(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
for i in range(dll.size(), 0, -1):
self.assertEqual(dll.size(), i)
dll.remove_last()
def test_remove(self):
dll = CircularLinkedList()
for name in TestCircularLinkedList.names:
dll.insert_last(name)
dll.remove(1)
self.assertEqual(dll.fetch(0), 'Bob Belcher')
self.assertEqual(dll.fetch(1), 'Tina Belcher')
self.assertEqual(dll.fetch(2), 'Gene Belcher')
self.assertEqual(dll.fetch(3), 'Louise Belcher')
if __name__ == '__main__':
unittest.main()
NodeContants
NodeConstants is an example of Python’s enumeration. A circular linked list requires a distinct head node that the client code can easily identify. Without a distinct head node, we could easily introduce an infinate loop when traversing the linked list. We are going to use NodeContants to help identify the head node.
from enum import Enum
class NodeConstants(Enum):
FRONT_NODE = 1
There are other ways to indentify the head node, so using enumerations isn’t required. It does give us a way to show off how to do enumerations in Python for those readers who are interested.
Node
We can use the same Node class that we used in singular linked list. Like all linked lists, the Node class holds the data stored in the list and a reference to the next Node in the list.
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
def __str__(self):
if self.element:
return self.element.__str__()
else:
return 'Empty Node'
def __repr__(self):
return self.__str__()
CircularLinkedList
This class is the work house of this module and provides us with the linked list implementation. It’s not very different than the singular linked list implementation.
class CircularLinkedList:
def __init__(self):
self.head = Node(element=NodeConstants.FRONT_NODE)
self.head.next_node = self.head
def size(self):
count = 0
current = self.head.next_node
while current != self.head:
count += 1
current = current.next_node
return count
def insert_front(self, data):
node = Node(element=data, next_node=self.head.next_node)
self.head.next_node = node
def insert_last(self, data):
current_node = self.head.next_node
while current_node.next_node != self.head:
current_node = current_node.next_node
node = Node(element=data, next_node=current_node.next_node)
current_node.next_node = node
def insert(self, data, position):
if position == 0:
self.insert_front(data)
elif position == self.size():
self.insert_last(data)
else:
if 0 < position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position - 1:
current_pos += 1
current_node = current_node.next_node
node = Node(data, current_node.next_node)
current_node.next_node = node
else:
raise IndexError
def remove_first(self):
self.head.next_node = self.head.next_node.next_node
def remove_last(self):
current_node = self.head.next_node
while current_node.next_node.next_node != self.head:
current_node = current_node.next_node
current_node.next_node = self.head
def remove(self, position):
if position == 0:
self.remove_first()
elif position == self.size():
self.remove_last()
else:
if 0 < position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position - 1:
current_node = current_node.next_node
current_pos += 1
current_node.next_node = current_node.next_node.next_node
else:
raise IndexError
def fetch(self, position):
if 0 <= position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position:
current_node = current_node.next_node
current_pos += 1
return current_node.element
else:
raise IndexError
__init__
We initialize the linked list by creating a head Node and then pointing it’s next_node at itself.
def __init__(self):
self.head = Node(element=NodeConstants.FRONT_NODE)
self.head.next_node = self.head
In this case, we will use our NodeConstants.FRONT_NODE to help us indentify the head of the list in the debugger. We don’t actually need this but it does help make the code more clear.
size
This method returns the number of elements contained in the linked list.
def size(self):
count = 0
current = self.head.next_node
while current != self.head:
count += 1
current = current.next_node
return count
We begin by making a count variable and a current variable. Current points at self.head.next_node because we aren’t counting self.head. Now we are going to loop until current == self.head. We don’t need to check for None in this case because we don’t have any such Nodes in this implementation.
As we loop, we increment count by one and then advance current to the next node in the list. Eventually, current points at self.head and we terminate the loop at this point. We then return the count.
insert_front
There isn’t much work to do to insert a Node at the beginning of the list.
def insert_front(self, data):
node = Node(element=data, next_node=self.head.next_node)
self.head.next_node = node
We create a new Node and point it’s next node at self.head.next_node. Then we just need to point self.head.next_node at the new Node.
insert_last
To insert a Node at the end of the list, we need to tranverse the list to right before self.head.
def insert_last(self, data):
current_node = self.head.next_node
while current_node.next_node != self.head:
current_node = current_node.next_node
node = Node(element=data, next_node=current_node.next_node)
current_node.next_node = node
Once again, we have a current_node that requires us to start at self.head.next_node. We then enter a loop that terminates when current_node.next_node == self.head to avoid an infinate loop.
Once we find our insertion point, we create a new Node and point it’s next_node to current_node.next_node (which happens to be self.head). Then current_node.next_node is updated to point at Node.
insert
The insert method let’s us support insertions in the middle of the list. It works by traversing the list to right before the desired position and performing an insertion.
Keep in mind this method has four possible scenerios it must take into account.
- Position is 0 -> insert at the front
- Position == size() -> insert the end
- Position size() -> throw exception
- Position > 0 and Position Perform insertion
def insert(self, data, position):
if position == 0:
# Case 1
self.insert_front(data)
elif position == self.size():
# Case 2
self.insert_last(data)
else:
if 0 < position < self.size():
# Case 4
current_node = self.head.next_node
current_pos = 0
while current_pos < position - 1:
current_pos += 1
current_node = current_node.next_node
node = Node(data, current_node.next_node)
current_node.next_node = node
else:
# Case 3
raise IndexError
The cases have been identified with the comments. In cases one and two, we are simply going to reuse code by calling self.insert_front or self.insert_last respectively. We handle case three by raising IndexError to indicate a programming error.
Case four works similar to other other insertions. We start with current_node at self.head.next_node and current_pos at 0. Then we iterate through the list until we reach the node right before the specified position (position – 1).
After exiting the while loop, we create a new Node and point it's next_node at current_node.next_node. The we update current_node.next_node to point at our new Node which now resides at our position.
remove_first
When removing nodes from the front of the list, we reassign self.head.next_node rather than self.head.
def remove_first(self):
self.head.next_node = self.head.next_node.next_node
Remember that the last Node in this linked list always points at self.head. If we accidently reassigned self.head rather than self.head.next_node, we would break our linked list. However, when we update self.head.next_node to point at self.head.next_node.next_node, we are removing the Node currently located at self.head.next_node.
The removed Node gets garbage collected by the Python runtime environment and the linked list is shrunk by one element.
remove_last
It’s a fairly painless process to remove elements from the end of a circular linked list. We simply need to advance to the element located two positions before self.head and then point that Node’s next_node at self.head.
def remove_last(self):
current_node = self.head.next_node
while current_node.next_node.next_node != self.head:
current_node = current_node.next_node
current_node.next_node = self.head
We begin with current_node pointing at self.head.next_node and then enter a while loop. Notice that the condition on the while loop is current_node_next_node.next_node != self.head. We want to advance to the second to last element in this list.
Once we have positioned current_node to the proper index in the list, we remove the last node by pointing current_node.next_node at self.head. The removed Node ends up getting grabage collected by Python’s runtime.
remove
The remove method supports removing items from the middle of the list. It has to account for the same cases as insert.
def remove(self, position):
if position == 0:
# Case 1
self.remove_first()
elif position == self.size():
# Case 2
self.remove_last()
else:
if 0 < position < self.size():
# Case 3
current_node = self.head.next_node
current_pos = 0
while current_pos < position - 1:
current_node = current_node.next_node
current_pos += 1
current_node.next_node = current_node.next_node.next_node
else:
# Case 4
raise IndexError
Once again, we are going to dicuss case 3. We start with current_node pointing at self.head.next_node and current_pos = 0. We traverse the list until we arrive at the Node located before position. Now we nust point current_node.next_node at current_node.next_node.next_node. The removed Node gets garbage collected by the Python runtime.
fetch
This method let’s us get data out of the list.
def fetch(self, position):
if 0 <= position < self.size():
current_node = self.head.next_node
current_pos = 0
while current_pos < position:
current_node = current_node.next_node
current_pos += 1
return current_node.element
else:
raise IndexError
After checking position to make sure it's valid, we traverse the list until we arrive at the position. Then we return current_node.element. If position isn't valid, we raise an exception.
Conclusion
This code shows an example a circular linked list, but it’s a simple implementation that we could optimize. This implementation always starts at self.head and traverse the list to a required position, but it could operate by tracking the most recently accessed Node and starting traversals from that point rather than always starting at the front of the list.
Stone Soup Programming 