Traversal and Printing a Linked List in DSA Python - Time & Space Complexity

Time Complexity: Traversal and Printing a Linked List

O(n)

Understanding Time Complexity

When we traverse and print a linked list, we want to know how the time taken grows as the list gets longer.

We ask: How does the number of steps change when the list size increases?

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 print_linked_list(head):
    current = head
    while current is not None:
        print(current.data)
        current = current.next

This code goes through each node in the linked list and prints its data.

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 per node, so as many times as the number of nodes (n).

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	10 steps (visiting each node once)
100	100 steps
1000	1000 steps

Pattern observation: The steps increase in a straight line as the list size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to print the list grows directly with the number of nodes.

Common Mistake

[X] Wrong: "Printing a linked list is always constant time because we just start at the head."

[OK] Correct: Even though we start at the head, we must visit every node to print it, so time grows with list size.

Interview Connect

Understanding how traversing a linked list scales helps you explain simple but important operations clearly in interviews.

Self-Check

"What if we only printed every other node? How would the time complexity change?"