Java Reference
In-Depth Information
lastNode = newNode;
}
// end addToBack
Aside from its name, this method differs from
enqueue
only in the statement that allocates a new node.
FIGURE 11-18
Adding to the back of a nonempty deque: (a) after the new node
is allocated; (b) after the addition is complete
(a)
newNode
lastNode
(b)
lastNode
The method
addToFront
has an analogous implementation. When adding a node to the begin-
ning of a doubly linked chain, we must make the chain's current first node reference the new node
by passing the deque's data field
firstNode
to the node's constructor. Compare the following defi-
nition for
addToFront
with the one just given for
addToBack
:
public void
addToFront(T newEntry)
{
DLNode newNode =
new
DLNode(
null
, newEntry, firstNode);
if
(isEmpty())
lastNode = newNode;
else
firstNode.setPreviousNode(newNode);
firstNode = newNode;
}
// end addToFront
As given here, both
addToFront
and
addToBack
are O(1) operations.
11.38
Removing an entry.
The method
removeFront
has an implementation much like that of
dequeue
given in Segment 11.5, but it has one other concern. After detaching the first node, if the deque is
not empty,
removeFront
must set the field
previous
in the new first node to
null
. This step occurs
in the
else
clause of the following definition:
public
T removeFront()
{
T front =
null
;
if
(!isEmpty())
{
front = firstNode.getData();
firstNode = firstNode.getNextNode();
if
(firstNode ==
null
)
lastNode =
null
;
else
firstNode.setPreviousNode(
null
);
}
// end if
