BiLists and Their Iterators

The lists of the last few sections can be efficiently scanned in only one direction, starting at the front and proceeding element by element to the end. We would now like to develop a more general form of list that supports both forward and backward traversal. The new list implementation will use doubly-linked lists, and we will call the new lists BiLists and their iterators BiIterators.

As with our previous lists, we define a pair of interfaces, IBiList for lists, and IBiIterator for iterators. Since BiLists and BiIterators will support all the same operations as Lists and Iterators, we will make these interfaces subinterfaces of IBiList and IBiIterator.

IBiList supports an additional operation for removing nodes at the rear of the list, and provides an additional factory method for producing IBiIterators.

interface IBiList extends IList {
  void remRear();
  BiIIterator newBiIterator();
}

IBiIterator supports backward traversal of lists, and so requires methods for moving to the end of a list, moving back an element, and a test for whether the iterator is at the front of the list.

interface IBiIterator extends IIterator {
  void last();
  void prev();
  boolean atBeginning();
}

Since a IBiIterator is also necessarily an Iterator_I, a BiIterator_I instance can be substituted for an Iterator_I instance. Thus the newIterator and newBiIterator methods can share the same implementation.

An implementation of BiList and BiIterator is given below. In contrast to the List implementation of the last section, all the classes are top-level, and so imperative operations are not as well hidden. The BiIterator must now have a field to record the BiList it operates on, and this must be initialized at construction time. As an exercise, try converting the implementation so it uses nested and inner classes as in the List case.

The underlying list structure is doubly-linked and circular. The dummy node acts as both a marker for the beginning and the end of the list. Since nodes have pointers to both next and previous nodes, the insertion and deletion methods are a little more tricky and require more elaborate pointer juggling. When implementing doubly-linked lists yourself, it helps to draw diagrams that show what points to what at each stage of one of these operations.

In the following code defining the interface IBiList class BiList the interfaces IList, ReadIterator, and Iterator_I and classes ListException and IteratorException are identical to those in the code for the (singly-linked) class MutList.

interface IBiList extends IList {

  // Extra operation required for bi-directional traversal
  // Standard implementation uses double linking
  
  void remRear();
  IBiIterator newBiIterator(); 
  // duplicate of newIterator() with more precise return type
}

interface IBiIterator extends IIterator {

  // extended iterator for IBiList

  void last();
  void prev();
}

class BiList implements IBiList {

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

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

  // ** toString
  public String toString() {
    IBiIterator i = new BiIterator(this);
    String result = "(";

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

  // ** methods in Interface IBiList

  public IList newList() { return new BiList(); }

  public IBiList newBiList() { return new BiList(); }

  public int length() { return length; }

  public void insertFront(Object o) { 
    Node oldSucc = head.succ;
    Node newNode = new Node(o,head,oldSucc);  // allocate new Node
    // insert new Node
    head.succ = newNode;
    oldSucc.pred = newNode;
    length++;
  }
    
  public void insertRear(Object o)  { 
    Node oldPred = head.pred;
    Node newNode = new Node(o,oldPred,head);  // allocate new Node
    // insert new Node
    head.pred = newNode;
    oldPred.succ = newNode;
    length++;
  }

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

  public void remRear() { 
    if (isEmpty())    
      throw new ListException("remRear() applied to EmptyList");
    else {
      Node newPred = head.pred.pred;
      head.pred = newPred;
      newPred.succ = head;
      length--;
    }
  }

  public boolean isEmpty() { return head == head.succ; }

  public IIterator newIterator() {
    // weaker typing for BiIterator when viewed as Iterator
    return new BiIterator(this);
  }

  public IBiIterator newBiIterator() {
    return new BiIterator(this);
  }
}

// Implementation classes (not hidden!)

class Node {
  // ** fields ** 
  Object item;
  Node pred,succ;

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

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

class BiIterator implements IBiIterator {

  // ** fields **
  BiList listThis;
  Node current;

  // ** constructors **
  BiIterator(BiList l) {
    listThis = l;                  // associated List instance
    current = listThis.head.succ;  // current is first item (if one exists)
  }

  // ** methods in BiIterator interface **
  public void first() { 
    current = listThis.head.succ;  // current is first item (if one exists)
  }

  public void last() { 
    current = listThis.head.pred;  // current is last item (if one exists)
  }

  public void next() {
    current = current.succ;        // wraps around end
  }

  public void prev() {
    current = current.pred;        // wraps around end
  }

  public Object currentItem() { 
    if (current == listThis.head) throw
      new IteratorException("No current element in " + listThis);
    return current.item; 
  }

  public boolean atEnd() { return current == listThis.head; }

  public void insert(Object o) {

    // pre: true
    // post: Node containing o is inserted before current item, 
    //       current is unchanged

    Node oldPred = current.pred;
    Node newNode = new Node(o, oldPred, current);  // allocate new node
    current.pred = newNode;                        // insert it
    oldPred.succ = newNode;
    listThis.length++;
  }     

  public void remove() {

    // pre:  current is valid
    // post: current becomes current.succ

    if (current == listThis.head) throw 
      new IteratorException(
        "BiIterator.remove() applied at end of BiList " + listThis);
    Node cPred = current.pred;
    Node cSucc = current.succ;
    cPred.succ = cSucc;
    cSucc.pred = cPred;
    current = cSucc;  
    listThis.length--;
  }     
}