Iterators

• Data structures typically contain a collection of elements.
• It is often useful to be able to traverse that collection of elements.
• It is possible to get an iterator from any collection that implements the Iterable<T> interface.
• The Iterable<T> interface is quite simple:

  Iterator<T> iterator();
  

• You may be wondering why you're seeing <T> instead of <E>.
  • Skip these sub-bullets if you aren't the slight bit interested.
  • The E in List<E> refers to the type of element in the list.
  • The T in Iterable<T> refers to the type of element over which we can iterate.
  • Okay... at least I gave you the option of skipping these sub-bullets.
• So you're probably wondering what you can do with an iterator. If not, you should be.
• Iterator<E> is an interface consisting of three methods:
  • boolean hasNext() — returns true if another element exists in the collection
  • E next() — returns the next element in the collection
  • void remove() — removes, from the underlying collection, the last element returned by the iterator (the result of the most recent next() call)
• That's all great, but who's going to implement the Iterator<E> interface?
  • We need a class to implement the interface, but the class needs to be able to access the elements within the collection.
  • Nested/Inner class to the rescue.¹⁾

Revisiting the Simplified ArrayList<E> Example

• Here is how we could add the Iterable<T> interface to our simplified ArrayList<E> class

    @Override
    public Iterator<E> iterator() {
      return new ArrayListIterator();
    }
    
    private class ArrayListIterator implements Iterator<E> {
    
      private int position;
    
      private boolean isLegalToRemove;
    
      private ArrayListIterator(){
        position = -1;
        isLegalToRemove = false;
      }
    
      @Override
      public boolean hasNext() {
        return size() > (position+1);
      }
    
      @Override
      public E next() {
        if(!hasNext()){
          throw new NoSuchElementException("No next element available");
        }
        isLegalToRemove = true;
        return array[++position];
      }
    
      @Override
      public void remove() {
        if(!isLegalToRemove){
          throw new IllegalStateException("Must call next() before remove()");
        }
        isLegalToRemove = false;
        ArrayList.this.remove(position--);
      }
    
    } // End of ArrayListIterator class
  

• You might think that we'd need to change the class declaration to this:

  public class ArrayList<E> implements List<E>, Iterable<E> {
  

  • We don't need to do this because the List<E> interface extends the Collection<E> interface which extends the Iterable<E> interface.
• Let's look at this code for a little bit...
  • The iterator() method was part of the ArrayList<E> class before, we just hadn't implemented it here.
  • Our implementation just returns a reference to an object from the ArrayListIterator class — the superhero inner class.
  • The ArrayListIterator class and its constructor are declared private since nobody but the ArrayList<E> class has any business messing with the class directly.
  • The position attribute keeps track of where we are in the collection.
  • The isLegalToRemove attribute is used by the remove method, and we'll talk about it in a bit.
  • The constructor forces us to begin one before the first element of the collection.
  • hasNext() needs to make sure that the position is such that we still have at least one more element in the collection to traverse.
    • We just make sure that we'll still have an element to return after incrementing the position.
  • next() moves the iterator to the next element and returns a reference to it.
    • First, we check to make sure that we have an element in the collection (if not we throw a NoSuchElementException exception).
    • Second, we increment the position attribute. Note: because we are using the pre-increment operator, position gets incremented before we evaluate the rest of the expression. If we did position++ instead, we would get an ArrayIndexOutOfBoundsException exception the first time we called next() because it would be trying this: array[-1].
    • Third, we return a reference to the next element in the collection.
  • remove() is an optional method (meaning you can throw an UnsupportedOperationException exception instead of implementing it), but the List<E> interface provides a remove(int index) method that does just what we want, so we'll call it.²⁾
    • The remove() method should only be called if next() has been called since it the iterator was instantiated and since the last remove() call.
    • As a result, we have introduced the isLegalToRemove flag to keep track of when it is legal to call remove().
      • isLegalToRemove is set to false in the constructor and whenever remove() is called.
      • isLegalToRemove is set to true whenever next() is called.

Enhanced for Loop: The foreach Loop

• Iterators are what make it possible for us to use the enhance for loop.
• Consider:

      List<Integer> list = new ArrayList<Integer>();
      for(int i=0; i<5; ++i) {
        list.add((int)(Math.random()*25));
      }
    
      for(Integer number : list) {
        System.out.println(number);
      }
  

  • The second for loop makes use of an interator to navigate the collection.
  • It is equivalent to doing this:

        Iterator<Integer> itr = list.iterator();
        while(itr.hasNext()) {
          Integer number = itr.next();
          System.out.println(number);
        }