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

{

nodeBefore = currentNode;
currentNode = currentNode.getNextNode();
} // end while
return nodeBefore;
} // end getNodeBefore

Recall that the method compareTo returns a negative, zero, or positive integer according to
whether the comparison is, respectively, less than, equal to, or greater than.

Question 3 In the while statement of the method getNodeBefore , how important is the order
of the two boolean expressions that the operator && joins? Explain.

Question 4 What does getNodeBefore return if the sorted list is empty? How can you use
this fact to simplify the implementation of the method add given in Segment 16.10?

Question 5 Suppose that you use the previous method add to add an entry to a sorted list.
If the entry is already in the list, where in the list will add insert it? Before the first occur-
rence of the entry, after the first occurrence of the entry, after the last occurrence of the
entry, or somewhere else?

Question 6 What would be the answer to the previous question if you changed > to >= in
the while statement of the method getNodeBefore ?

16.12

Thinking recursively. Using recursion to process a chain of linked nodes can be an attractive alter-
native to an iterative approach. The basic concept is easy, but, as you will see, the implementation
is more involved, since Java passes objects to methods as references.
Recall from Segment 7.20 of Chapter 7 that you can process the chain's first node and then
process the rest of the chain recursively. Thus, to add a new node to a sorted chain of linked nodes,
you use the following logic:
if ( the chain is empty or the new node belongs at the beginning of the chain )
Add the new node to the beginning of the chain
else
Ignore the first node and add the new node to the rest of the chain

Figure 16-2 illustrates the logic needed to recursively add the name Luke to a sorted chain of
names. Since Luke is greater than Bob, you recursively consider the subchain that begins at Jill .
Luke is also greater than Jill , so you now consider the subchain beginning at Mike . Finally, Luke is
less than Mike , so you make the actual addition at the beginning of this subchain—that is, before
Mike . Adding to the beginning of a chain—or subchain—is the base case of this recursion. Happily,
the beginning of a chain is the easiest place to make an addition.
If currentNode initially references the chain and later references the rest of the chain, we can
add some detail to the previous logic, as follows:
if ( (currentNode == null ) or (newEntry <= currentNode.getData()) )
currentNode = new Node(newEntry, currentNode)
else
Recursively add newEntry to the chain beginning at currentNode.getNextNode()