Circular Linked List in Python (Example)

In this tutorial, you will learn how to create a circular linked list using the Python programming language. A circular linked list is a data structure where each node has a reference to the next node, and the last node’s next pointer points back to the first node, creating a circular structure.

The table of content is structured as follows:

Let’s dive into the implementation!

Implementation of Circular Linked List

We’ll start by defining a Node class to represent each node in the circular linked list. Each node will have a value and a pointer to the next node.

class Node:
    def __init__(self, value):
        self.value = value                      # Value stored in the node
        self.next = None                        # Reference to the next node

Next, we’ll define a CircularLinkedList class to encapsulate the circular linked list. This class will have methods to perform various operations on the list, such as inserting at the end, inserting at the beginning, removing a node, and displaying the list.

class CircularLinkedList:
    def __init__(self):
        self.head = None                        # Reference to the first node in the list
 
    def is_empty(self):
        return self.head is None                # Check if the list is empty
 
    def prepend(self, value):
        new_node = Node(value)
        if self.is_empty():
            new_node.next = new_node            # Make the new node circular by pointing to itself
            self.head = new_node
        else:
            new_node.next = self.head           # New node points to the current head
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node             # Update the last node's next pointer to the new node
            self.head = new_node                # Update the head to the new node
 
    def append(self, value):
        new_node = Node(value)
        if self.is_empty():
            new_node.next = new_node            # Make the new node circular by pointing to itself
            self.head = new_node
        else:
            new_node.next = self.head           # New node points to the current head
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node             # Update the last node's next pointer to the new node
 
    def remove(self, value):
        if self.is_empty():                     # The list is empty
            return
 
        if self.head.value == value:            # The value is stored in head node
            current = self.head
            while current.next != self.head:
                current = current.next
            if self.head == self.head.next:     # Only one node in the list
                self.head = None
            else:
                current.next = self.head.next
                self.head = self.head.next
            return
 
        current = self.head                     # The value is stored in another node
        while current.next != self.head:
            if current.next.value == value:     # Update the current node's next pointer
                current.next = current.next.next  
                return
            current = current.next
 
    def display(self):
        if self.is_empty():
            print("Circular Linked List is empty.")
            return
 
        current = self.head
        while True:
            print(current.value, end=" ")
            current = current.next
            if current == self.head:
                break
        print()

The detailed explanations for each function in the CircularLinkedList class:

is_empty: Checks if the circular linked list is empty by verifying if the head is None.

prepend: Inserts a new node with the given value at the beginning of the circular linked list. If the list is empty, the new node becomes the head, and it points to itself. Otherwise, the new node’s next pointer is updated to point to the current head, and the last node’s next pointer is updated to the new node. Finally, the head is updated to the new node.

append: Inserts a new node with the given value at the end of the circular linked list. If the list is empty, the new node becomes the head, and it points to itself. Otherwise, the new node’s next pointer is updated to point to the current head, and the last node’s next pointer is updated to the new node.

remove: Removes the first occurrence of a node with the given value from the circular linked list. If the list is empty, or the value is not found, the function returns. If the value is found at the head, special handling is done to update the last node’s next pointer and update the head. Otherwise, the list is traversed until the value is found, and the previous node’s next pointer is updated to skip the node with the given value.

display: Traverses and prints the elements of the circular linked list. It starts from the head and continues until reaching the head again, printing the value of each node.

Example

Now that we have our CircularLinkedList class let’s test it with some examples to see how it performs.

# Create a circular linked list
clist = CircularLinkedList()
 
# Append elements
clist.append(1)
clist.append(2)
clist.append(3)
 
# Display the list
clist.display()  
# 1 2 3
 
# Prepend an element
clist.prepend(0)
 
# Display the list
clist.display()  
# 0 1 2 3
 
# Remove an element
clist.remove(2)
 
# Display the list
clist.display()  
# 0 1 3

In this example, we created a circular linked list, appended elements, prepended an element, and removed an element. The display method is used to print the contents of the list.

That’s it! You now have a basic implementation of a circular linked list in Python. You can extend the CircularLinkedList class with more functionality as needed for your specific use case.

Video, Further Resources & Summary

Do you need more explanations on how to define a circular linked list in Python? Then you should have a look at the following YouTube video of the Statistics Globe YouTube channel.

The YouTube video will be added soon.

Furthermore, you could have a look at some of the other tutorials on Statistics Globe:

• Are Dictionaries Faster than Lists in Python?
• Check if Linked List is Empty in Python (2 Examples)
• What is a List Node in Python? (2 Examples)
• How to Use Lists in Python (13 Examples)

This post has shown how to create a circular linked list in Python. In case you have further questions, you may leave a comment below.

This page was created in collaboration with Ömer Ekiz. You may have a look at Ömer’s author page to read more about his academic background and the other articles he has written for Statistics Globe.