Demystifying Algorithms: Circular Linked Lists

What is a Circular Linked List?

A circular linked list is a variation of a linked list where:

1. The last node points back to the first node, forming a loop.
2. Traversal can continue indefinitely because there’s no null at the end.

Circular linked lists can be:

• Singly Circular: Each node has one pointer (Next), and the last node points to the head.
• Doubly Circular: Each node has two pointers (Next and Prev), and the last node’s Next points to the head, while the head’s Prev points to the last node.

This structure is efficient for situations requiring cyclic traversal, like buffering or real-time simulations.

The Technical View

• Time Complexity:

  • Access: (O(n)) (you must traverse the list).
  • Insertion/Deletion:
  • At the head or tail: (O(1)).
  • At a specific position: (O(n)).

• Space Complexity:

  • (O(n)), where (n) is the number of nodes.

A Fifth-Grader's Summary

Imagine a group of kids playing a game of tag in a circle. Each kid points to the next one in the circle, and there’s no "end" of the line—they just keep going around. That’s how a circular linked list works!

Real-World Example

A carousel (merry-go-round) is a real-world analogy for a circular linked list. Each seat (node) points to the next, and the last seat connects back to the first, creating a continuous loop.

Operations on a Circular Linked List

1. Insert a Node at the Head

Problem: Add a new node with value 3 at the beginning of the list.

Code:

class CircularLinkedListNode {
    public int Data;
    public CircularLinkedListNode Next;

    public CircularLinkedListNode(int data) {
        Data = data;
        Next = null;
    }
}

CircularLinkedListNode InsertAtHead(CircularLinkedListNode head, int data) {
    CircularLinkedListNode newNode = new CircularLinkedListNode(data);

    if (head == null) {
        newNode.Next = newNode;
        return newNode;
    }

    CircularLinkedListNode current = head;
    while (current.Next != head) {
        current = current.Next;
    }

    newNode.Next = head;
    current.Next = newNode;

    return newNode;
}

Initial List: 5 -> 10 -> 15 -> (points back to 5)

Steps:

1. Create a new node with data 3.
2. Traverse to the last node (15) that points back to the head (5).
3. Point the last node’s Next to the new node.
4. Point the new node’s Next to the current head (5).
5. Update the head to the new node.

Updated List: 3 -> 5 -> 10 -> 15 -> (points back to 3)

2. Insert a Node at the Tail

Problem: Add a new node with value 20 at the end of the list.

Code:

CircularLinkedListNode InsertAtTail(CircularLinkedListNode head, int data) {
    CircularLinkedListNode newNode = new CircularLinkedListNode(data);

    if (head == null) {
        newNode.Next = newNode;
        return newNode;
    }

    CircularLinkedListNode current = head;
    while (current.Next != head) {
        current = current.Next;
    }

    current.Next = newNode;
    newNode.Next = head;

    return head;
}

Initial List: 5 -> 10 -> 15 -> (points back to 5)

Steps:

1. Create a new node with data 20.
2. Traverse to the last node (15) that points back to the head (5).
3. Point the last node’s Next to the new node.
4. Point the new node’s Next to the head.

Updated List: 5 -> 10 -> 15 -> 20 -> (points back to 5)

3. Insert a Node at a Specific Position

Problem: Insert a node with value 12 at position 2 (0-based index).

Code:

CircularLinkedListNode InsertAtPosition(CircularLinkedListNode head, int data, int position) {
    CircularLinkedListNode newNode = new CircularLinkedListNode(data);

    if (position == 0) {
        return InsertAtHead(head, data);
    }

    CircularLinkedListNode current = head;
    while (position - 1 > 0) {
        current = current.Next;
        position--;
    }

    newNode.Next = current.Next;
    current.Next = newNode;

    return head;
}

Initial List: 5 -> 10 -> 15 -> (points back to 5)

Steps:

1. Create a new node with data 12.
2. Traverse to the node at position 1 (10).
3. Set the new node’s Next to the node at position 2 (15).
4. Set the Next of the node at position 1 (10) to the new node.

Updated List: 5 -> 10 -> 12 -> 15 -> (points back to 5)

4. Delete a Node

Problem: Remove the node at position 1 (0-based index).

Code:

CircularLinkedListNode DeleteNode(CircularLinkedListNode head, int position) {
    if (head == null) return null;

    if (position == 0) {
        if (head.Next == head) return null;

        CircularLinkedListNode current = head;
        while (current.Next != head) {
            current = current.Next;
        }
        current.Next = head.Next;
        return current.Next;
    }

    CircularLinkedListNode currentNode = head;
    while (position - 1 > 0) {
        currentNode = currentNode.Next;
        position--;
    }

    currentNode.Next = currentNode.Next.Next;
    return head;
}

Initial List: 5 -> 10 -> 15 -> (points back to 5)

Steps:

1. Traverse to the node at position 0 (5).
2. Update pointers:
   • Point 5’s Next to 15.

Updated List: 5 -> 15 -> (points back to 5)

5. Detect a Loop in a Circular Linked List

Problem: Check if the linked list contains a loop.

Code:

bool HasLoop(CircularLinkedListNode head) {
    if (head == null) return false;

    CircularLinkedListNode slow = head, fast = head;

    while (fast != null && fast.Next != null) {
        slow = slow.Next;
        fast = fast.Next.Next;

        if (slow == fast) return true;
    }

    return false;
}

Initial List: 5 -> 10 -> 15 -> (points back to 5)

Steps:

1. Use two pointers (slow and fast).
2. Move slow one step at a time and fast two steps.
3. If they meet, there’s a loop.

Result: Returns true for a circular linked list.

Conclusion

Circular linked lists are useful for scenarios requiring continuous or cyclic traversal, such as round-robin scheduling or buffering systems. Understanding their operations and behavior equips you to handle efficient data structures for cyclic problems.

Stay tuned for more demystified data structures and algorithms!