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 BiIteratorI 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 BiIteratorI.
BiListI supports an additional operation for removing nodes at the rear of the list, and provides an additional factory method for producing BiIteratorIs.
interface BiListI extends ListI {
void remRear();
BiIteratorI newBiIterator();
}
BiIteratorI 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 BiIteratorI extends IteratorI {
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 a marker for the both 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 bit more complicated to code and require more elaborate pointer juggling. When implementing doubly-linked lists, it helps to draw diagrams that show what points to what at each stage of one of these operations. Remember to check the correctness of your code on boundary cases such as inserting into an empty list and deleting the last node in a list.
In the following code defining the interface BiListI class BiList the interfaces ListI, ReadIteratorI, and IteratorI and classes ListException and IteratorException are identical to those in the code for the (singly-linked) class MutList.
interface BiListI extends ListI {
/** removes the last element from the list */
void remRear();
/** duplicates the behavior of newIterator(); more precise return type */
BiIteratorI newBiIterator();
}
/** extended iterator for BiListI */
interface BiIteratorI extends IteratorI {
/** move cursor to point to last element of list */
void last();
/** move cursor to the preceding element */
void prev();
}
class BiList implements BiListI {
Node head = new Node(); // allocate circularly linked header node
int length = 0;
// relying on default constructor
public String toString() {
BiIteratorI i = new BiIterator(this);
String result = "(";
for (i.first() ; ! i.atEnd(); i.next())
result = result + " " + i.currentItem();
return result + " )";
}
/* BiListI methods */
public ListI newList() { return new BiList(); }
public BiListI newBiList() { return new BiList(); }
public int length() { return length; }
public void insertFront(T item) {
Node oldSucc = head.succ;
Node newNode = new Node(item, head, oldSucc); // allocate new Node
head.succ = newNode; // insert new Node
oldSucc.pred = newNode;
length++;
}
public void insertRear(T item) {
Node oldPred = head.pred;
Node newNode = new Node(item, oldPred, head); // allocate new Node
head.pred = newNode; // insert new Node
oldPred.succ = newNode;
length++;
}
public void removeFront() {
if (isEmpty())
throw new ListException("removeFront() 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 IteratorI newIterator() {
return new BiIterator(this);
}
public BiIteratorI newBiIterator() {
return new BiIterator(this);
}
}
/* Implementation classes */
class Node {
T item;
Node pred,succ;
Node(T i, Node p, Node s) {
item = i;
pred = p;
succ = s;
}
Node() { // allocate header
item = null;
pred = this;
succ = this;
}
}
class BiIterator implements BiIteratorI {
BiList listThis;
Node current;
BiIterator(BiList l) {
listThis = l; // associated List instance
current = listThis.head.succ; // current is first item (if one exists)
}
/* BiIteratorI methods */
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 T 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(T item) {
/* pre: true
* post: Node containing item is inserted before current item,
* current is unchanged
*/
Node oldPred = current.pred;
Node newNode = new Node(item, 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--;
}
}