next up previous
Next: 2.1.6 Alternate Representations of Up: 2.1.5 An Implementation Previous: 2.1.5 An Implementation

2.1.5.1 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, BiListI for lists, and BiIterator_I for iterators. Since BiLists and BiIterators will support all the same operations as Lists and Iterators, we will make these interfaces subinterfaces of BiListI and BiIterator_I.

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

interface BiListI extends ListI {
  void remRear();
  BiIterator_I newBiIterator();
}

BiIterator_I 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 BiIterator_I extends Iterator_I {
  void last();
  void prev();
  boolean atBeginning();
}
Since a BiIterator_I 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 BiListI class BiList the interfaces ListI, ReadIterator, and Iterator_I and classes ListException and IteratorException are identical to those in the code for the (singly-linked) class MutList.

interface BiListI extends ListI {

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

interface BiIterator_I extends Iterator_I {

  // extended iterator for BiListI

  void last();
  void prev();
}

class BiList implements BiListI {

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

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

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

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

  // ** methods in Interface BiListI

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

  public BiListI 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 Iterator_I newIterator() {
    // weaker typing for BiIterator when viewed as Iterator
    return new BiIterator(this);
  }

  public BiIterator_I 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 BiIterator_I {

  // ** 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--;
  }     
}


next up previous
Next: 2.1.6 Alternate Representations of Up: 2.1.5 An Implementation Previous: 2.1.5 An Implementation
Corky Cartwright
2000-01-07