Designing an Iterator in Java

Question

I ran into many problems when an iterator is required. Often these are simple things in which you already have a basic data structure that you can put aside. In other cases, it becomes more complex.

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

• Create a stack in the constructor.
• Go to the leftmost node.
• Keep in mind that for the convenience of returning from hasNext (), more nodes have been added.
• Save the next node for a quick jump from the next ().

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

---

My question

Are there standards or guidelines on how to do most of the work in your iterator implementation? Is one way cleaner than the other?

Answer 1

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

This means that there are two styles of using the iterator: while (it.hasNext()) it.next() and try { while (true) it.next(); } catch ... try { while (true) it.next(); } catch ... The latter is not good practice, but it should be supported. I mentioned this because you cannot rely on hasNext , which was called before next . I found this requirement, as a rule, the culprit of unnecessary complexity in the implementation of iterators.

My choice has a local variable with the value next . 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 have not realized this 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 traversal case in order, you should keep the stack (note that the Stack implementation is array-based and synchronized, it is best to use Dequeue , such as LinkedList , which also supports push and pop in Java 6) and an auxiliary state in order to know how to resume iteration every time findNext is findNext .

Answer 2

Bypassing BST in order can be implemented using simple recursive DFS (left child → node → right child).

Answering your question: in general, I think that there are no “best practices” for developing an iterator, because your data structures can be arbitrarily complex. Some general rules:

• Your iterator should support hasNext() and next() operations anyway. If your data structure is immutable (or the removal is not typical), the remove() method should throw an OperationNotSupportedException() .
• next() method should check the hasNext() value at the beginning of the implementation and throw a NoSuchElementException if hasNext() returns false .
• If your data structure has an iterator, it must implement the Iterable<Type> interface and implement the public Iterator<Type> iterator() method.
• So, if you implement the Iterable interface, client code can use the foreach to process your data structure. If this behavior is undesirable (for example, using foreach with a bipartite chart structure can lead to several client errors, because it’s not obvious what exactly iteration is for), you should probably consider another way to implement sequential iterations.
• If your data structure uses a list or set, your iterator implementation can use the appropriate collection iterator.

In any case, you should design iterators with care. Each iterator is deeply related to its data structure and needs to be developed together.