Flatten Nested List iterator

XXX. Nested Iterator

Iterator

Stack

Problem Statement:

Implement an iterator for a nested list structure where each element is either an integer or a list of nested integers.

• Must implement hasNext() and next()
• Elements must be returned in flattened order
• Should follow standard Iterator pattern

Implementation 1 (hasNext in next):

public class NestedIterator implements Iterator {
    private Stack stack;

    public NestedIterator(List nestedList) {
        stack = new Stack<>();
        flattenList(nestedList);
    }

    @Override
    public Integer next() {
        return hasNext() ? stack.pop().getInteger() : null;
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            if (stack.peek().isInteger()) return true;
            flattenList(stack.pop().getList());
        }
        return false;
    }

    // Push items in reverse order for correct processing
    private void flattenList(List list) {
        for (int i = list.size() - 1; i >= 0; i--) 
            stack.push(list.get(i));
    }
}

Implementation 2 (Standard Iterator Pattern):

class NestedIterator2 implements Iterator {
    private Stack stack;

    public NestedIterator2(List nestedList) {
        stack = new Stack<>();
        enstack(nestedList);
    }
    
    private void enstack(List list) {        
        for (int i = list.size() - 1; i >= 0; i--) 
            stack.push(list.get(i));
        
        // Ensure top of stack is always an integer
        while (!stack.isEmpty() && !stack.peek().isInteger()) 
            enstack(stack.pop().getList());
    }

    @Override
    public Integer next() {
        Integer res = stack.pop().getInteger();
        // Prepare next integer if needed
        if (!stack.isEmpty() && !stack.peek().isInteger()) 
            enstack(stack.pop().getList());
        return res;
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

Key Differences:

• **Implementation 1**:
  • Lazily flattens in hasNext()
  • Calls hasNext() from next()
  • Simpler but less standard
• **Implementation 2**:
  • Maintains integer at stack top
  • Independent hasNext() and next()
  • More standard iterator pattern

Example:

For nested list: [[1,1],2,[1,1]]

• Initial stack (bottom to top): [1,1], 2, [1,1]
• After processing: 1, 1, 2, 1, 1

Implementation Notes:

• **Stack Usage**:
  • Push in reverse order
  • Process nested lists when encountered
  • Maintain correct order of elements
• **Efficiency**:
  • Lazy evaluation in first implementation
  • Pre-processing in second implementation
  • O(1) average time for operations