Search for a Value in Linked List in DSA C - Time & Space Complexity

Time Complexity: Search for a Value in Linked List

O(n)

Understanding Time Complexity

When searching for a value in a linked list, we want to know how long it takes as the list grows.

We ask: How does the search time change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Search for a value in a linked list
int search(Node* head, int target) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == target) {
            return 1; // Found
        }
        current = current->next;
    }
    return 0; // Not found
}
    

This code checks each node one by one until it finds the target or reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each node's data once.
• How many times: Up to n times, where n is the number of nodes in the list.

How Execution Grows With Input

As the list grows, the search may check more nodes.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows directly with the list size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Searching a linked list is always fast because it's simple."

[OK] Correct: Even though the code is simple, the search may need to check every node, so it can take longer as the list grows.

Interview Connect

Understanding this helps you explain how linked lists work and why searching them takes time proportional to their size.

Self-Check

"What if the linked list was sorted? How would that change the time complexity of searching for a value?"