Creating an interleaving iterator is a popular interview question in the Java world.

What is an Interleaving Iterator?

An interleaving iterator is an iterator of iterators. An iterator is a class that implements the following methods (others exist but are not mandatory).

boolean hasNext();
T next();

Iterators are designed to “iterate” (cycle through) a sequence of elements of unknown length. You don’t know how many elements there are; you just know that hasNext() returns true so more elements exist (or it returns false and you’re done with the iterator).

So, an iterator of iterators is an iterator that iterates over iterators which iterate over sequences of elements of another type.

Iterators can even be potentially infinite; they may never end!

Solution Details

There are quite a few different solutions for this… but the easiest one I’ve seen leverages a queue. The basic approach is:

• Create a member variable in the class that is a Queue.
• On construction, populate the queue with all of the provided iterators.
• Create a utility method (getNext() in the solution below).
  • This method is designed to get the next element if it hasn’t already been found.
  • It stores it in a member variable of the class so that we know if it has already been found.
  • The methods next() and hasNext() both defer to this method to test if there is a next element and/or retrieve the next element.
  • This is important as when using the iterator, callers will call hasNext() to see if there is a next element (which must clearly get the next element to know if it exists). We want to return that already-found element when next is called instead of accidentally skipping ahead to yet-another element.
  • Also, if I (badly) made an iterator of iterators that I knew I put 10 elements in overall, I should technically be able to just call next() 10 times without calling hasNext(), even though it is bad practice.
  • IMPORTANT – the method must basically consist of:
  • while next element isn’t found and some iterators remain in the queue:
    • Take next iterator.
    • See if it has more elements.
    • If it does, take the next element and put it back in the queue if it has more.
    • If it doesn’t have more elements, add it back to the queue.
• The next() method just gets the next element using the utility method and returns it, or throws a NoSuchElementException if there wasn’t one.
• The hasNext() method just returns whether or not the utility method says there are more elements.

Implementation (Java)

import java.util.*;

public class InterleavingIterator<T> implements Iterator<T> {

    private Queue<Iterator<T>> iteratorQueue;
    private T next;

    public InterleavingIterator(Iterator<Iterator<T>> masterIterator) {
        if (masterIterator == null) {
            throw new IllegalArgumentException("Iterator cannot be null.");
        }
        iteratorQueue = new ArrayDeque<>();
        masterIterator.forEachRemaining(iteratorQueue::add);
    }

    private T getNext() {
        while (next == null && !iteratorQueue.isEmpty()) {
            Iterator<T> iterator = iteratorQueue.poll();
            if (iterator.hasNext()) {
                next = iterator.next();
                if (iterator.hasNext()) {
                    iteratorQueue.add(iterator);
                }
                return next;
            }
        }
        return next;
    }

    @Override
    public boolean hasNext() {
        return getNext() != null;
    }

    @Override
    public T next() {
        T n = getNext();
        next = null;
        if (n == null) throw new NoSuchElementException();
        return n;
    }

    //Test it out!
    public static void main(String[] args) {

        //Create 4 lists with a range of test cases.
        List<String> a = Arrays.asList("a", "d", "f");
        List<String> b = Arrays.asList("b", "e", "g", "h");
        List<String> c = Collections.singletonList("c");
        List<String> d = Collections.emptyList();

        Iterator<Iterator<String>> masterIterator = Arrays.asList(
                a.iterator(),
                b.iterator(),
                c.iterator(),
                d.iterator()).iterator();

        InterleavingIterator<String> interleaving =
                new InterleavingIterator<>(masterIterator);

        while (interleaving.hasNext()) {
            System.out.println(interleaving.next());
        }
    }
}

Output

a
b
c
d
e
f
g
h