The Iterator Pattern

Before we present a complete implementation of singly-linked imperative lists, we describe a new pattern which allows us to process lists similarly to arrays. The pattern is called the Iterator pattern, and consists of two interfaces, an abstract list, with methods for building and modifying lists

interface ItSeq extends {
  void insertFront(Object o);     
  void insertRear(Object o);      
  boolean isEmpty();              
  void remFront();          // remove the first element
}

and an abstract iterator, with methods for traversing a list and examining its contents

interface IIterator {
  void front();             // move to first element
  void next();                    
  boolean atEnd();          // test whether past the last element
  Object currentItem();     // contents of current element
}

The iterator's atEnd method returns true if and only if the iterator has moved past the last element of the list. When the iterator is in this state, the currentItem method will throw an exception.

With such a list and such an iterator we could easily implement a queue, since we can remove from the front and add at the back.

It would be nice if the list were more flexible however. For example, we may wish to sort a list. We can already do this in a functional style, by building a new list while using insertion sort, but since this is a mutable list we should ideally be able to sort the list without copying the nodes, changing it from an unsorted list into a sorted one. We can implement such a sort if we add two more methods to the Iterator_I implementation:

  void insertBefore(Object o); // add new element before current
  void remove();               // remove current

A given list may have more that one iterator active on it at one time, so the remove and insertBefore methods must be used with some care.

The definition of an iterator class implementing the Iterator_I involves two subtle issues: First, for an iterator to remove the current element, it must have a reference to the element immediately before the current element.

Second, we can treat the empty list like any other list if we include a dummy node which is always at the head of the list. This dummy node simplifes the implementation of element removal when that element is the last element of the list. When the list is empty, the last field refers to dummy node.