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.