Searching in a Linked List
What you'll learn: How to find a node containing a specific value in a linked list and why it takes linear time.
The Core Idea
Searching in a linked list means looking for a node that contains a particular value. Unlike arrays where you can jump to any index instantly, linked lists force you to start at the head and check each node one by one until you either find what you're looking for or reach the end of the list.
Think of it like searching for a specific page in a choose-your-own-adventure book where each page only tells you "continue to page X." You can't flip directly to page 47—you must follow the chain of instructions from the beginning.
How It Works
You start at the head pointer and examine the current node's data. If it matches your target value, you've found it! If not, you follow the next pointer to move forward and repeat the process. If you reach a NULL pointer (the end), the value isn't in the list.
current = head
while current is not NULL:
if current's data equals target:
return current (found it!)
current = current's next
return NULL (not found)
Time Complexity: O(n)
In the worst case, the value you're searching for is at the end of the list or doesn't exist at all, forcing you to visit every single node. With n nodes, this means n checks—hence O(n) linear time complexity. Unlike binary search on sorted arrays, there's no shortcut here because you must follow the sequential chain of pointers.
Key Takeaway: Searching a linked list requires linear traversal from head to tail, checking each node sequentially, resulting in O(n) time complexity.