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();
}
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--;
}
}