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.
The Time Efficiency of Recursive Methods
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.
The Time Efficiency of countDown
7.22
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
 
 
 
Search WWH ::




Custom Search