Searching
Searching a linked list means walking it from the head, comparing each node's value against a target, and stopping as soon as a match is found or the list runs out.
Because a node only knows about the node right after it, there's no way to jump into the middle of the list. Every search has to start at the head and move one node at a time.
That single restriction is what separates linked list search from array search: an array gives you direct index access, so a sorted array can be binary searched in O(log n). A linked list can't, no matter how the data is ordered.
Key Insight: Linked lists only support linear search. There's no linked list equivalent of binary search, since reaching any node still requires traversing every node before it.
Search Approaches
Iterative Linear Search
Complexity: O(n)
Walk from head with a loop, comparing each node's value to the target
function search(head, target) {
let current = head;
let index = 0;
while (current) {
if (current.data === target) return index;
current = current.next;
index++;
}
return -1;
}Recursive Linear Search
Complexity: O(n) time, O(n) space (call stack)
Check the current node, then recurse on the rest of the list
function search(node, target) {
if (!node) return false;
if (node.data === target) return true;
return search(node.next, target);
}Search Process
- Start from the head node with a current pointer
- Compare current node's data with the target value
- If it matches, the search is done: return the node, its index, or true
- Otherwise move current to current.next and repeat
- If current becomes null, the target isn't in the list
Operation Visualization
| Operation | List State |
|---|---|
| List | head → [10] → [25] → [40] → [55] → null |
| search(40) | Check 10 (no) → check 25 (no) → check 40 (match, index 2) |
| search(99) | Check 10, 25, 40, 55, all fail, current reaches null: not found |
Edge Cases to Consider
Empty list (head = null): the target can never be found
Target at the head: found after a single comparison
Target at the tail: worst case for a hit, still O(n)
Target missing entirely: traversal runs all the way to null
Duplicate values: a linear search returns the first match unless coded to collect all matches
Best Practices
Guard against an empty list before starting the loop
Track an index alongside the pointer if the caller needs a position, not just a boolean
Prefer iteration over recursion for long lists to avoid stack depth issues
Stop the moment a match is found rather than scanning the rest of the list
If the same list is searched repeatedly, consider a hash map alongside it to get O(1) lookups
Comparison with Array Search
| Feature | Array | Linked List |
|---|---|---|
| Sorted, unsorted search | O(log n) sorted via binary search, O(n) unsorted | O(n) regardless of order |
| Access pattern | Random access by index | Sequential access via next pointer only |
| Why sorting doesn't help | Binary search needs the midpoint in O(1) | Reaching the midpoint itself costs O(n) |
| Best case | O(1) if target is at the checked index first | O(1) if target is at the head |
When to Choose: If you need frequent lookups by value, an array (sorted, with binary search) or a hash map will beat a linked list every time. Linked lists earn their keep when insertion and deletion at known positions matter more than search speed.
Implementation Notes
- Early exit: Return or break as soon as a match is found, don't keep scanning
- Return value: Decide upfront whether the caller needs the node itself, its index, or just a boolean
- Recursion depth: A recursive search on a very long list can exhaust the call stack; iterate instead
- Frequent lookups: If the same list is searched often, pairing it with a hash map trades memory for O(1) average lookups