What Is an Iterator? The Lazy Sequence Every Language Runs On

Every for loop has a contract. It silently asks the collection: "do you have a next value?" The collection hands one back. The loop asks again. Eventually the answer is no, and the loop ends. That silent back-and-forth is an iterator, and understanding it sharpens how you think about memory, lazy evaluation, and API design.

The Problem Iterators Solve

Imagine reading a log file with a billion lines. The naive approach loads everything into a list first. Your laptop fan spins up like a turbine. Your RAM fills. You haven't processed a single line yet. That's O(n) space consumed before you've done anything useful.

An iterator avoids this by handing you one element at a time, on demand, without materializing the full collection. The file stays on disk. The network stream stays in the socket buffer. The Fibonacci sequence can run forever without overflowing memory, because no one ever stores all of it.

An iterator is a stateful cursor, not a data structure. It knows where it is and how to get the next thing. That's all.

What Is an Iterator?

An iterator satisfies two operations:

1. "Give me the next value." Advance the cursor and return what it was pointing at.
2. "Are there more values?" Or: signal exhaustion by returning a sentinel like None or raising an exception.

Different languages spell these differently. Python uses __next__() raising StopIteration. Rust uses next() returning Option<T>. Java uses hasNext() plus next(). C++ uses pointer-like increment and dereference operators.

An iterator is a protocol, not a class you inherit from. Satisfy the protocol, and the language's for machinery drives it.

Iterator vs Iterable: The Distinction That Trips Everyone

These two words sound interchangeable. They aren't. Most Python tutorials online use them wrong, which explains a lot about certain Stack Overflow answers.

An iterable is something you can iterate over: a list, a string, a tree, a database cursor. It knows how to produce an iterator. In Python, that's __iter__(). In Java, it's Iterable<T> with an iterator() method.

An iterator is the cursor itself. It holds position and produces values.

A list is iterable but not an iterator. You can loop over a list multiple times because iter(list) creates a fresh cursor each time. A file object in Python is both: it's its own iterator, so you can only traverse it once. Once EOF, it's done.

That distinction matters in interviews when you're asked to design a class that supports for loops but also needs to be reset or cloned.

Lazy Is the Right Default

The key property of iterators is laziness. Values are computed only when requested.

# This never allocates a list of 10 billion integers
big = range(10_000_000_000)
first_ten = [next(iter(big)) for _ in range(10)]

Generators push this further: yield suspends execution mid-function, resuming on the next next() call.

def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

fib = fibonacci()
print(next(fib))  # 0
print(next(fib))  # 1
print(next(fib))  # 1
print(next(fib))  # 2

This produces an infinite sequence in O(1) space. A list of Fibonacci numbers would eventually exhaust RAM. The infinite loop is not a bug. It's the point.

Running forever was the goal all along.

Time and Space Complexity

Iterator-based traversal uses O(1) extra space, regardless of collection size. The one caveat: iterators that buffer internally (like a sorted merge over k sorted streams) hold O(k) state. Read the implementation, not the interface.

Where Iterators Show Up in Coding Interviews

Iterator design is a distinct problem category, most common at Google, Meta, and fintech firms that value OOP and API design.

LeetCode 284, Peeking Iterator: Wrap an existing iterator and add a peek() method. Requires caching one element. The trick: peek() must eagerly call next() on the underlying iterator and store the result, so the subsequent next() call returns the cached value instead of advancing again.

LeetCode 341, Flatten Nested List Iterator: Given a NestedInteger interface that holds either an integer or a list of NestedIntegers, implement a flat iterator. Most people's first instinct is to flatten everything in the constructor. Resist that. The clean solution uses an explicit stack mirroring iterative DFS, stays lazy, and handles arbitrarily deep nesting.

LeetCode 604 / 900, RLE Iterators: Lazy decoding of run-length encoded sequences. Tests stateful traversal with a mutable pointer into a consumed sequence.

The pattern across all of these: iterators hold mutable state, and that state must be updated correctly across every code path. One missed update in peek() causes next() to return the wrong element. Track where the cursor is after every operation.

One Structure, Every Language

A custom range iterator: counts from start to stop (exclusive), O(1) space.

class CountUp:
    def __init__(self, start: int, stop: int) -> None:
        self.current = start
        self.stop = stop

    def __iter__(self):
        return self

    def __next__(self) -> int:
        if self.current >= self.stop:
            raise StopIteration
        value = self.current
        self.current += 1
        return value

for n in CountUp(1, 4):
    print(n)  # 1, 2, 3

Key Takeaways

• An iterator is a stateful cursor, not a data type. It's a protocol. Satisfy it and the for loop machinery takes over.
• An iterable produces iterators. An iterator advances through a sequence. One class can be both, or they can be separate.
• Lazy iteration is O(1) space per element regardless of collection size. For streams, files, and infinite sequences, that difference is everything.
• In interviews, iterator problems test state management under API constraints. Track the cursor position after every operation: peek(), skip(), and hasNext() all mutate or expose state.
• Practice explaining state transitions out loud at SpaceComplexity. That's the part text-based practice can't train.

Further Reading

• Iterator, Wikipedia
• Python Iterator Types, Python 3 Documentation
• Iterator, Java SE Documentation
• Iteration Protocols, MDN Web Docs
• std::iter::Iterator, Rust Standard Library
• Range Over Function Types, The Go Blog