# 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:

```text id="e2k7m1"
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.

```text id="p9v4r6"
Iterator {
  cur : Node | null
}
```

Initialization:

```text id="d5m8q2"
iter = Iterator(head)
```

Next operation:

```text id="x3n7c9"
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.

```text id="h8q1z5"
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.

```text id="r6t9k2"
for_each(head, visit):
  cur = head

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

The caller supplies behavior, while the iterator controls traversal.

```text id="z1w7c4"
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:

```text id="k4h2q8"
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.

```text id="x9b5m7"
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.

```text id="c7v2n6"
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`.

```text id="t3m9p1"
Iterator {
  prev : Node
  cur  : Node | null
}
```

Using a dummy node:

```text id="f8q6d4"
dummy.next = head
iter.prev = dummy
iter.cur = head
```

Remove current:

```text id="q2r8x6"
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:

```text id="m5w1z9"
advance(iter):
  if iter.cur != null:
    iter.prev = iter.cur
    iter.cur = iter.cur.next
```

The invariant is:

```text id="v7n4k3"
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.

```text id="g6y4c2"
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.

```text id="y9d8v1"
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:

```text id="s5n3h8"
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.

```text id="k1c6p7"
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

| Iterator pattern        |    Time per step | Extra space |
| ----------------------- | ---------------: | ----------: |
| Forward value iterator  |             O(1) |        O(1) |
| Forward node iterator   |             O(1) |        O(1) |
| Mutation-aware iterator |             O(1) |        O(1) |
| Two-list iterator       |             O(1) |        O(1) |
| Snapshot iterator       | O(1) after setup |        O(n) |
| Snapshot setup          |             O(n) |        O(n) |

## 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.