Circular Linked List Implementation in Python

← Back to Data Structures and Algorithms in Python

1. Introduction

A Circular Linked List (CLL) is a variation of the standard linked list where the last node of the list points back to the first node instead of having a null reference. This circular structure can be useful in scenarios where we need a cyclic iteration through the elements.

2. Implementation Steps

1. Define a Node class that contains the data and a reference to the next node.

2. Implement the CircularLinkedList class with a reference to the head node.

3. Create methods to append, prepend, remove, and display the list.

4. Ensure that the tail's next pointer always points back to the head to maintain the circular structure.

3. Implementation in Python

class Node:
    def __init__(self, data):
        self.data = data         # Holds the data of the node
        self.next = None         # Pointer to the next node
class CircularLinkedList:
    def __init__(self):
        self.head = None         # Initialize the head of the linked list
    def append(self, data):
        # Append data to the end of the linked list
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head
    def prepend(self, data):
        # Add data to the beginning of the linked list
        new_node = Node(data)
        new_node.next = self.head
        temp = self.head
        while temp.next != self.head:
            temp = temp.next
        temp.next = new_node
        self.head = new_node
    def remove(self, data):
        # Remove a node with the given data
        current = self.head
        prev = None
        while current:
            if current.data == data:
                if prev:
                    prev.next = current.next
                    if current == self.head:
                        self.head = current.next
                else:
                    next_node = current.next
                    if current == self.head:
                        while current.next != self.head:
                            current = current.next
                        current.next = next_node
                        self.head = next_node
                return
            prev = current
            current = current.next
            if current == self.head:
                return
    def display(self):
        # Print the linked list
        nodes = []
        current_node = self.head
        while True:
            nodes.append(current_node.data)
            current_node = current_node.next
            if current_node == self.head:
                break
        print(" -> ".join(map(str, nodes)) + " -> ...")
# Test the CircularLinkedList class
cllist = CircularLinkedList()
cllist.append("A")
cllist.append("B")
cllist.append("C")
cllist.prepend("D")
cllist.display()
cllist.remove("B")
cllist.display()

Output:

D -> A -> B -> C -> ...
D -> A -> C -> ...

Explanation:

1. The Node class for a circular linked list has the data and a pointer to the next node.

2. The CircularLinkedList class keeps a reference to the head node.

3. In the append method, we loop until we find the last node (which has a next pointer to the head) and add our new node there.

4. The prepend method involves adjusting both the new node's next pointer and the tail's next pointer to ensure a circular structure.

5. The remove method deletes nodes while considering edge cases to maintain the circular nature.

6. The display method prints elements in the list and ends with '...' to indicate the cyclic nature.

7. In the test, we create a list, append and prepend nodes, and then remove a node to demonstrate the circular linked list's functionality.

Related Data Structures in Python

1. Stack Implementation in Python
2. Queue Implementation in Python
3. Deque Implementation in Python
4. Singly Linked List Implementation in Python
5. Doubly Linked List Implementation in Python
6. Circular Linked List Implementation in Python
7. PriorityQueue Implementation in Python
8. Circular Queue Implementation in Python
9. Binary Search Tree Implementation in Python
10. Stack Implementation Using Linked List in Python
11. Stack Implementation Using Doubly Linked List in Python

← Back to Data Structures and Algorithms in Python