Iterator pattern in LLD - System Design Guide

Problem Statement

When a collection's internal structure is exposed directly, clients can accidentally modify it or become tightly coupled to its implementation. This makes the code fragile and hard to maintain, especially when the collection changes internally.

Solution

The iterator pattern provides a way to access elements of a collection sequentially without exposing its underlying representation. It defines a separate iterator object that handles traversal, allowing clients to iterate safely and uniformly over different collection types.

Architecture

┌───────────────┐       ┌───────────────┐       ┌───────────────┐
│   Client      │──────▶│   Iterator    │──────▶│   Collection  │
│ (uses next()) │       │ (next(), hasNext())│   │ (data storage)│
└───────────────┘       └───────────────┘       └───────────────┘

This diagram shows the client using an iterator to traverse a collection without accessing its internal structure directly.

Trade-offs

✓ Pros

→

Encapsulates traversal logic, keeping collection implementation hidden.

→

Supports multiple traversal algorithms without changing the collection.

→

Simplifies client code by providing a uniform interface for iteration.

✗ Cons

→

Adds extra classes and objects, increasing code complexity.

→

May introduce slight performance overhead due to additional abstraction.

→

Requires careful design to handle concurrent modifications safely.

Use when you need to traverse different types of collections uniformly or want to hide the internal structure of collections from clients.

Avoid when collections are simple and direct access is sufficient, or when performance is critical and the overhead of iterator objects is unacceptable.

Real World Examples

Java (Oracle)

Java's Collection Framework uses the Iterator pattern to allow clients to traverse lists, sets, and other collections uniformly without exposing internal data structures.

Python

Python's iterator protocol enables for-loops to traverse various data types like lists, tuples, and generators without exposing their internal implementations.

C++ (STL)

The Standard Template Library uses iterators to provide a common interface for traversing containers like vectors, lists, and maps.

Code Example

Before applying the Iterator pattern, the client accesses the collection's internal list directly, which couples client code to the data structure. After applying the pattern, the Numbers class provides an iterator object that handles traversal, allowing the client to iterate without knowing the internal details.

LLD

### Before (without Iterator pattern):
class Numbers:
    def __init__(self):
        self.data = [1, 2, 3, 4, 5]

# Client accesses internal data directly
nums = Numbers()
for i in range(len(nums.data)):
    print(nums.data[i])


### After (with Iterator pattern):
class Numbers:
    def __init__(self):
        self.data = [1, 2, 3, 4, 5]

    def __iter__(self):
        return NumbersIterator(self.data)

class NumbersIterator:
    def __init__(self, data):
        self._data = data
        self._index = 0

    def __next__(self):
        if self._index < len(self._data):
            result = self._data[self._index]
            self._index += 1
            return result
        else:
            raise StopIteration

    def __iter__(self):
        return self

# Client uses iterator without accessing internal data
nums = Numbers()
for num in nums:
    print(num)

Alternatives

Cursor

Cursor exposes the position within the collection and allows modification during traversal, unlike Iterator which focuses on read-only traversal.

Use when: Choose Cursor when you need to modify the collection during iteration.

Enumeration

Enumeration is an older pattern that only supports forward traversal and lacks removal capability, unlike Iterator which supports more operations.

Use when: Choose Enumeration only for legacy systems requiring simple forward traversal.

Summary

The Iterator pattern separates traversal logic from the collection, hiding internal structure.

It provides a uniform way to access elements sequentially across different collection types.

This pattern improves code maintainability and flexibility by decoupling clients from data storage details.

Practice

1.

What is the main purpose of the Iterator pattern in system design?

easy

A. To manage user authentication and authorization

B. To store data in a database efficiently

C. To create multiple copies of an object

D. To provide a way to access elements of a collection sequentially without exposing its underlying structure

Solution

1. Step 1: Understand the role of Iterator pattern

   The Iterator pattern is designed to provide a way to access elements of a collection one by one without revealing the internal structure of the collection.

2. Step 2: Compare with other options

   Options B, C, and D describe unrelated design patterns or system functions such as data storage, object cloning, and security management.

3. Final Answer:

   To provide a way to access elements of a collection sequentially without exposing its underlying structure -> Option D

4. Quick Check:

   Iterator pattern = Access collection without exposing structure [OK]

Hint: Iterator = access elements without showing internal details [OK]

Common Mistakes:

• Confusing Iterator with data storage or cloning patterns
• Thinking Iterator manages security or authentication
• Assuming Iterator modifies the collection

2.

Which of the following is the correct method signature for the next() method in an iterator interface?

easy

A. def next() -> void

B. def next(self, index) -> Element

C. def next(self) -> Element

D. def next(self, element) -> bool

Solution

1. Step 1: Recall the standard iterator method signature

   The next() method typically takes no parameters except the implicit self and returns the next element in the collection.

2. Step 2: Analyze each option

   def next(self) -> Element matches the standard signature: it takes self and returns an element. Options B and D incorrectly add parameters, and C returns void which is incorrect.

3. Final Answer:

   def next(self) -> Element -> Option C

4. Quick Check:

   next() takes no args, returns element [OK]

Hint: next() returns next element, no extra parameters [OK]

Common Mistakes:

• Adding parameters to next() method
• Returning void instead of element
• Confusing next() with hasNext() method

3.

Consider the following Python code implementing a simple iterator:

class MyIterator:
    def __init__(self, data):
        self.data = data
        self.index = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.index < len(self.data):
            result = self.data[self.index]
            self.index += 1
            return result
        else:
            raise StopIteration

it = MyIterator([10, 20, 30])
print(next(it))
print(next(it))

What will be the output?

medium

A. 20\n30

B. 10\n20

C. 10\n30

D. Error at runtime

Solution

1. Step 1: Trace the iterator's next calls

   First call to next(it) returns data[0] = 10 and increments index to 1. Second call returns data[1] = 20 and increments index to 2.

2. Step 2: Confirm no errors occur

   Since index is less than length during both calls, no StopIteration is raised.

3. Final Answer:

   10 20 -> Option B

4. Quick Check:

   First two elements printed: 10 and 20 [OK]

Hint: next() returns elements in order, increments index [OK]

Common Mistakes:

• Assuming next() skips elements
• Expecting error before StopIteration
• Mixing up index increments

4.

Given this iterator implementation in Python, identify the bug:

class BuggyIterator:
    def __init__(self, data):
        self.data = data
        self.index = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.index <= len(self.data):
            result = self.data[self.index]
            self.index += 1
            return result
        else:
            raise StopIteration

What is the cause of the error when iterating?

medium

A. IndexError due to accessing out-of-range element

B. StopIteration raised too early

C. Infinite loop because index never increments

D. Syntax error in method definitions

Solution

1. Step 1: Analyze the condition in __next__

   The condition uses <= len(self.data), which allows index to equal length, causing out-of-range access.

2. Step 2: Understand the error caused

   Accessing self.data[self.index] when index == len(self.data) causes IndexError because list indices go from 0 to len-1.

3. Final Answer:

   IndexError due to accessing out-of-range element -> Option A

4. Quick Check:

   Condition allows index == length causing IndexError [OK]

Hint: Use < not <= to avoid out-of-range errors [OK]

Common Mistakes:

• Using <= instead of < in boundary check
• Assuming StopIteration triggers before error
• Ignoring index increment effects

5.

You need to design an iterator for a complex data structure that contains nested lists of integers. Which approach best follows the Iterator pattern principles to allow clients to iterate over all integers seamlessly?

1. Flatten the nested lists into a single list before iteration.
2. Implement a recursive iterator that yields integers from nested lists on demand.
3. Expose the internal nested list structure and let clients handle iteration.
4. Provide separate iterators for each nested list and require clients to manage them.

hard

A. Implement a recursive iterator that yields integers from nested lists on demand

B. Flatten the nested lists into a single list before iteration

C. Expose the internal nested list structure and let clients handle iteration

D. Provide separate iterators for each nested list and require clients to manage them

Solution

1. Step 1: Understand Iterator pattern goal

   The pattern aims to hide internal structure and provide a simple way to access elements sequentially.

2. Step 2: Evaluate each approach

   Flatten the nested lists into a single list before iteration flattens data upfront, which may be inefficient and breaks lazy access. Implement a recursive iterator that yields integers from nested lists on demand uses a recursive iterator to yield elements on demand, hiding complexity and supporting lazy iteration. Options C and D expose internal structure or complexity to clients, violating encapsulation.

3. Final Answer:

   Implement a recursive iterator that yields integers from nested lists on demand -> Option A

4. Quick Check:

   Recursive iterator hides structure, yields elements lazily [OK]

Hint: Use recursive iterator to hide nested structure [OK]

Common Mistakes:

• Flattening data upfront losing lazy iteration benefits
• Exposing internal structure breaking encapsulation
• Forcing clients to manage multiple iterators