Traversal of Circular Linked List in DSA Python - Time & Space Complexity

Time Complexity: Traversal of Circular Linked List

O(n)

Understanding Time Complexity

We want to understand how long it takes to go through all items in a circular linked list.

How does the time grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def traverse_circular_list(head):
    if not head:
        return
    current = head
    while True:
        print(current.data)
        current = current.next
        if current == head:
            break

This code prints each element in a circular linked list once, stopping when it loops back to the start.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that visits each node once.
• How many times: Exactly once for each node in the list, until it returns to the start.

How Execution Grows With Input

As the list grows, the number of steps grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: The steps increase one-for-one with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to traverse grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Since the list loops, traversal might never end or take infinite time."

[OK] Correct: The code stops when it returns to the start node, so it visits each node only once and ends properly.

Interview Connect

Understanding traversal time helps you explain how linked lists work and shows you can reason about loops that cycle back.

Self-Check

"What if the list was singly linked but not circular? How would the time complexity change?"