Traversal and Printing a Linked List in DSA C - 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 it takes changes as the list grows.

We ask: How does the number of steps grow when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    int data;
    struct Node* next;
};

void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
    

This code goes through each node in the linked list and prints its value until it reaches the end.

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 there are nodes in the list.

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	About 10 steps
100	About 100 steps
1000	About 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: "The printing takes constant time because it just prints once."

[OK] Correct: Actually, it prints once for each node, so the time grows with the list size, not fixed.

Interview Connect

Understanding this helps you explain how simple list operations scale, a key skill in many coding interviews.

Self-Check

"What if we changed the linked list to a doubly linked list? How would the time complexity change when printing all nodes?"