skip to content

Write a custom type that supports `for`-in by implementing the iterator protocol, and explain where the traversal state lives.

level: middleimportance: should knowfreq 55%

answer

  1. iterator() returns a fresh cursor each call
  2. state lives in the iterator, not the source
  3. hasNext() is side-effect-free; next() advances
  4. implement Iterable<T> to inherit map/filter/etc.
  5. iterator { yield(...) } builder for lazy traversal

basics

~20 s

Add an operator fun iterator() that returns an object tracking a position. That object's hasNext() checks if more items remain and next() returns the current item and moves forward. The position lives in the iterator, not the collection.

solid answer

~40 s

To make a type loop-able, provide `operator fun iterator(): Iterator<T>`. The returned `Iterator` holds the **cursor** — the current index or node — so the source object itself stays immutable and re-iterable. Each `for` loop calls `iterator()` once, getting a fresh cursor at the start; calling it again yields an independent traversal. `hasNext()` must not advance state (it only peeks); `next()` returns the current element and advances. If you implement `Iterable<T>` (rather than just the operator), you also inherit all stdlib operators (`map`, `filter`, etc.). For a binary tree or graph you'd typically buffer the traversal order or use a stack inside the iterator. A common pitfall is making the iterator share mutable state with the source (e.g., a single shared cursor field), which breaks nested loops over the same instance.

code

kotlin · 12 lines
kotlin
class IntRangeStep(val from: Int, val to: Int, val step: Int) : Iterable<Int> {
    override fun iterator() = object : Iterator<Int> {
        var cur = from
        override fun hasNext() = cur <= to
        override fun next(): Int {
            if (!hasNext()) throw NoSuchElementException()
            return cur.also { cur += step }
        }
    }
}

for (i in IntRangeStep(0, 10, 3)) print("$i ") // 0 3 6 9

go deeper

for a junior

Can write a basic index-based iterator() with hasNext()/next().

for a middle

Places state correctly in the iterator, handles exhaustion, and knows implementing Iterable unlocks stdlib operators.

for a senior

Reasons about re-iteration/nesting, side-effect-free hasNext(), and uses the iterator { yield } builder for complex traversals.

for a principal

Designs iteration APIs for tree/graph/lazy sources, considers thread-safety, fail-fast semantics, and when to expose Sequence vs Iterable.

## Two ways to be loop-able 1. **Operator convention only** — define `operator fun iterator()`. Enough for `for`-in. 2. **Implement `Iterable<T>`** — gives you `for`-in *and* every stdlib extension (`map`, `filter`, `count`, `forEach`, `joinToString`, …). Prefer implementing `Iterable<T>` for collection-like types. ## The iterator owns the state The **source** (collection) describes the data; the **iterator** describes a *position* into it. Keeping the cursor in the iterator (not the source) means: - The source stays immutable and thread-shareable. - Calling `iterator()` twice gives two independent walks — needed for nested loops over the same object. - `hasNext()` is a pure check; only `next()` mutates the cursor. ```kotlin class Ring<T>(private val items: List<T>, private val start: Int) : Iterable<T> { override fun iterator(): Iterator<T> = object : Iterator<T> { private var seen = 0 private var idx = start override fun hasNext(): Boolean = seen < items.size override fun next(): T { if (!hasNext()) throw NoSuchElementException() val v = items[idx] idx = (idx + 1) % items.size seen++ return v } } } ``` Because `seen`/`idx` live in the anonymous object, two concurrent `for` loops over the same `Ring` don't interfere. ## Tree / lazy traversal pattern For structures without a flat index, hold a stack or precomputed order in the iterator: ```kotlin class Node(val value: Int, val children: List<Node> = emptyList()) : Iterable<Int> { override fun iterator(): Iterator<Int> = iterator { // stdlib coroutine-based builder suspend fun SequenceScope<Int>.walk(n: Node) { yield(n.value) n.children.forEach { walk(it) } } walk(this@Node) } } ``` The stdlib `iterator { yield(...) }` builder uses restricted suspension to produce a lazy `Iterator<T>` without manual state machines. ## Contract details to respect - `next()` after exhaustion should throw `NoSuchElementException`. - `hasNext()` must be **idempotent** and side-effect-free. - Don't leak source mutability into the iterator (e.g., shared single cursor) — that breaks re-iteration and nesting.

  • Why shouldn't the cursor be a field on the source collection itself?
    A shared cursor makes the collection single-use and breaks nested or concurrent iteration over the same instance. Each `iterator()` call must yield an independent position.
  • How can you build an iterator lazily without writing a manual state machine?
    Use the stdlib `iterator { ... yield(x) ... }` builder (or `sequence { }` for a Sequence). It compiles your suspending block into an on-demand iterator/sequence.

saying these in an interview costs you the question

  • Storing the cursor in the collection so it can only be iterated once
  • Mutating state inside `hasNext()`
  • Forgetting `NoSuchElementException` on exhausted `next()`
  • Returning the same iterator instance from every `iterator()` call
  • Confusing `Iterable` (re-iterable) with `Iterator` (one-shot)

context

resolving links…