Skip to content
BytePatterns

Traversal and Search

Linked Lists: lesson 2 of 6

One node at a time is the only way through.

Lesson 2 of 6 · 4 min

Traversal and Search

Step 1 of 11

Traversal is one pointer and one rule: keep reassigning it to node.next until it falls off the end.

The Idea

Traversal means parking a pointer on the head and reassigning it to current.next until it falls off the end. Searching is traversal with a comparison inside. Both are O(n), and neither can skip ahead.

Real-World Example

A museum audio tour numbers its stations, but each recording only ends with "now walk to the next stop." There is no map in your hand, so hearing station twelve means standing through the eleven before it, in order.

The Code

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

def find(head, target):
    node, index = head, 0
    while node is not None:        # walk until the chain ends
        if node.value == target:
            return index
        node = node.next           # hop to the next node
        index += 1
    return -1                      # target is not in the list

head = Node(4); head.next = Node(8); head.next.next = Node(15)
print(find(head, 15))              # 2
print(find(head, 9))               # -1

Your turn

Put the steps in the right order.

  1. Move current on to current.next
  2. Point current at the head node
  3. Compare current.value with the target
  4. Stop once current is None and report a miss

Mini quiz

1 / 3

Why can't a linked list use binary search?