Get Length of Linked List in DSA C - Time & Space Complexity

Time Complexity: Get Length of Linked List

O(n)

Understanding Time Complexity

We want to know how long it takes to find the length of a linked list as the list grows.

The question is: how does the time needed change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int getLength(struct Node* head) {
    int count = 0;
    struct Node* current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}
    

This code counts how many nodes are in a linked list by moving through each node one by one.

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 in the list, from start to end.

How Execution Grows With Input

As the list gets longer, the time to count nodes 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 find the length grows directly with the number of nodes in the list.

Common Mistake

[X] Wrong: "The length can be found instantly without checking nodes."

[OK] Correct: Because a linked list does not store its size, you must visit each node to count them.

Interview Connect

Understanding this helps you explain how simple operations on linked lists work and shows you can analyze basic loops well.

Self-Check

"What if the linked list stored its length as a variable updated on insertions and deletions? How would the time complexity change?"