Iterators

Often times you find yourself traversing/iterating over a collection. The iterator pattern encapsulates this functionality without exposing its underlying representation of the collection. In java this pattern is used to implement the enhanced for or also called for-each loop. Under the hood all the for each loop does is get an iterator instance and iterate over it step by step, this is also why you can only use the for-each loop on collections that actually implement the Iterable<T> (opens in a new tab) interface.

Why is this pattern useful?

Because depending on the collection there might be different ways to traverse it, for example binary trees can be traversed in many orders but the methods you call to traverse the collection should be the same. We want a common interface for traversing different collections in different ways.
Also, because the iterator object holds all the details regarding the traversal of the collection, several iterators can go through the same collection at the same time, independently of each other as long as they don't change the underlying collection, if they do it gets a bit complicated with mutexes.

How different iterators can traverse a binary tree.

Structure

The Iterable<T> interface defines the method Iterator<T> iterator(), or Iterator<T> createIterator()which is responsible for creating and returning the iterator interface (opens in a new tab) that can then be used to traverse the collection containing elements of type T.

An iterator always holds the value of the next element, apart from at the beginning of an iteration, where it holds a reference to the first element. In java the iterator instance returned must implement the Iterator<T> interface which declares the operations required for traversing the collection.

Todo

An animation of the iterator moving through a linked list would be cool.

Info

When implementing an iterator it is recommended to do so in an internal private final class in the collection class as you then have access to the internal structure of the collection without having to make all the details public.

The pattern then has an overall structure that can look something like this:

The T next() method returns the element the iterator is currently pointing to and advances the iterator to the next element.
The boolean hasNext() method returns false once the iterator has reached the end of the collection, otherwise true.

ListIterator

In Java, there is also the ListIterator<T> (opens in a new tab) interface which extends the Iterator<T> interface. This interface adds functionality that allows for iteration in both directions with T next() and T previous(). Matchingly it also offers a boolean hasPrevious() to the boolean hasNext() method. One can imagine that ListIterator has no current element, its position is always between the element that would be returned by a call to previous() and the element that would be returned by a call to next().

Because the iterator traverses a collection like a list it also works and assigns an index to each element which can be fetched.

Removing Elements

The iterator interface also defines an optional void remove() method, that removes the most recently returned element from the iterator.

How the remove method works in an iterator.

However, when removing elements whilst other iterators are also traversing the collection, for example in a concurrent program some problems can occur, mainly in consistent state and iterator pointers getting cut of from iterating further. One way of solving these problems is by using a modification counter (modCount) which is incremented whenever the underlying collection is changed, for example when adding or removing an element. When an iterator is instantiated the modCount is copied and continuously checked if it is the same as the underlying modCount of the collection if not then a ConcurrentModificationException is thrown. How this works for different collections in java is explained here (opens in a new tab).

Implementation

A possible implementation for an iterator over a linked list could look like this:

 
class SomeCollection<T> implements Iterable<T> {
 
    //implementation of other functions and internal state
 
    @Override
    public Iterator <T> iterator() {
        return new MyIterator();
    }
 
    private final class MyIterator implements Iterator<T> {
        // p and pp keeps track of the previous elements to be able to remove
        private Node<T> next = first, p = null, pp = null;
        private int myModCount = modCount; // copy the modCount of the collection
        private boolean mayRemove = false;
 
        @Override
        public boolean hasNext() {
            return next != null;
        }
 
        @Override
        public T next() {
            if (modCount != myModCount)
                throw new ConcurrentModificationException();
            if (next == null)
                throw new NoSuchElementException();
            T elem = next.elem;
            if (p != null) pp = p;
            p = next;
            next = next.next;
            mayRemove = true;
            return elem;
        }
 
        @Override
        public void remove() {
            if (modCount != myModCount)
                throw new ConcurrentModificationException();
            if (!mayRemove)
                throw new IllegalStateException();
            if (pp != null) pp.next = next;
            else first = next;
            if (next == null) last = pp;
            p = pp;
            mayRemove = false;
            size--;
            modCount++;
            myModCount = modCount;
        }
    }
}

Spliterator

Factory Observer