Sorted Lists - Data Structures and Abstractions with Java - page 417

return currentNode;
} // end add

The private method add adds newEntry to the subchain that begins at currentNode . We will trace
and explain its logic in a moment.

Question 7 Repeat Question 5, using the method add that was just given.

16.14

Tracing an addition to the list's beginning. Suppose that nameList is the sorted list that the chain
in Figure 16-3a represents. Let's invoke nameList.add("Ally") to add Ally to this list. This addi-
tion will occur at the beginning of the chain. The public method add will call the private method
add with the invocation add("Ally", firstNode) . The reference in the argument firstNode is
copied to the parameter currentNode , and so it also references the first node in the chain, as
Figure 16-3b illustrates.

FIGURE 16-3

Recursively adding a node at the beginning of a chain

(a) The list before any additions

firstNode Bob Jill Mike Sue

(b) As add("Ally", firstNode) begins execution

firstNode

Bob Jill Mike Sue

currentNode

(c) After a new node is created (the base case)

firstNode

Sue

Bob Jill Mike

currentNode Ally

The private method returns the
reference that is in currentNode

(d) After the public add assigns the returned reference to firstNode

firstNode Bob Jill Mike Sue

currentNode

Ally