3.18 Iterators

An iterator is an object or procedure that visits the nodes of a linked list one at a time. It separates traversal from the operation applied to each node. This separation is useful because many list algorithms have the same walking pattern but different processing logic.

Problem

You need to scan a linked list without exposing every detail of pointer movement to the caller.

Typical uses include:

print every value
find a value
count nodes
copy nodes
filter nodes
apply a function to each node

A direct traversal is simple, but repeated traversal code creates duplication and makes it easier to introduce inconsistent edge-case handling.

Basic External Iterator

An external iterator stores the current node and advances on request.

Iterator {
  cur : Node | null
}

Initialization:

iter = Iterator(head)

Next operation:

next(iter):
  if iter.cur == null:
    return none

  value = iter.cur.value
  iter.cur = iter.cur.next
  return some(value)

The caller controls the loop.

while true:
  item = next(iter)
  if item is none:
    break
  process(item.value)

This style is useful when traversal must pause and resume.

Internal Iterator

An internal iterator takes a function and applies it to each node.

for_each(head, visit):
  cur = head

  while cur != null:
    visit(cur.value)
    cur = cur.next

The caller supplies behavior, while the iterator controls traversal.

for_each(head, print)

This style is compact but less flexible when the caller needs early exit, mutation, or interleaving with other traversals.

Iterator Invariant

For a simple forward iterator:

cur points to the next node that has not yet been yielded

After next(iter) returns a value, cur advances to the following node. When cur = null, the iterator is exhausted.

Iterator with Node Access

Sometimes the caller needs the node, not only the value.

next_node(iter):
  if iter.cur == null:
    return null

  node = iter.cur
  iter.cur = iter.cur.next
  return node

This is useful for algorithms that inspect identity, compare pointers, or move nodes between lists.

The danger is that callers can mutate node.next, which may invalidate the iterator’s assumptions. The iterator must advance before returning the node if mutation is allowed.

Safe Mutation During Iteration

If the current node may be removed or moved, save the successor before exposing or mutating the node.

cur = head

while cur != null:
  next = cur.next

  if should_remove(cur):
    remove(cur)

  cur = next

This pattern protects traversal from changes to cur.next.

Removing While Iterating

For a singly linked list, deletion requires a predecessor. A mutation-aware iterator can store both prev and cur.

Iterator {
  prev : Node
  cur  : Node | null
}

Using a dummy node:

dummy.next = head
iter.prev = dummy
iter.cur = head

Remove current:

remove_current(iter):
  if iter.cur == null:
    return

  node = iter.cur
  iter.prev.next = node.next
  iter.cur = node.next
  node.next = null

Advance without removing:

advance(iter):
  if iter.cur != null:
    iter.prev = iter.cur
    iter.cur = iter.cur.next

The invariant is:

iter.prev.next == iter.cur

This is the same invariant used in deletion patterns.

Iterating Two Lists Together

Some algorithms compare or combine two lists.

p = l1
q = l2

while p != null and q != null:
  process(p.value, q.value)
  p = p.next
  q = q.next

This appears in equality checking, pairwise merge, vector-like operations, and zip logic.

If the lists may have unequal length, handle the remainder explicitly.

while p != null:
  process_left_remainder(p.value)
  p = p.next

while q != null:
  process_right_remainder(q.value)
  q = q.next

Iterator Invalidity

An iterator becomes invalid when the structure it depends on changes in a way it cannot track.

Examples:

the current node is deleted elsewhere
the next pointer is changed before the iterator reads it
the list is reversed during traversal
the list is destroyed

Some systems define precise invalidation rules. Others leave the behavior undefined. In either case, linked list iterators are safer when mutation happens through the iterator itself.

Snapshot Iteration

A snapshot iterator preserves the sequence as it existed when iteration began. For a mutable linked list, true snapshot behavior usually requires copying nodes or storing references to all nodes in an array.

snapshot = []

cur = head
while cur != null:
  snapshot.append(cur)
  cur = cur.next

Then iterate over snapshot.

This uses O(n) extra space but isolates iteration from later structural changes.

Lazy Iteration

A lazy iterator produces one value at a time and does not scan the whole list upfront. The basic external iterator is lazy.

Lazy iteration uses O(1) extra space and supports large lists. It also means that structural mutation during iteration can affect future results.

Complexity Summary

Common Failure Modes

A common error is removing the current node and then advancing through cur.next. If the node has been detached or freed, cur.next may be invalid. Save next first or let the iterator update itself during removal.

Another error is exposing nodes while assuming callers will not mutate them. If mutation is allowed, the iterator should either document invalidation rules or advance before returning the node.

A third error is using value equality where node identity is needed. Iterators over linked lists often need to reason about nodes, not just values.

Key Insight

An iterator packages traversal state. For a read-only list, this state can be just the current node. For a mutable list, the iterator must also protect the next step, often by storing a predecessor or saving the successor before mutation. The design goal is to make the traversal invariant explicit instead of duplicating fragile pointer movement throughout the program.