Iterator pattern in LLD - System Design Exercise

Design: Iterator Pattern Implementation

Design the iterator pattern focusing on the interface and interaction with collections. Implementation details of collections themselves are out of scope except for demonstration.

Functional Requirements

FR1: Provide a way to access elements of a collection sequentially without exposing its underlying representation

FR2: Support multiple types of collections (e.g., lists, trees, graphs)

FR3: Allow multiple iterators to traverse the same collection independently

FR4: Support forward traversal at minimum; optional support for backward traversal

FR5: Ensure the iterator interface is simple and consistent across collection types

Non-Functional Requirements

NFR1: Iterator operations should have O(1) time complexity where possible

NFR2: Memory overhead should be minimal and proportional to the number of active iterators

NFR3: The design should be extensible to support new collection types without modifying existing code

NFR4: Thread safety is not required in the initial design

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Iterator interface defining traversal methods

Concrete iterator implementations for each collection type

Aggregate interface representing collections that can create iterators

Concrete aggregate implementations (e.g., List, Tree)

Client code that uses iterators to traverse collections

Design Patterns

Iterator pattern for traversal abstraction

Composite pattern if collections are hierarchical (like trees)

Factory method pattern for creating iterators

Decorator pattern if adding extra behavior to iterators

Reference Architecture

Client
  |
  v
Aggregate Interface <---- Concrete Aggregates (List, Tree)
  |
  v
Iterator Interface <---- Concrete Iterators (ListIterator, TreeIterator)

Components

Iterator Interface

Abstract Interface

Defines methods like next(), hasNext() to traverse elements

Concrete Iterator

Class implementing Iterator Interface

Implements traversal logic specific to a collection type

Aggregate Interface

Abstract Interface

Defines method to create an iterator for the collection

Concrete Aggregate

Class implementing Aggregate Interface

Represents a collection and returns its iterator

Client

Application code

Uses iterator interface to traverse collections without knowing their structure

Request Flow

1. Client requests an iterator from a collection (Aggregate)

2. Collection returns a Concrete Iterator instance

3. Client uses iterator's hasNext() and next() methods to access elements sequentially

4. Iterator internally manages traversal state without exposing collection structure

5. Client completes traversal or stops early without affecting collection

Database Schema

Not applicable for Iterator pattern as it is a behavioral design pattern focusing on object interaction rather than data storage.

Scaling Discussion

Bottlenecks

Multiple iterators on large collections may increase memory usage

Complex collections like trees may have more complex iterator logic affecting performance

If collections are modified during iteration, iterator consistency can break

Supporting backward traversal or random access may complicate iterator design

Solutions

Use lightweight iterator objects and share immutable state where possible

Optimize traversal algorithms for complex collections

Implement fail-fast or fail-safe iterators to handle concurrent modifications

Design separate iterator interfaces for different traversal capabilities (forward, backward)

Interview Tips

Time: Spend 10 minutes explaining the problem and requirements, 15 minutes designing interfaces and classes, 10 minutes discussing scaling and extensions, and 10 minutes answering questions.

Explain the need to separate traversal from collection structure

Describe how the iterator interface provides a uniform way to access elements

Show how multiple iterators can work independently on the same collection

Discuss trade-offs between simplicity and supporting advanced traversal features

Mention how the pattern improves code maintainability and extensibility