Keywords: current

Next: 2.1.9 Alternate Representations of Up: 2.1.8 An Implementation Previous: 2.1.8 An Implementation

### 2.1.8.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 `BiList`s and their iterators `BiIterator`s.

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 `List`s and `Iterator`s, 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_I`s.

    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: 2.1.9 Alternate Representations of Up: 2.1.8 An Implementation Previous: 2.1.8 An Implementation