Keywords: current

Next: 2.1.8.1 BiLists and Their Up: 2.1 Sequences Previous: 2.1.7.3 The Iterator Pattern

## 2.1.8 An Implementation

All of our implementation sketches of the last few sections now culminate in the following real list implementation. Notice that we make use of both static nested and inner classes in an effort to hide imperative details.

    // (Singly-Linked) Mutable Lists

    // The ListI interface includes a method newIterator that creates
    // a new iterator for a list.  The List Class implementing ListI
    // hides the Iterator class implementing ListI.  As a result,
    // invoking newIterator is the only way to create new iterators.

    interface ListI {

      ListI newList();
      int length();
      void insertFront(Object o);
      void insertRear(Object o);
      void remFront();
      boolean isEmpty();

      Iterator_I newIterator();
    }

    interface ReadIterator_I {

      // interface for processing both mutable and immutable lists
      void first();
      void next();
      boolean atEnd();
      Object currentItem();

    }

    interface Iterator_I extends ReadIterator_I {

      /* Destructive operations */
      void insert(Object o);
      // inserts before current item; when atEnd(), does insertRear(o)
      void remove();
    }

    // Exception classes for Lists and Iterators

    class ListException extends RuntimeException {
      ListException(String s) { super(s); }
    }

    class IteratorException extends RuntimeException {
      IteratorException(String s) { super(s); }
    }

    class List implements ListI {

      // ** fields **
      private Node head = new Node();  // allocate header node
      private Node last = head;
      private int length = 0;

      // ** constructors **
      // relying on default constructor

      // ** toString() **
      public String toString() {
        Iterator_I i = new Iterator();
        String result = "(";

        for (i.first() ; ! i.atEnd(); i.next())
          result = result + " " + i.currentItem();
        return result + " )";
      }

      // ** methods of ListI **
      public ListI newList() { return new List(); }

      public int length() { return length; }

      public void insertFront(Object o) {
        Node oldSucc = head.succ;
        Node newNode = new Node(o,oldSucc);
        head.succ = newNode;
        if (last == head) last = newNode;
        length++;
      }

      public void insertRear(Object o)  {
        Node newNode = new Node(o,null);
        last.succ = newNode;
        last = newNode;
        length++;
      }

      public void remFront() {
        if (isEmpty()) throw new
          ListException("remFront() applied to EmptyList");
        else {
          Node newSucc = head.succ.succ;
          head.succ = newSucc;
          if (newSucc == null) last = head;
          length--;
        }
      }

      public boolean isEmpty() { return head == last; }

      public Iterator_I newIterator() {
        return new Iterator();
      }

      // ** hidden classes Node and Iterator **/

      private static class Node {

        /* fields */
        Object item;
        Node succ;

        /* constructors */
        Node(Object i, Node s) {
          item = i;
          succ = s;
        }

        Node() {  // allocate header
          item = null;
          succ = null;
        }

        // fields are accessed directly by code in List class
      }

      private class Iterator implements Iterator_I {

        // NOTE: Iterator points to predecessor of current item.
        // Hence, current item is pred.succ

        /* fields */
        Node pred;

        /* Constructors */
        Iterator() {
          pred = head;
        }

        /* methods in Iterator_I interface */
        public void first() {
          // reposition cursor to refer to first item (if one exists)
          pred = head;
        }

        public void next() {
          // advance cursor
          if (atEnd()) throw new
              IteratorException("No next element in Iteration");
          pred = pred.succ;
        }

        public Object currentItem() {
          // returns current item
          if (atEnd()) throw new
            IteratorException("No current element in " + List.this);
          return pred.succ.item;
        }

        public boolean atEnd() { return pred == last; }
        // returns true iff cursor points to imaginary element beyond last

        public void insert(Object o) {

          // pre: current is either a list element or an imaginary
          //      element just beyond the last element
          // post: Node containing o is inserted before current item,
          //       current is unchanged (pred is changed, last may be)

          Node oldSucc = pred.succ;
          Node newNode = new Node(o, oldSucc); // allocate new node
          pred.succ = newNode;                 // insert it
          pred = newNode;                      // update current
          if (oldSucc == null) last = newNode; // update last if needed
          length++;
        }

        public void remove() {

          // pre: pred != last (current is valid)
          // post: pred.succ becomes pred.succ.succ

          if (atEnd()) // no element available to remove!
            throw new IteratorException(
              "Iterator.remove() applied at end of List");
          Node deadNode = pred.succ;
          pred.succ = deadNode.succ;
          if (last == deadNode) last = pred;
          length--;
        }
      }
    }

Subsections

- 2.1.8.1 BiLists and Their Iterators