Back to blog
← View series: problem solving with dsa
← View series: problem solving with dsa
~/blog
Linked List Search
Jun 2, 2026•8 min read•By Mohammed Vasim
dsapythondata-structuresalgorithmsproblem-solving
The Problem
Find whether a value exists in a linked list. If it does, return the 0-indexed position. If it does not, return -1.
This is the same problem as searching an array, with one critical difference: you cannot binary search a linked list. Binary search requires random access to compute mid in O(1). A linked list requires O(n) to reach any position, which eliminates binary search's O(log n) advantage — the traversal to the midpoint costs more than the comparison saves.
Searching a Linked List
Example 1 — target found at the head.
Search for 10 in 10 → 20 → 30 → 40 → None:
text
Start: current → 10, position = 0
Check: current.data == 10? Yes.
Return: position 0
```text
One comparison. Best case.
**Example 2 — target found in the middle.**
Search for `30` in `10 → 20 → 30 → 40 → None`:
| Step | current | position | current.data | Comparison |
|---|---|---|---|---|
| 1 | 10 | 0 | 10 | 10 == 30? No. Advance. |
| 2 | 20 | 1 | 20 | 20 == 30? No. Advance. |
| 3 | 30 | 2 | 30 | 30 == 30? Yes. Return 2. |
Three steps. On average, n/2 steps for a present value.
**Example 3 — target not present.**
Search for `99` in `10 → 20 → 30 → 40 → None`:
| Step | current | position | current.data | Comparison |
|---|---|---|---|---|
| 1 | 10 | 0 | 10 | 10 == 99? No. Advance. |
| 2 | 20 | 1 | 20 | 20 == 99? No. Advance. |
| 3 | 30 | 2 | 30 | 30 == 99? No. Advance. |
| 4 | 40 | 3 | 40 | 40 == 99? No. Advance. |
| 5 | None | — | — | current is None. Exit loop. Return -1. |
All n elements checked. Worst case.
### Code
```textpython
def search(head: Node, target) -> int:
position = 0
current = head
while current:
if current.data == target:
return position
position += 1
current = current.next
return -1
```text
Line by line:
- `position = 0` — counter for the 0-indexed position.
- `current = head` — start at the first node. If `head` is `None`, the loop never runs.
- `while current:` — stop when `current` is `None`, which means the list has been fully traversed.
- `if current.data == target:` — compare the current node's data with the target.
- `return position` — found. Return immediately. Without this early return, the function would continue scanning the rest of the list unnecessarily.
- `position += 1` — not found yet. Increment the counter for the next node.
- `current = current.next` — advance to the next node.
- `return -1` — the loop completed without finding the target. The value is not in the list.
**Edge case — empty list.** `head` is `None`. `current` is `None`. Loop does not run. Returns -1.
**Edge case — target at head.** Returns 0 on the first iteration. No traversal needed.
**Edge case — target at tail.** The loop reaches the last node, checks `current.data`, and returns the position. All n nodes traversed.
**Edge case — duplicate values.** Returns the position of the first match. If you need the last match, traverse the entire list and update on each match. If you need all positions, collect them in a list.
### Code Trace — `search(head_of_10_20_30_40_50, 40)`
Search for `40` in `10 → 20 → 30 → 40 → 50 → None`.
| Loop iteration | current | position | `current.data == 40`? | Action |
|---|---|---|---|---|
| 1 | node(10) | 0 | 10 == 40? No | position → 1, current = node(20) |
| 2 | node(20) | 1 | 20 == 40? No | position → 2, current = node(30) |
| 3 | node(30) | 2 | 30 == 40? No | position → 3, current = node(40) |
| 4 | node(40) | 3 | 40 == 40? Yes | return 3 |
Four iterations. Found at position 3. The function returns early and does not visit `node(50)`.
**Time:** O(n) — every element compared in the worst case. **Space:** O(1) — two integer-sized variables regardless of list size.
Let us visualise each step:
<svg role="img" aria-label="search Step 1: current=node(10), data=10 != target=40, advance to next" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
<rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="20" y="25"></rect>
<text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
<path d="M 115 40 L 145 40" marker-end="url(#sarrow)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="155" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
<path d="M 250 40 L 280 40" marker-end="url(#sarrow)" stroke="#94a3b8" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="290" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="330" y="45">30</text>
<path d="M 365 40 L 395 40" marker-end="url(#sarrow)" stroke="#94a3b8" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="405" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="445" y="45">40</text>
<path d="M 480 40 L 510 40" marker-end="url(#sarrow)" stroke="#94a3b8" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="520" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="560" y="45">50</text>
<path d="M 30 70 L 30 85" stroke="#f59e0b" stroke-width="2"></path>
<polygon fill="#f59e0b" points="30,90 25,80 35,80"></polygon>
<text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="30" y="98">current</text>
<text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="70" y="85">pos=0 ≠</text>
<defs><marker id="sarrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>
<svg role="img" aria-label="search Step 2: current=node(20), data=20 != target=40, advance to next" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
<rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="20" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
<path d="M 115 40 L 145 40" marker-end="url(#sarrow2)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="155" y="25"></rect>
<text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
<path d="M 250 40 L 280 40" marker-end="url(#sarrow2)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="290" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="330" y="45">30</text>
<path d="M 365 40 L 395 40" marker-end="url(#sarrow2)" stroke="#94a3b8" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="405" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="445" y="45">40</text>
<path d="M 480 40 L 510 40" marker-end="url(#sarrow2)" stroke="#94a3b8" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="520" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="560" y="45">50</text>
<path d="M 165 70 L 165 85" stroke="#f59e0b" stroke-width="2"></path>
<polygon fill="#f59e0b" points="165,90 160,80 170,80"></polygon>
<text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="165" y="98">current</text>
<text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="205" y="85">pos=1 ≠</text>
<defs><marker id="sarrow2" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>
<svg role="img" aria-label="search Step 3: current=node(30), data=30 != target=40, advance to next" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
<rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="20" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
<path d="M 115 40 L 145 40" marker-end="url(#sarrow3)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="155" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
<path d="M 250 40 L 280 40" marker-end="url(#sarrow3)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="290" y="25"></rect>
<text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="330" y="45">30</text>
<path d="M 365 40 L 395 40" marker-end="url(#sarrow3)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1.5" x="405" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="445" y="45">40</text>
<path d="M 480 40 L 510 40" marker-end="url(#sarrow3)" stroke="#94a3b8" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="520" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="560" y="45">50</text>
<path d="M 300 70 L 300 85" stroke="#f59e0b" stroke-width="2"></path>
<polygon fill="#f59e0b" points="300,90 295,80 305,80"></polygon>
<text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="300" y="98">current</text>
<text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="330" y="85">pos=2 ≠</text>
<defs><marker id="sarrow3" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>
<svg role="img" aria-label="search Step 4: current=node(40), data=40 == target=40. Found at position 3. Return 3." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/2000/svg">
<rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="20" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
<path d="M 115 40 L 145 40" marker-end="url(#sarrow4)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="155" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
<path d="M 250 40 L 280 40" marker-end="url(#sarrow4)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="290" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="330" y="45">30</text>
<path d="M 365 40 L 395 40" marker-end="url(#sarrow4)" stroke="#3b82f6" stroke-width="1.5"></path>
<rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="405" y="25"></rect>
<text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="445" y="45">40</text>
<path d="M 480 40 L 510 40" marker-end="url(#sarrow4)" stroke="#94a3b8" stroke-width="1.5"></path>
<rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="520" y="25"></rect>
<text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="560" y="45">50</text>
<path d="M 415 70 L 415 85" stroke="#22c55e" stroke-width="2"></path>
<polygon fill="#22c55e" points="415,90 410,80 420,80"></polygon>
<text fill="#22c55e" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="415" y="98">found</text>
<text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="445" y="85">pos=3 ✓</text>
<defs><marker id="sarrow4" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>
### Returning the Node Instead of the Position
Sometimes you need the node itself — for example, to modify or delete the node after finding it:
```textpython
def search_node(head: Node, target) -> Node | None:
current = head
while current:
if current.data == target:
return current
current = current.next
return None
```text
`current = head` — start at the first node.
`while current:` — continue until `current` is `None`.
`if current.data == target:` — match found. Return the node itself, not the position.
`current = current.next` — advance to the next node.
`return None` — the target was not in any node. Return `None` instead of -1, since the return type is a node reference.
Returns `None` instead of -1 when the target is not found. Worth keeping both versions — position for reporting, node for manipulation.
**Time:** O(n). **Space:** O(1).
## Why Binary Search Does Not Apply
Binary search eliminates half the remaining elements each iteration by computing the midpoint: `mid = (left + right) // 2`. That computation is O(1) for an array. For a linked list, reaching the midpoint requires traversing n/2 nodes. The first midpoint traversal alone is O(n), which is the same as linear search. Repeating it log n times makes binary search O(n log n) on a linked list — strictly worse than linear search's O(n).
Direct array access at `arr[mid]` is the enabling operation. Without it, binary search does not work.
## Why You Cannot Do Better
Linked lists do not support binary search because they do not support random access. This is not a limitation of the algorithm — it is a property of the data structure. The "search in a linked list" problem is O(n) by definition. If you are writing a search-heavy system and reach for a linked list, that is the red flag: the search cost will dominate.
Linked lists are for insert-heavy workloads at known positions. If you need fast search, use a hash set (O(1) average) or a sorted array with binary search (O(log n)).
The linear search walk across nodes is the same pattern that makes other pointer-based traversals expensive — graph DFS, tree in-order traversal, and collision chain walking in hash tables all share this cost structure. Knowing when the walk is the bottleneck, and when it is acceptable, is what separates good data structure choices from bad ones.