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

FIGURE 16-2

Recursively adding Luke to a sorted chain of names

Luke Bob , so add Luke

to the rest of the chain

Bob Jill Mike Sue

firstNode

Luke Jill , so add Luke

to the rest of the chain

Jill Mike Sue

Luke Mike , so add Luke here, at

the beginning of the rest of the chain

Mike Sue

16.13

A recursive implementation of add . The example in Segment 7.20 displayed the contents of a
chain. Since that operation does not alter the chain, its recursive formulation was straightforward.
Obviously, in our present situation, the method add does alter the chain. Getting the recursive
method to make these changes is the challenge in Java.
Let's look at the recursive implementation of the method add before we describe why it works.
You learned in Segment 7.19 that you write a private method to perform the recursion and you
write a public method—typically the one that implements the ADT operation—to invoke this pri-
vate method. Thus, we have the following method definitions:

public void add(T newEntry)
{

firstNode = add(newEntry, firstNode);
numberOfEntries++;
} // end add
private Node add(T newEntry, Node currentNode)
{

if ( (currentNode == null ) ||
(newEntry.compareTo(currentNode.getData()) <= 0) )

{

currentNode = new Node(newEntry, currentNode);

}
else
{

Node nodeAfter = add(newEntry, currentNode.getNextNode());
currentNode.setNextNode(nodeAfter);
} // end if