2.1.5 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--;
    }   
  }
}