Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 115

/ ** Insert"it"atcurrentposition * /
publicvoidinsert(Eit){
curr.setNext(newDLink<E>(it,curr,curr.next()));
curr.next().next().setPrev(curr.next());
cnt++;

}

/ ** Append"it"tolist * /
publicvoidappend(Eit){
tail.setPrev(newDLink<E>(it,tail.prev(),tail));
tail.prev().prev().setNext(tail.prev());
cnt++;

}

/ ** Removeandreturncurrentelement * /
publicEremove(){
if(curr.next()==tail)returnnull;//Nothingtoremove
Eit=curr.next().element(); //Remembervalue
curr.next().next().setPrev(curr);
curr.setNext(curr.next().next());//Removefromlist
cnt--; //Decrementthecount

returnit; //Returnvalueremoved

}

/ ** Movecurronestepleft;nochangeifatfront * /
publicvoidprev(){
if(curr!=head) //Can'tbackupfromlisthead
curr=curr.prev();

}

Figure4.15 Implementations for doubly linked list insert , append ,
remove , and prev methods.

Example4.1 There is a space-saving technique that can be employed to
eliminate the additional space requirement, though it will complicate the
implementation and be somewhat slower. Thus, this is an example of a
space/time tradeoff. It is based on observing that, if we store the sum of
two values, then we can get either value back by subtracting the other. That
is, if we store a + b in variable c, then b = ca and a = cb. Of course,
to recover one of the values out of the stored summation, the other value
must be supplied. A pointer to the first node in the list, along with the value
of one of its two link fields, will allow access to all of the remaining nodes
of the list in order. This is because the pointer to the node must be the same
as the value of the following node's prev pointer, as well as the previous
node's next pointer. It is possible to move down the list breaking apart
the summed link fields as though you were opening a zipper. Details for
implementing this variation are left as an exercise.