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?
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