Tutorials
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.1)

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.2)
      • 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);
          }
      
1)It's tough to take superhero seriously if it has a slash in its name, so I probably should have just said Nested class to the rescue OR Inner class to the rescue.
2)Hopefully you didn't notice that we didn't actually implement that method.

Last modified: Monday, 17-Aug-2015 21:49:40 CDT