Circular Linked List in Python using OOP

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article at OpenGenus, we will explore how to implement Circular Linked List in Python using OOP.

Table of Contents:

  1. Introduction
  2. Implementing the Node class
  3. Creating the CircularLinkedList class
  4. Appending elements to the circular linked list
  5. Displaying the circular linked list
  6. Inheritance
  7. Conclusion

Introduction
A linked list is a type of data structure made up of a number of nodes, each of which has a value and a reference to the node after it in the list. A circular loop is created in a circular linked list when the final node's subsequent reference points back to the first node. In this article, object-oriented programming (OOP) ideas are used to create a circular linked list in Python.

Implementing the Node class
Let's start by creating the Node class that will act as the foundation of our circular linked list. The Node class will have two attributes: "next" and "data," which refer to the next node in the sequence and respectively store the node's value.

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

Creating the CircularLinkedList class
Let's define the CircularLinkedList class now, which will manage the operations and keep the circular linked list in a stable state. The class will contain a head attribute with a default value of "None," which denotes an empty list. 'is_empty' function will also be included to determine whether or not the circular linked list is empty.

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

    def is_empty(self):
        return self.head is None

Appending elements to the circular linked list
The circular linked list's new node is added using the append technique. It uses the Node class to initially construct a new node before determining whether the list is empty. If it is empty, the new node assumes the head position and sets its next reference to self, resulting in a loop. If not, it goes down the list until it reaches the last node (which is indicated by the 'next' reference going back to the head) and then adds the new node by changing the references.

class CircularLinkedList:
    # ...

    def append(self, data):
        new_node = Node(data)

        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

Displaying the circular linked list
The items of the circular linked list are printed using the display method. It begins at the top and works its way down the list, outputting the data for each node as it goes.

class CircularLinkedList:
    # ...

    def display(self):
        if self.is_empty():
            print("Circular Linked List is empty")
        else:
            current = self.head
            while True:
                print(current.data, end=" ")
                current = current.next
                if current == self.head:
                    break

Conclusion
In conclusion, by applying OOP concepts to the implementation of a circular linked list in Python, we may produce a modular and adaptable data structure. We may add entries to the circular linked list and display its contents by defining the Node class and the CircularLinkedList class. This strategy helps code maintenance and expansion while clearly separating the various concerns. By including more actions, such as deletion, searching, and inserting at certain spots, according to your needs, you may further develop this implementation.

Here's a full implementation

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

    def is_empty(self):
        return self.head is None

    def append(self, data):
        new_node = Node(data)

        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def display(self):
        if self.is_empty():
            print("Circular Linked List is empty")
        else:
            current = self.head
            while True:
                print(current.data, end=" ")
                current = current.next
                if current == self.head:
                    break
                    
    
clist = CircularLinkedList()

# Append elements to the circular linked list
clist.append(10)
clist.append(20)
clist.append(30)
clist.append(40)

# Display the elements of the circular linked list
clist.display()


Inheritance:
A major concept in object-oriented programming is inheritance, which enables us to build a new class (a "child class") from an existing class (a "parent class") by inheriting its properties and functions. Let's use the circular linked list example to illustrate inheritance.

The ability to traverse the list both forward and backwards may be added to a new class named "DoublyCircularLinkedList" that inherits from the "CircularLinkedList" class and expands its capability. This is the updated code:

class DoublyCircularLinkedList(CircularLinkedList):
    def __init__(self):
        super().__init__()

    def display_backward(self):
        if self.is_empty():
            print("Doubly Circular Linked List is empty.")
            return

        current = self.head
        while True:
            current = current.next
            print(current.data, end=" ")
            if current == self.head:
                break

        print()

We provide a new method named display_backward() in the DoublyCircularLinkedList class that enables backward traversal of the circular linked list. Using the 'next' reference, it travels from the 'head' to the 'previous' node. Then, until we return to the "head," we publish the data of each node.

To show how the Double Circular Linked List class inherits the capabilities of the Circular Linked List class, let's make an instance of it.
:

# Create an instance of DoublyCircularLinkedList
dlist = DoublyCircularLinkedList()

# Insert nodes
dlist.insert(50)
dlist.insert(60)
dlist.insert(70)
dlist.insert(80)

# Display the doubly circular linked list in both forward and backward directions
print("Doubly Circular Linked List (Forward):")
dlist.display()

print("Doubly Circular Linked List (Backward):")
dlist.display_backward()

# Delete a node
dlist.delete(60)

# Display the updated doubly circular linked list in both forward and backward directions
print("Updated Doubly Circular Linked List (Forward):")
dlist.display()

print("Updated Doubly Circular Linked List (Backward):")
dlist.display_backward()

As you can see, the DoublyCircularLinkedList class gets all of its characteristics and functions from the CircularLinkedList class. Additionally, it adds a brand-new function called display_backward() that enables us to navigate the circular linked list in reverse.

With the help of inheritance, we may reuse previously written code and increase the functionality of a base class to produce specialized classes with new capabilities.

By utilizing the power of OOP,

We are able to design attractive and effective data structures that encourage code reuse and readability. Circular linked lists have distinct advantages and can be used to build circular queues or represent cyclic data structures, among other things.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.