A List Implementation That Links Data - Data Structures and Abstractions with Java - page 343

We could do this by using the list's first add method. However, if add contains the statements
in Segment 14.4 that add an entry to the end of a list, the method getNodeAt will be invoked to
locate the last node in the chain. To accomplish this task, getNodeAt must begin at the first node
and traverse the chain until it locates the last node. Given a reference to the last node, add can insert
the new entry at the end of the chain. If this reference is not retained when the method completes its
task, adding another entry to the end of the list forces add to invoke getNodeAt again. The result is
another traversal of the chain from its beginning. Since we plan to add entries repeatedly to the end
of the list, many repetitious traversals will occur.
In such cases, maintaining a reference to the end of the chain—as well as a reference to the
beginning of the chain—is advantageous. Such a reference to the end of a chain is called a tail
reference, and was introduced in Chapter 11 for the linked implementation of a queue.
Figure 14-7 illustrates two linked chains: one with a head reference and the other with both
head and tail references.
Maintaining both head and tail references is somewhat more involved for a list than it was for
a queue. Thus, our first class of lists using a linked implementation will not define a tail reference.
After we successfully complete this simpler definition, we will modify it by adding a tail reference
and thereby improve its time efficiency. Recall that solving a simpler problem first is often a rea-
sonable strategy.

FIGURE 14-7

A linked chain with (a) a head reference; (b) both a head refer-
ence and a tail reference

(a)

firstNode

(b)

firstNode lastNode

The Data Fields and Constructor
14.8

Listing 14-1 contains an outline of the class LList 1 that implements the ADT list. Recall that Chapter 12
defined the interface ListInterface . It and the classes that implement it define a generic type T for the
objects in the list. We plan to define a chain of linked nodes to contain the list's entries. Thus, we need the class
Node , which we have used in our previous discussion, and so we define it as an inner class of LList . The
generic type T that appears in LList 's header is the same one that we use in the class Node .

LISTING 14-1

An outline of the class LList

/**

A linked implementation of the ADT list.
@author Frank M. Carrano

*/
public class LList<T > implements ListInterface<T >

1. We named this class LList instead of LinkedList to avoid confusion with Java's class LinkedList in the package
java.util . You will see Java's LinkedList at the end of this chapter.