Circular Linked List—Python

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.

  1. Position is 0 -> insert at the front
  2. Position == size() -> insert the end
  3. Position size() -> throw exception
  4. 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s