Java Reference
In-Depth Information
Since Ally will be added to the beginning of the chain, the statement
currentNode = new Node("Ally", currentNode);
executes and creates a new node for Ally . This node is linked to the original chain, as Figure 16-3c
shows. Notice that firstNode is unchanged, even though it is the argument that corresponds to the
parameter currentNode .
The private method now returns the value of currentNode , and the public method add assigns
that value to firstNode . Thus, the chain with the completed addition appears as in Figure 16-3d.
16.15
Tracing an addition to the list's interior: the recursive calls. What happens when the addition
is not at the beginning of the original chain? Let's trace what happens when we add Luke to
the chain in Figure 16-4a. The public method add calls the private method add with the invo-
cation add("Luke", firstNode) . As in the previous segment, the reference in firstNode is
copied to the parameter currentNode , and so it also references the first node in the chain, as
Figure 16-4a illustrates.
Since Luke comes after Bob , another recursive call occurs:
add("Luke", currentNode.getNextNode())
The second argument is a reference to the chain's second node, the one containing Jill . This refer-
ence is copied to the parameter currentNode , as Figure 16-4b depicts.
Luke comes after Jill , so the recursive process is repeated again, and currentNode references
the chain's third node— Mike 's node—as shown in Figure 16-4c. Luke is less than Mike, so no
recursive call occurs. We are at the base case. A new node is created that contains Luke and refer-
ences Mike 's node, as Figure 16-4d illustrates.
16.16
Tracing the returns from the recursive method. Having just created a new node, the private
method add returns a reference to it, as Figure 16-4d indicates. The statement that invoked add now
resumes execution:
nodeAfter = add("Luke", currentNode.getNextNode());
Thus, nodeAfter is assigned a reference to the new node containing Luke , as Figure 16-4e
illustrates.
At this point, currentNode references Jill 's node, as it did in Part b of the figure. The next
statement to execute is
currentNode.setNextNode(nodeAfter);
Thus, the data field next in Jill 's node is changed to reference Luke 's node, as shown in Figure 16-4f.
The private method add now returns a reference to Jill 's node. If we continue the trace, we will
make Bob 's node reference Jill 's node and firstNode reference Bob 's node, even though these ref-
erences are already in place.
Note: A recursive addition to a chain of nodes locates and remembers the nodes prior to the
insertion point. After the portion of the chain that follows the insertion point is linked to the
new node, the recursion links the remembered nodes back into the chain.
Search WWH ::




Custom Search