Linked List Traversal and Search in Python

Almost every linked list operation starts the same way: park a pointer on the head and keep moving it to node.next. Insert, delete, reverse, find the middle, detect a cycle, they are all a traversal with something extra inside the loop. Getting the loop's stop condition right is most of the difficulty. This article covers the handful of loop shapes, what each one stops on, and what searching really costs.

The problem it solves

A linked list gives you exactly one door: the head. There is no list[i], no length field unless you keep one, and no way to jump. To find a value, count the nodes, reach the last node or find the node before a target, you walk.

How nodes and links are built, and why reaching item k costs k hops, is in the singly linked list article. Here the focus is the walk itself: which loop condition to write, and how many nodes each search touches.

The intuition

There are three loop conditions, and each answers a different question.

• while node is not None visits every node, including the last, and ends with node equal to None. Use it to search, count or print. After the loop you have no node in hand, which is fine for a search that returns from inside.
• while node.next is not None stops on the last node instead of falling off it. Use it to reach the tail, for example to append without a tail pointer. It crashes on an empty list unless you check the head first.
• while node.next is not None and node.next.value != target looks one step ahead and stops before the match. That predecessor is what deletion and insertion need, since a singly linked node cannot reach back.

Searching is the first loop with a comparison inside. A hit at index i costs i + 1 comparisons, so averaged over every position a successful search costs (n + 1) / 2. A miss costs all n, because nothing short of the end proves the value is absent. If the list is sorted, a miss can stop early at the first larger value, but it still cannot skip ahead.

That is also why binary search does not help. Binary search is fast because reaching the middle of an array is one step. In a linked list, reaching the middle is already n / 2 hops, so halving saves nothing.

Watch it run

The animation walks the lesson's three-node list: 4, 8, 15. Traversal is one pointer and one rule: keep reassigning it to node.next until it falls off the end. First, find(head, 15). 4 is not 15, and the only move available is node = node.next. 8 is not 15 either. Then node.value == 15, so the search returns index 2, after two hops.

Why no binary search? Jumping to the middle already costs a walk, so halving buys nothing. Now the miss, find(head, 9): the same walk, with no early exit available. 4, 8 and 15 are each not 9, so keep walking; a miss has to touch every node. After the third hop, node is now None, shown as ∅. That is the list's built-in stop sign, and the loop returns −1. Best case is a hit on the head, O(1); worst case is the whole chain, O(n). Nothing lets the walk skip ahead.

The code

The lesson's search, a search by condition that returns the node itself, the look-ahead predecessor, and the last node, with every value comparison counted:

import random

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

checks = 0                                 # value comparisons, counted for the table below

def find(head, target):                    # the lesson's search: index or -1
    global checks
    node, index = head, 0
    while node is not None:                # stop sign: the tail's next is None
        checks += 1
        if node.value == target:
            return index
        node, index = node.next, index + 1
    return -1

def first_where(head, test):               # search by condition, return the node itself
    node = head
    while node is not None and not test(node.value):
        node = node.next
    return node                            # None means no match

def node_before(head, target):             # look one ahead: the shape delete needs
    if head is None or head.value == target:
        return None                        # no predecessor to return
    node = head
    while node.next is not None and node.next.value != target:
        node = node.next
    return node if node.next is not None else None

def last(head):                            # `while node.next`, not `while node`
    node = head
    while node is not None and node.next is not None:
        node = node.next
    return node

head = build([4, 8, 15, 16, 23])
print(find(head, 15), find(head, 9))                  # 2 -1
print(first_where(head, lambda v: v % 2 == 1).value)  # 15
print(node_before(head, 16).value, last(head).value)  # 15 23

checks = 0
for v in [4, 8, 15, 16, 23]:
    find(head, v)
print(checks, checks / 5)                  # 15 3.0  -> (n + 1) / 2 per hit
checks = 0
find(head, 42)
print(checks)                              # 5  -> a miss reads every node

Five hits cost 1 + 2 + 3 + 4 + 5 = 15 comparisons, an average of 3 = (5 + 1) / 2. The miss costs 5.

The seeded check: 3,000 random lists with duplicates, each compared against a plain Python list. find must match list.index (or −1) and make exactly index + 1 comparisons on a hit and n on a miss; first_where must find the first odd value; node_before must sit exactly one position before the first match; last must hold the final value:

def position(head, target_node):
    node, i = head, 0
    while node is not target_node:
        node, i = node.next, i + 1
    return i

rng = random.Random(39)
ok = True
for _ in range(3000):
    values = [rng.randint(0, 9) for _ in range(rng.randint(0, 12))]
    head, t = build(values), rng.randint(0, 9)
    checks = 0
    got = find(head, t)
    want = values.index(t) if t in values else -1          # brute force: Python's own list
    ok &= got == want and checks == (want + 1 if want >= 0 else len(values))
    odd = first_where(head, lambda v: v % 2 == 1)
    ok &= (odd.value if odd else None) == next((v for v in values if v % 2 == 1), None)
    before = node_before(head, t)
    if want > 0:
        ok &= position(head, before) == want - 1 and before.next.value == t
    else:
        ok &= before is None
    ok &= (last(head).value if values else None) == (values[-1] if values else None)
print(ok)                                  # True

The complexity

• Traversal: O(n) time, O(1) extra space: one pointer and maybe a counter.
• Search: O(1) best case (the head), O(n) worst case and on every miss, (n + 1) / 2 comparisons on an average hit.
• Predecessor and tail: O(n) each, which is why lists that append often keep a tail pointer. The Big-O cheat sheet lists the linked list operations side by side.

Where it goes wrong

• while node.next on an empty list. None.next raises AttributeError; check the head first.
• Losing the head. Walk with a separate variable; reassigning head itself makes the front of the list unreachable.
• Stopping on the match when you needed the node before it. For deletion, compare node.next.value, as in insertion and deletion.
• A cycle. while node never ends on a list whose tail points back inside. Detect it with Floyd's fast and slow pointers before walking untrusted input.
• Expecting binary search to help on sorted data. It cannot; sort order only lets a miss stop early.

When it shows up in interviews

As a warm-up ("search a linked list", "return the length"), as the first step of nearly every list problem, and as a theory question: "why can't you binary search a linked list?" The predecessor loop is the core of "remove all nodes with value x" and of most insertion problems.

How to say it in an interview

"I walk with a separate pointer, starting at the head and moving to next until it is None, so the head stays intact. Search is that loop with a comparison: a hit at index i costs i + 1 checks, about n / 2 on average, and a miss always costs n. If I need the node before a match, for deletion, I compare node.next.value instead. Binary search doesn't help, because reaching the middle already costs n / 2 hops."