Designing an iterator in Java

Question

I have come across many problems where an iterator is required. Often, they are simple things where you already have an underlying data structure that you can defer to. Other times, it gets more complex.

An example would be iterating over a BST without parent links using an in-order traversal. This requires that you do something like:

• Create a stack in the constructor.
• Iterate to the left-most node.
• Store that there are more nodes to visit for easy return from hasNext().
• Store the next node to visit for easy return from next().

You can do the work to locate the next node in hasNext(), or in next(). You can also locate the first node in the constructor or in the first call to hasNext().

---

My Question

Are there standards or best practices for where to do most of the work in your iterator implementation? Is one way "cleaner" than another?

Answer 1

First, the contract of Iterator requires that hasNext return true if there are more elements, and next will throw an exception if hasNext()==false.

That means that there are two styles of using an iterator: while (it.hasNext()) it.next(), and try { while (true) it.next(); } catch .... The latter is not a good practice, but it must be supported. I mentioned this because you cannot rely on hasNext having been called before next. I found this requirement is usually the culprit of otherwise unnecesary complexity in the implementation of iterators.

My choice is having a local variable with the next value. If next==null either the next value is unknown (and we must find it), or we have reached the end of the iteration (hasNext() will return false and next() will fail). Consider also that when the next value is unknown, it is possible that we are at the end of the iteration, but we haven't realized it yet.

Node next;

public boolean hasNext() {
   //if the next value already known, do nothing
   if (next==null) {         
     //otherwise lookup the next value
     next=findNext();
   }
   //return true if the next value was found
   return next!=null;
}

public Node next() {
  if (next==null&&!hasNext()) {
     //here we have reached the end of the iteration
     throw new NoSuchElementException();
  } else {
     //either we alredy knowed the next element 
     //or it was found by hasNext
     Node result = next;
     next=null;
     return result;
  }   
}

private Node findNext() {
   //the actual iteration
}

About the case of in-order traversal, you should keep a stack (note that the implementation of Stack is array-based and synchronized, probebly it is better to use a Dequeue such as LinkedList, which also supports push and pop as of Java 6), and auxiliary state for knowing how to resume the iteration each time that findNext is called.