Circular Linked Lists

# CHAPTER 10

Circular Linked Lists #

1. Introduction #

2. Learning Objectives #

• Define the structural difference of a Circular Linked List.

• Traverse an infinite loop without crashing the program.

• Understand the unique "Tail-Only" pointer optimization.

• Identify real-world applications (Round-Robin scheduling).

3. The Architecture: Closing the Loop #

Visualizing a Singly Circular Linked List:

      -----------------------------------------
     |                                         |
     v                                         |
   [Head: 10] -> [Node: 20] -> [Node: 30] -> [Tail: 40]

*(Notice: There is absolutely no NULL value anywhere in this entire data structure!)*

4. The "Tail-Only" Pointer Trick #

• Tail: is tail. (Access back is O(1)).

• Head: is exactly tail.next! (Access front is O(1)).

5. Circular Traversal Algorithm #

To traverse exactly once, you must stop when you hit the Head *a second time*.

// Java Example: Safe Circular Traversal
public void traverseCircular(Node head) {
    if (head == null) return; // Empty list check
    
    Node current = head;
    
    // Using a DO-WHILE loop guarantees we run at least once before checking the condition
    do {
        System.out.print(current.data + " -> ");
        current = current.next;
    } while (current != head); // Stop when we lap around back to the start!
    
    System.out.println("(Back to Head)");
}

6. Insertion in a Circular List #

# Python Example: Insert at End (O(1) Time using Tail pointer)
def insert_at_end(self, data):
    new_node = Node(data)
    
    # Edge Case: List is totally empty
    if self.tail is None:
        self.tail = new_node
        new_node.next = new_node # It points to ITSELF to form a 1-node circle!
        return
        
    # Standard Insertion
    new_node.next = self.tail.next # New node points to the Head
    self.tail.next = new_node      # Old Tail points to New node
    self.tail = new_node           # Declare New node as the official Tail

7. Real-World Applications #

1. 1. Multiplayer Gaming: Managing whose turn it is. (Player 1 -> Player 2 -> Player 3 -> Player 1).

1. 2. CPU Round-Robin Scheduling: The Operating System must give 3 running applications a fraction of CPU time. It executes App 1, pauses it, executes App 2, executes App 3, and then loops back to App 1 infinitely until the user closes them.

1. 3. Carousel UI Elements: An image slider on a website where clicking "Next" on the final image seamlessly loops back to the first image.

8. Common Mistakes #

• Infinite Loops during Searching: If you are searching for the number 99 in a Circular List, and 99 does not exist, a standard while(current.data != 99) loop will spin infinitely forever, freezing the server CPU at 100% capacity. You must explicitly count nodes or check if current == head to force a termination!

9. Best Practices #

• Use the Do-While Loop: For standard languages (C, C++, Java), the do-while loop is the undisputed best practice for Circular Lists. It elegantly bypasses the awkward initial state where current == head on the very first execution step.

10. Exercises #

1. 1. Write an algorithm to count the total number of nodes in a Circular Linked List.

1. 2. What happens to the structure if you have a Circular List with only ONE node? What does its next pointer point to?

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Coding:* "Josephus Problem: n people are standing in a circle. Every k-th person is eliminated. Who is the last person standing? Solve this using a Circular Linked List." *(This is a legendary competitive programming question).*

• *Conceptual:* "Draw a diagram of a Doubly Circular Linked List containing 3 nodes. Explicitly label the prev and next pointers of the Head and Tail."

Common Pitfalls:

• Using standard while (current != null) out of habit during whiteboard interviews. The interviewer will instantly penalize you for architecting an infinite loop.

13. FAQs #

14. Summary #

15. Next Chapter Recommendation #