Search for a Value in Linked List in DSA Python - 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 the time to find it changes as the list grows.

We ask: How many steps does it take to find a value when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def search_linked_list(head, target):
    current = head
    while current is not None:
        if current.value == target:
            return True
        current = current.next
    return False

This code looks through each node in the linked list to find if the target value exists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each node's value one by one.
• How many times: Up to once for every node in the list until the target is found or the list ends.

How Execution Grows With Input

As the list gets longer, the number of checks grows roughly the same as the number of nodes.

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

Pattern observation: The steps grow directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a value grows in a straight line with the number of nodes in the list.

Common Mistake

[X] Wrong: "Searching a linked list is always very fast because you just follow the links."

[OK] Correct: You must check nodes one by one, so if the list is long, it can take a long time.

Interview Connect

Understanding this helps you explain how simple searches work and why linked lists have different speed traits than arrays.

Self-Check

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