2.1.7.3 The Iterator Pattern
Keywords: current

Next: 2.1.8 An Implementation Up: 2.1.7 Extended Mutable Lists Previous: 2.1.7.2 Spaghetti References (akin

###
2.1.7.3 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 Iterator_I {
      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.

Next: 2.1.8 An Implementation Up: 2.1.7 Extended Mutable Lists Previous: 2.1.7.2 Spaghetti References (akin