TeachJava Laboratory 6
Imperative Object-Oriented Programming

Preparation: the Iterator Design Pattern

A good discipline for expressing computations involving mutable lists is to separate the structural definition of mutable lists from the operations that traverse them. The iterator design pattern is a particularly elegant way to enforce this separation. The iterator pattern consists of two interfaces: an AbstractList interface for constructing lists and an Iterator interface for traversing and modifying them. Neither interface makes the linked list representation explicit; other implementations are possible (and desirable if the Iterator interface includes operations that require indexed access [as in arrays]). A minimal definition of these two interfaces appears below: 
interface AbstractList {
  // maintains a list of elements (e1 e2 ... en)
  void insertFront(Object o); // (e1 e2 ... en) -> (o e1 e2 ... en)
  void insertRear(Object o);  // (e1 e2 ... en) -> (e1 e2 ... en o)
  void remFront();            // (e1 e2 ... en) -> (e2 ... en)
  boolean isEmpty();          // true only for () 
}

interface Iterator {
  // maintains a "cursor" marking a position in traversal of an AbstractList
  // which can be used to access items in the list

  // each Iterator class is paired with a specific AbstractList class

  // each instance of an Iterator class is tied to a corresponding
  // instance the associated AbstractList class 

  void front();          // moves cursor to front of list;
                         // currentItem() is first element

  void next();           // advances cursor one position; throws exception
                         // if atEnd() is true on entry

  boolean atEnd();       // true only when cursor has passed all elements;
                         // (currentItem does not exist!)

  Object currentItem();  // returns item in current node; throws exception
                         // if atEnd() is true on entry

}
The minimalist Iterator pattern shown above does not support the insertion or deletion of items as part of a traversal. The DeIterator interface extending Iterator below adds this capability.

I. Exercises Using Iteration

  1. Load the file ~/comp212/teachjava/List.java into DrJava. Write the body of the max method in the class Test using an appropriate Iterator.

  2. Write a method sum to compute the sum of a list.
  3. Write a method reverse that constructs a reversed copy of the list.