Flatten iterator for nested list

Given a list which can can contain elements as well as lists, write an iterator to flatten a nested list. Please make this code better and suggest any improvements.

public class FlattenIterator implements Iterator {

    private final Stack iteratorStack;

    private Object next;

    public FlattenIterator(List list) {
        if (list == null) {
            throw new NullPointerException();
        }

        iteratorStack = new Stack();
        iteratorStack.push(list.iterator());
    }

    public void remove() {
        /* Not implemented */
    }

    private void moveToNext() {
        if ((next == null) && !iteratorStack.empty()) {
            if (iteratorStack.peek().hasNext()) {
                final Object next = iteratorStack.peek().next();
                if (next instanceof Iterator) {
                    iteratorStack.push((Iterator) next);
                    moveToNext();
                } else if (next instanceof Iterable) {
                    iteratorStack.push(((Iterable) next).iterator());
                    moveToNext();
                } else if (next instanceof Array) {
                    iteratorStack.push(Arrays.asList((Array) next).iterator());
                    moveToNext();
                } else {
                    this.next = next;
                }
            } else {
                iteratorStack.pop();
                moveToNext();
            }
        }
    }

    public boolean hasNext() {
        moveToNext();
        return next != null;
    }

    public Object next() {
        moveToNext();
        if (next == null) {
            throw new NoSuchElementException(); 
        } else {
            Object objectToReturn = next;
            next = null;
            return objectToReturn;
        }
    }
}

You should probably review: com.google.common.collect.Iterators, especially com.google.common.collect.Iterators.concat() (com.google.guava:guava). That implementation uses a member variable to hold and track the current iterator, in addition to the container of ordered iterators to inspect.

If you initialize current iterator with an empty iterator value (again, see guava), you'll eliminate some problem edge cases.

moveToNext() should not use recursion. Instead, it ought to be a while loop that is determining the correct current iterator to use, and then returning the status of that iterator. After all, you've already got a Stack, why do you need to use the stack also?

Take a good look at that constructor again - you happen to be getting an iterator from List.iterator(), but there's no reason at all to care if it came from List, or some other collection.

private final Stack iteratorStack = new Stack();
public FlattenIterator(List list) { this(list.iterator);  }
public FlattenIterator(Iterator iterator) { iteratorStack.push(iterator); }

The Dependency Injection pattern would perhaps suggest that you should have a constructor that accepts a Stack, and factory methods that create the Stack from the initial source iterator. Not immediately clear - here, the stack is an implementation detail, so maybe it's not important. On the other hand, if you can imagine sometimes swapping in a different implementation, that will run extra logging/instrumentation/debug code, then maybe you'll want to have that constructor.

Why not FlattenIterator extends Iterator? Yes, the source is going to be mixed type, but you don't need to propagate that forward forever.

You might consider whether List is actually the right idea; here, you are using List as a poor man's Composite (see Design Patterns, Gamma et al). What you are really doing, after all, is visiting all leaves of a tree, so maybe the tree should be explicit, rather than implicit in the list. If you have control over the caller, that's a design choice you might consider walking backwards.

It's not clear if remove() should be a no-op, as it is here, or throw an UnsupportedOperationException. At a minumum, there should be a comment explaining why it doesn't throw.

StackExchange Code Review Q#32827, answer score: 4