Java Reference
In-Depth Information
7.21
Displaying a chain backwards.
Suppose that you want to traverse a chain of linked nodes in
reverse order. In particular, suppose that you want to display the object in the last node, then the one
in the next-to-last node, and so on working your way toward the beginning of the chain. Since each
node references the next node but not the previous one, using iteration for this task would be diffi-
cult. You could traverse to the last node, display its contents, go back to the beginning and traverse
to the next-to-last node, and so on. Clearly, however, this is a tedious and time-consuming
approach. Alternatively, you could traverse the chain once and save a reference to each node. You
could then use these references to display the objects in the chain's nodes in reverse order. A recur-
sive solution would do this for you.
If a friend could display the nodes in reverse order, beginning with the second node, you could
display the first node and complete the task. The following recursive solution implements this idea:
public void
displayBackward()
{
displayChainBackward(firstNode);
}
// end displayBackward
private void
displayChainBackward(Node nodeOne)
{
if
(nodeOne !=
null
)
{
displayChainBackward(nodeOne.getNextNode());
System.out.println(nodeOne.getData());
}
// end if
}
// end displayChainBackward
Note:
Traversing a chain of linked nodes in reverse order is easier when done recursively
than iteratively.
Question 6
Trace the previous method
displayBackward
for a chain of three nodes.
Chapter 4 showed you how to measure an algorithm's time requirement by using Big Oh notation.
We used a count of the algorithm's major operations as a first step in selecting an appropriate
growth-rate function. For the iterative examples we examined, that process was straightforward.
We will use a more formal technique here to measure the time requirement of a recursive algorithm
and thereby choose the right growth-rate function.
As a first example, consider the
countDown
method given in Segment 7.3. The size of the prob-
lem of counting down to 1 from a given integer is directly related to the size of that integer. Since
Chapter 4 used
n
to represent the size of the problem, we will rename the parameter
integer
in
countDown
to
n
to simplify our discussion. Here is the revised method:
public static void
countDown(
int
n)
{
System.out.println(n);
if
(n
>
1)
countDown(n - 1);
}
// end countDown