Data Structure

Circular Linked List in Python

8 Mins Read
Pinterest LinkedIn Tumblr

A Circular Linked List (CLL) is a type of linked list where the last node points back to the first node, forming a circle. This circular structure allows for efficient traversal and manipulation of the list. Unlike singly linked lists and doubly linked list, circular linked list do not have null values in their next pointers, making them ideal for applications requiring continuous looping.

Structure of a Circular Linked List Node

A node in a circular linked list contains:

  1. Data: The value stored in the node.
  2. Next Pointer: A pointer to the next node in the list.

Here’s a basic Python class representing a node in a circular linked list:

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

Advantages and Disadvantages of Circular Linked Lists

Advantages

  1. Efficient Traversal: The circular nature allows for continuous traversal without needing to reset.
  2. Simplified Operations: Insertion and deletion operations can be simplified, especially for circular buffers and round-robin scheduling.

Disadvantages

  1. Complexity: Implementing a circular linked list can be more complex than a singly linked list.
  2. Infinite Loop Risk: Improper handling can lead to infinite loops.

Inserting a Node at the Beginning of a Circular Linked List

To insert a node at the beginning of a CLL, you need to update the next pointer of the new node to point to the current head and then update the last node to point to the new node.

Example:

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

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

# Example usage
cll = CircularLinkedList()
cll.insert_at_beginning(10)
cll.insert_at_beginning(20)

Explanation

  • Initialization: We first check if the list is empty. If it is, we set the new node to point to itself.
  • Non-Empty List: We traverse to the last node (the node whose next points to the head), update its next pointer to the new node, and then set the new node’s next pointer to the current head. Finally, we update the head to the new node.

Inserting a Node at the End of a Circular Linked List

To insert a node at the end, traverse to the last node and update its next pointer to the new node, and set the new node’s next pointer to the head.

Example:

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

# Adding method to the class
CircularLinkedList.insert_at_end = insert_at_end

# Example usage
cll.insert_at_end(30)
cll.insert_at_end(40)

Explanation

  • Initialization: Check if the list is empty. If it is, initialize the list similarly to the beginning insertion.
  • Non-Empty List: Traverse to the last node, update its next pointer to the new node, and set the new node’s next pointer to the head.

Inserting a Node at a Given Position in a Circular Linked List

Inserting at a specific position requires traversing to that position and updating the pointers accordingly.

Example

def insert_at_position(self, data, position):
    if position == 0:
        self.insert_at_beginning(data)
        return

    new_node = Node(data)
    temp = self.head
    for _ in range(position - 1):
        if temp.next == self.head:
            raise IndexError("Position out of bounds")
        temp = temp.next

    new_node.next = temp.next
    temp.next = new_node

# Adding method to the class
CircularLinkedList.insert_at_position = insert_at_position

# Example usage
cll.insert_at_position(25, 2)

Explanation

  • Position Check: If the position is 0, we call the insert at beginning method.
  • Traverse: We traverse to the node before the desired position.
  • Update Pointers: Update the new node’s next pointer to the next node, and the current node’s next pointer to the new node.

Deleting a Node in a Circular Linked List

To delete a node, we need to update the pointers of the adjacent nodes to bypass the node to be deleted.

Example

def delete_node(self, key):
    if not self.head:
        return

    temp = self.head
    prev = None
    while True:
        if temp.data == key:
            if prev:
                prev.next = temp.next
            else:
                # Deleting head node
                if temp.next == self.head:
                    self.head = None
                else:
                    prev = self.head
                    while prev.next != self.head:
                        prev = prev.next
                    self.head = temp.next
                    prev.next = self.head
            return
        elif temp.next == self.head:
            break
        prev = temp
        temp = temp.next

# Adding method to the class
CircularLinkedList.delete_node = delete_node

# Example usage
cll.delete_node(25)

Explanation

  • Initialization: Check if the list is empty. If it is, there’s nothing to delete.
  • Traverse and Find Node: Traverse the list to find the node to delete.
  • Update Pointers: If the node is found, update the previous node’s next pointer to skip the node to be deleted. Special care is taken if the node to delete is the head.

Deleting the First Node of a Circular Linked List

Deleting the first node involves updating the head pointer and ensuring the last node points to the new head.

Example

def delete_first_node(self):
    if not self.head:
        return
    if self.head.next == self.head:
        self.head = None
    else:
        last = self.head
        while last.next != self.head:
            last = last.next
        self.head = self.head.next
        last.next = self.head

# Adding method to the class
CircularLinkedList.delete_first_node = delete_first_node

# Example usage
cll.delete_first_node()

Explanation

  • Single Node: If there’s only one node, we simply set the head to None.
  • Multiple Nodes: We find the last node, update the head to the next node, and set the last node’s next pointer to the new head.

Deleting the Last Node of a Circular Linked List

To delete the last node, we need to update the second last node’s next pointer to the head.

Example

def delete_last_node(self):
    if not self.head:
        return
    if self.head.next == self.head:
        self.head = None
    else:
        temp = self.head
        while temp.next.next != self.head:
            temp = temp.next
        temp.next = self.head

# Adding method to the class
CircularLinkedList.delete_last_node = delete_last_node

# Example usage
cll.delete_last_node()

Explanation

  • Single Node: If there’s only one node, we set the head to None.
  • Multiple Nodes: Traverse to the second last node and update its next pointer to the head.

Deleting a Node at a Given Position in a Circular Linked List

Deleting a node at a specific position involves traversing to the node before the desired position and updating the pointers.

Example

def delete_at_position(self, position):
    if not self.head:
        return
    if position == 0:
        self.delete_first_node()
        return

    temp = self.head
    for _ in range(position - 1):
        if temp.next == self.head:
            raise IndexError("Position out of bounds")
        temp = temp.next

    temp.next = temp.next.next

# Adding method to the class
CircularLinkedList.delete_at_position = delete_at_position

# Example usage
cll.delete_at_position(1)

Explanation

  • Position Check: If the position is 0, we call the delete first node method.
  • Traverse: Traverse to the node before the desired position.
  • Update Pointers: Update the current node’s next pointer to skip the node to be deleted.

Search a Node in a Circular Linked List

To search for a node, traverse the list until the node with the desired value is found.

Example

def search(self, key):
    if not self.head:
        return False
    temp = self.head
    while True:
        if temp.data == key:
            return True
        temp = temp.next
        if temp == self.head:
            break
    return False

# Adding method to the class
CircularLinkedList.search = search

# Example usage
print(cll.search(20))  # Output: True
print(cll.search(100))  # Output: False

Explanation

  • Initialization: Check if the list is empty. If it is, return False.
  • Traverse and Find: Traverse the list and check if the node’s data matches the key. If found, return True. If we reach back to the head, break the loop and return False.

Traversing a Circular Linked List

Traversal involves iterating through the list from the head back to the head.

Example

def traverse(self):
    if not self.head:
        return
    temp = self.head
    while True:
        print(temp.data, end=' ')
        temp = temp.next
        if temp == self.head:
            break
    print()

# Adding method to the class
CircularLinkedList.traverse = traverse

# Example usage
cll.traverse()  # Output: 20 10 30 40

Explanation

  • Initialization: Check if the list is empty.
  • Traverse and Print: Traverse from the head and print each node’s data until we reach back to the head.

Applications of Circular Linked Lists

Circular linked lists are used in various applications, such as:

  1. Circular Buffers: Used in buffering data streams.
  2. Round-Robin Scheduling: Useful in implementing round-robin scheduling in operating systems.
  3. Freespace Management in Memory Allocation: Managing free blocks of memory.

Comparison with Singly and Doubly Linked Lists

Singly Linked Lists

  1. Memory: Less memory usage as nodes have only one pointer.
  2. Traversal: Only supports forward traversal.

Doubly Linked Lists

  1. Memory: More memory usage due to two pointers.
  2. Traversal: Supports both forward and backward traversal.

Circular Linked Lists

  1. Memory: Similar to singly linked lists.
  2. Traversal: Continuous traversal without resetting to the head.

Common Mistakes and Best Practices in Implementing Circular Linked Lists

Common Mistakes

  1. Forgetting to Update Pointers: Ensure that all pointers are updated correctly when modifying the list.
  2. Handling Edge Cases: Properly handle cases where the list is empty or contains only one node.

Best Practices

  1. Consistent Pointer Updates: Always update the next pointers when modifying the list.
  2. Check for Infinite Loops: Ensure traversal has a terminating condition.
  3. Modular Code: Break down operations into smaller methods for easier debugging and maintenance.

Conclusion

Circular linked lists are versatile data structures that offer efficient traversal and manipulation. Understanding their implementation and applications can significantly enhance your programming skills. With the provided examples and detailed explanations, you should have a solid foundation to implement and utilize circular linked lists in various programming scenarios.

Related Posts

Write A Comment