Java Reference
In-Depth Information
so, getNodeAt must traverse the chain from its beginning. We can improve the time efficiency of
this add method by maintaining a reference to the end of the chain, as well as a reference to the
beginning of the chain, as was pictured earlier in Figure 14-7b and repeated here in Figure 14-8. In
this way, we avoid a traversal of the entire chain each time that add is called.
FIGURE 14-8
A linked chain with both a head reference and a tail reference
lastNode
firstNode
Question 15 Examine the implementation of the class LList given in this chapter. Which
methods would require a new definition if you use both a head reference and a tail reference?
The Tail Reference
14.20
The tail reference, like the head reference, is a private data field of the class. Thus, the private data
fields of the revised class are now
private Node firstNode; // head reference to first node
private Node lastNode; // tail reference to last node
private int numberOfEntries; // number of entries in list
By examining the class LList , as described earlier in this chapter, you should find that the two add
methods and the methods remove and clear are the ones that will involve the head and tail refer-
ences and, thus, need to be revised. We should also revise the assertions in the method isEmpty .
The rest of the original implementation, including the constructor, remains the same. Let's examine
these revisions. We will name the revised class LList2 to distinguish it from the original one.
14.21
The method clear . We begin with the method clear , because the constructor calls it. It must ini-
tialize both the head and tail references as well as the field numberOfEntries :
public final void clear()
{
firstNode = null ;
lastNode = null ;
numberOfEntries = 0;
} // end clear
Here, and in the rest of the revision, changes to the original implementation are highlighted.
14.22
Adding to the end of the list. The steps required to add an entry to the end of a list depend upon
whether the list is empty or not. After an item is added to the end of an empty list, both the head and
tail references must reference the new solitary node. Thus, after creating a new node that newNode
references, the add method would execute
firstNode = newNode;
lastNode = newNode;
Adding to the end of a nonempty list no longer requires a traversal to locate the last entry:
The tail reference lastNode provides this information. After the addition has been made, the tail
 
 
Search WWH ::




Custom Search