Implementing an Iterator

There are a few things to consider when implementing an iterator. The iterator needs to:

• have direct access to the list and its elements
• keep track of where it is in the list
• fail if concurrently modified

In order to have direct access, the iterator is typically implemented as an inner class. How it keeps track of where it is depends on how the list is implemented. For an array based list, the iterator will need to track an index. For a linked list, the iterator will need a Node.

One way to check for concurrent modifications is to have both the list and the iterator track modifications to the list. Every time the list is modified, the list updates its modification count. Every time the iterator makes a modification (i.e. successfully completes a remove). Remember that each object gets its own copies of all of the instance variables. If the modification values are ever unequal, then the list has been modified by something other than this iterator.

The code below demonstrates an outline of all of these points.

public class SomeIterableList implements Iterable {
    /*
     * List implementation goes here
     */
    // counts the number of modifications made to this list
    private int modCount;
    @Override
    public Iterator iterator() {
        return new SomeIterator();
    }
    /**
     * Iterator
     */
    private class SomeIterator implements Iterator {
        // needs private instance variables to keep
        // track of where it is in the list
        // counts the modifications made by THIS iterator
        private int iterModCount;
        public SomeIterator() {
            // initialize instance variables
		iterModCount = modCount;
        }
        @Override
        public boolean hasNext() {
            return false;
        }
        @Override
        public E next() {
            return null;
        }
        @Override
        public void remove() {
        }
    }
}

Note that you may need other private methods or instance variables depending on the kind of list through which you’re iterating. You will also need to consider how to determine if you can safely remove or not.