Iterator ​

Provide a way to sequentially access elements of a collection object without exposing its underlying representation.

The Iterator pattern is extensively used in Java's collection classes. Taking List as an example, to traverse an ArrayList, even if we know it internally stores an Object[] array, we should not directly use array indices for traversal because it requires understanding the collection's internal storage structure. By using an Iterator, both ArrayList and LinkedList can be traversed using a unified interface:

List<String> list = ...
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    String s = it.next();
}

In fact, because the Iterator pattern is so useful, Java allows us to write any collection that supports Iterator using a foreach loop:

List<String> list = ...
for (String s : list) {

}

The Java compiler then generates all the loop code that implements the Iterator pattern.

Although we have some understanding of how to use an Iterator, how do we implement an Iterator pattern? Let's create a custom collection example by implementing reverse traversal using the Iterator pattern:

public class ReverseArrayCollection<T> implements Iterable<T> {
    // Hold the collection as an array:
    private T[] array;

    public ReverseArrayCollection(T... objs) {
        this.array = Arrays.copyOfRange(objs, 0, objs.length);
    }

    public Iterator<T> iterator() {
        return ???;
    }
}

The key to implementing the Iterator pattern is to return an Iterator object that knows the internal structure of the collection, as it can implement reverse traversal. We use an inner class in Java to implement this Iterator:

public class ReverseArrayCollection<T> implements Iterable<T> {
    private T[] array;

    public ReverseArrayCollection(T... objs) {
        this.array = Arrays.copyOfRange(objs, 0, objs.length);
    }

    public Iterator<T> iterator() {
        return new ReverseIterator();
    }

    class ReverseIterator implements Iterator<T> {
        // Index position:
        int index;

        public ReverseIterator() {
            // When creating the Iterator, the index is at the end of the array:
            this.index = ReverseArrayCollection.this.array.length;
        }

        public boolean hasNext() {
            // If the index is greater than 0, we can move to the next element (moving backward):
            return index > 0;
        }

        public T next() {
            // Move the index to the next element and return it (moving backward):
            index--;
            return array[index];
        }
    }
}

The advantage of using an inner class is that the inner class implicitly holds a reference to its enclosing object (this), allowing access to the ReverseArrayCollection.this.array. The logic implemented above is straightforward, but in practical applications, if considering multi-threaded access where one thread is iterating over a collection while another thread modifies its contents, careful design is needed to determine whether to continue iterating safely or throw a ConcurrentModificationException.

Exercise ​

Implement reverse traversal of a collection using the Iterator pattern.

Summary ​

The Iterator pattern is commonly used for traversing collections. It allows collections to provide a unified Iterator interface to traverse elements while ensuring that callers remain unaware of the collection's internal data structures. This enables callers to traverse various types of collections using the same interface.