Data Structures in Python 🐍3️⃣ Circular Linked List

What is Circular Linked List 😵‍💫

Circular linked list is same as a singly linked list. The only difference is that the tail node points to the head 🔁 of the linked list instead of None🕳️.

Implementation 🧑🏻‍💻

We start by creating a class CircularLinkedList

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

1. Insertion 🪢

Now we will look at insertion: we can do insertion in different ways like append and prepend. To start with insertion we need node.
We will create a class Node🌗.

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

Now we will look at append method

def append(self, data):

    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        self.head.next = self.head
        return
    current_node = self.head
    while current_node.next != self.head:
        current_node = current_node.next
    current_node.next = new_node
    new_node.next = self.head

Seems good till now 🤔 We need to check the content of the linked list. For this, we will implement a new function print_list method

def print_list(self):
    current_node = self.head
    while current_node:
        print(current_node.data)
        current_node = current_node.next
        if current_node == self.head:
            break

Now we will look at prepend method where we insert an element at the beginning of the linked list.

def prepend(self, data):
    new_node = Node(data)
    current_node = self.head
    new_node.next = self.head
    if not self.head:
        new_node.next = new_node
    else:
        while current_node.next != self.head:
            current_node = current_node.next
        current_node.next = new_node
    self.head = new_node

2. Deletion 🗑️

We will implement deletion by value and deletion by position.
Let’s start by deletion_by_value method.

def remove(self, value):
    if self.head:
        if self.head.data == value:
            current_node = self.head
            while current_node.next != self.head:
                current_node = current_node.next
            if self.head == self.head.next:1
                self.head = None
            else:
                current_node.next = self.head.next
                self.head = self.head.next
        else:
            current_node = self.head
            previous_node = None
            while current_node.next != self.head:
                previous_node = current_node
                current_node = current_node.next
                if current_node.data == value:
                    previous_node.next = current_node.next
                    current_node = current_node.next

Next Up⏭️: Doubly Linked Lists