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

private T data;
private Node next;

< Constructors >
. . .
< Accessor and mutator methods: getData , setData , getNextNode , setNextNode >
. . .

} // end Node
} // end SortedLinkedList

The Method add
16.8

Locating the insertion point. Adding an entry to a sorted list requires that you find where in the
list the new entry belongs. Since the entries are sorted, you compare the new entry with the entries
in the sorted list until you reach an entry that is not smaller than the new entry. Figure 16-1 depicts
a chain of linked nodes, each containing a name, sorted alphabetically. The figure shows where the
additional names Ally , Cathy , Luke , Sue , and To m would be inserted into the chain and the compar-
isons that would have to occur to arrive at those locations.

FIGURE 16-1

Places to insert names into a sorted chain of linked nodes

Ally Bob Cathy Jill Luke Mike Sue Sue To m Sue

Sue

Bob Jill Mike

firstNode

You can see from the figure that, in a string comparison, Ally is less than Bob , and so it would
be inserted at the beginning of the chain. To see where to insert Luke , you would find that Luke is
greater than both Bob and Jill but less than Mike . Thus, Luke belongs before Mike in the chain. Sue ,
on the other hand, is already in one of the nodes. You would discover that Sue is greater than Bob ,
Jill , and Mike but not greater than Sue . So you would insert the new entry Sue just before the exist-
ing entry Sue . Finally, To m is greater than all the current names in the list, so you would add it to the
end of the chain.

Note: Given a sorted list with entries in ascending order, you insert a new entry just before
the first entry that is not smaller than the new entry.

16.9

The algorithm. Recall from Segment 14.10 of Chapter 14 that you handle the addition of a new
node to the beginning of a chain differently from an addition at other points in the chain. Adding to
the beginning is easy, since firstNode references the first node in the chain. To add anywhere else,
you need a reference to the node that will ultimately occur before the new node. Thus, while you
traverse the chain of linked nodes to discover where the new entry belongs, you must retain a refer-
ence to the node prior to the one under consideration.