8.3. Circular Linked Lists

Circular linked lists are a type of linked list where the last node points back to the first node. This makes it a circular data structure. In this notebook, we will implement a circular linked list and its operations.

Fig. 8.14 A circular linked list is a type of linked list where the last node points back to the first node.

There are two types of circular linked lists:

1. Singly Circular Linked List: In this type of circular linked list, each node has a single pointer that points to the next node in the list.

2. Doubly Circular Linked List: In this type of circular linked list, each node has two pointers: one that points to the next node and one that points to the previous node in the list.

Fig. 8.15 There are two types of circular linked lists: singly circular linked list and doubly circular linked list.

The implementation of the circular linked list depends on the type of linked list we want to create. In this notebook, we will implement the singly circular linked list.

8.3.1. Node

Let’s start by implementing the Node class for the singly circular linked list:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Note that this is unchanged from the singly linked list implementation.

8.3.2. CircularLinkedList

Next, we will implement the circular linked list class. It has a head field that points to the first node in the list.

class CircularLinkedList:
    def __init__(self):
        self.head = None

8.3.3. Insertion

To insert a new node in a circular linked list, we need to follow these steps:

1. Create a new node with the given data.

2. If the list is empty, set the head to the new node and make the new node point to itself.

3. Otherwise, traverse the list to find the last node.

4. Make the last node point to the new node.

5. Make the new node point to the head node.

    def insert(self, data):
        
        # step 1. create a new node
        new_node = Node(data) 

        # step 2. if the list is empty, set the head to the new node
        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
        else:
            # step 3. traverse the list to find the last node

            current = self.head
            while current.next != self.head:
                current = current.next
            
            # step 4. make the last node point to the new node
            current.next = new_node

            # step 5. make the new node point to the head node
            new_node.next = self.head

8.3.4. Deletion

To delete a node from a circular linked list, we need to follow these steps:

1. If the list is empty, return.

2. Traverse the list to find the node with the given data.

3. If the node is not found, return.

4. If the node to be deleted is the head node:

   • If the list has only one node, set the head to None.

   • Otherwise, find the last node and make it point to the next node of the head.

5. If the node to be deleted is not the head node:

   • If the node to be deleted is the last node, make the previous node point to the head.

   • Otherwise, make the previous node point to the next node of the node to be deleted.

    def remove(self, data):
        # step 1. if the list is empty, return
        if self.is_empty():
            return

        current = self.head
        prev = None

        # step 2. traverse the list to find the node with the given data
        while current.data != data:
            
            # step 3. if the node is not found, return
            if current.next == self.head:
                return
            prev = current
            current = current.next

        # step 4. if the node to be deleted is the head node
        if prev is None:
            if current.next == self.head:
                self.head = None
            else:
                temp = current.next
                while temp.next != self.head:
                    temp = temp.next
                self.head = current.next
                temp.next = self.head
        elif current.next == self.head:
            # step 5a. if the node to be deleted is the last node
            prev.next = self.head
        else:
            # step 5b. make the previous node point to the next node of the node to be deleted
            prev.next = current.next

8.3.5. Analysis

The time complexity of the insertion operation is O(n) in the worst case when we need to traverse the list to find the last node. The time complexity of the deletion operation is also O(n) in the worst case when we need to traverse the list to find the node to be deleted.

The space complexity of the circular linked list is O(n) for n nodes in the list.