Circular linked list in Data Structures Theory - Full Explanation

Introduction

Imagine you want to keep track of items in a list where you can keep moving forward without ever reaching an end. This is useful when you want to cycle through items repeatedly without stopping. A circular linked list solves this by connecting the last item back to the first, creating a loop.

Explanation

Structure of Circular Linked List

A circular linked list is like a chain of nodes where each node points to the next one. Unlike a regular linked list, the last node points back to the first node instead of pointing to nothing. This creates a circle, so you can keep moving from one node to the next endlessly.

The last node links back to the first node, forming a continuous loop.

Traversal in Circular Linked List

To go through the nodes, you start at any node and keep moving to the next node. Because the list loops, you must be careful to stop after one full cycle to avoid an infinite loop. Usually, you stop when you return to the starting node.

Traversal requires a stopping condition to avoid infinite looping.

Insertion in Circular Linked List

You can add new nodes anywhere in the list. When inserting at the end, you link the new node to the first node and update the last node to point to the new node. This keeps the circle intact. Inserting at the beginning or middle follows similar pointer updates.

Insertion updates pointers to maintain the circular connection.

Deletion in Circular Linked List

Removing a node means changing the pointer of the previous node to skip the removed node and point to the next one. If you remove the first node, you must also update the last node to point to the new first node. This keeps the circle unbroken.

Deletion adjusts pointers to keep the list circular.

Real World Analogy

Imagine a group of friends sitting in a circle playing a game where the turn passes from one person to the next endlessly. When the last person finishes their turn, it goes back to the first friend, so the game never stops.

Structure of Circular Linked List → Friends sitting in a circle where each friend passes the turn to the next

Traversal in Circular Linked List → Passing the turn around the circle until it comes back to the starting friend

Insertion in Circular Linked List → Adding a new friend into the circle without breaking the passing order

Deletion in Circular Linked List → Removing a friend from the circle and passing the turn directly to the next friend

Diagram

Diagram

┌───────┐     ┌───────┐     ┌───────┐
│ Node1 │ → │ Node2 │ → │ Node3 │
└───┬───┘     └───┬───┘     └───┬───┘
    ↑             ↓             │
    └─────────────┴─────────────┘

This diagram shows three nodes connected in a circle, where the last node points back to the first node.

Key Facts

Circular linked list → A linked list where the last node points back to the first node, forming a loop.

Node → An element in the list containing data and a pointer to the next node.

Traversal → Visiting each node in the list, usually stopping after one full cycle in a circular list.

Insertion → Adding a new node by updating pointers to maintain the circular structure.

Deletion → Removing a node by adjusting pointers to keep the list connected in a circle.

Code Example

Data Structures Theory

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

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

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

    def traverse(self):
        if not self.head:
            return []
        result = []
        current = self.head
        while True:
            result.append(current.data)
            current = current.next
            if current == self.head:
                break
        return result

cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
print(cll.traverse())

Common Confusions

Thinking a circular linked list has a clear end like a regular linked list.

Thinking a circular linked list has a clear end like a regular linked list. A circular linked list has no end because the last node points back to the first, creating an endless loop.

Believing traversal can stop when a node's next pointer is null.

Believing traversal can stop when a node's next pointer is null. In a circular linked list, no node's next pointer is null; traversal stops when you return to the starting node.

Summary

A circular linked list connects the last node back to the first, forming a loop with no end.

Traversal requires careful stopping to avoid infinite loops by checking when you return to the start.

Insertion and deletion update pointers to keep the circular structure intact.