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);
 
Search WWH ::




Custom Search