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

/ ** Doublylinkedlistnode * /
classDLink<E>{
privateEelement; //Valueforthisnode
privateDLink<E>next; //Pointertonextnodeinlist
privateDLink<E>prev; //Pointertopreviousnode

/ ** Constructors * /
DLink(Eit,DLink<E>p,DLink<E>n)
{element=it;prev=p;next=n;}
DLink(DLink<E>p,DLink<E>n){prev=p;next=n;}

/ ** Getandsetmethodsforthedatamembers * /
DLink<E>next(){returnnext;}
DLink<E>setNext(DLink<E>nextval)
{returnnext=nextval;}
DLink<E>prev(){returnprev;}
DLink<E>setPrev(DLink<E>prevval)
{returnprev=prevval;}
Eelement(){returnelement;}
EsetElement(Eit){returnelement=it;}

}

Figure4.14 Doubly linked list node implementation with a freelist.

of the header and tailer nodes mean that there are no special cases to worry about
when inserting into an empty list.
The append method is also simple. Again, the Link class constructor sets the
element , prev , and next fields of the node when the new operator is executed.
Method remove (illustrated by Figure 4.17) is straightforward, though the
code is somewhat longer. First, the variable it is assigned the value being re-
moved. Note that we must separate the element, which is returned to the caller,
from the link object. The following lines then adjust the list.

Eit=curr.next().element(); //Remembervalue
curr.next().next().setPrev(curr);
curr.setNext(curr.next().next());//Removefromlist

The first line stores the value of the node being removed. The second line makes
the next node's prev pointer point to the left of the node being removed. Finally,
the next field of the node preceding the one being deleted is adjusted. The final
steps of method remove are to update the list length and return the value of the
deleted element.
The only disadvantage of the doubly linked list as compared to the singly linked
list is the additional space used. The doubly linked list requires two pointers per
node, and so in the implementation presented it requires twice as much overhead
as the singly linked list.