Java Reference
In-Depth Information
11.36
An outline of the class.
The doubly linked implementation of the deque begins much like the linked
implementation of the queue given in Segment 11.2. The class has two data fields—
firstNode
and
lastNode
—that the default constructor sets to
null
, as you can see in Listing 11-5.
LISTING 11-5
An outline of a linked implementation of the ADT deque
/**
A class that implements a deque of objects by using
a chain of doubly linked nodes.
@author Frank M. Carrano
*/
public class
LinkedDeque<T>
implements
DequeInterface<T>
{
private
DLNode firstNode;
// references node for front of deque
private
DLNode lastNode;
// references node for back of deque
public
LinkedDeque()
{
firstNode =
null
;
lastNode =
null
;
}
// end default constructor
< Implementations of the deque operations go here. >
. . .
private class
DLNode
{
private
T data;
// deque entry
private
DLNode next;
// link to next node
private
DLNode previous;
// link to previous node
< Constructors and the methods
getData
,
setData
,
getNextNode
,
setNextNode
,
getPreviousNode
,
and
setPreviousNode
are here. >
. . .
}
// end DLNode
}
// end LinkedDeque
11.37
Adding an entry.
The implementation of the method
addToBack
is like the implementation of
enqueue
given in Segment 11.3. Both methods add a node to the end of a chain so that the chain's cur-
rent last node references the new node. Here, we also make the new node reference the current last
node by passing the deque's data field
lastNode
to the node's constructor. The addition to the back of
a chain that is not empty is illustrated in Figure 11-18. An implementation of the method follows:
public void
addToBack(T newEntry)
{
DLNode newNode =
new
DLNode(lastNode, newEntry,
null
);
if
(isEmpty())
firstNode = newNode;
else
lastNode.setNextNode(newNode);