Programming and Problem Solving with Java

11.4 S o r t e d L i s t | 547

june june

susy

susy sarah bobby judy

june

sarah

susy

bobby

june

sarah

susy

bobby

judy

june

sarah

susy

Put susy

at end

of the

list.

Move susy

down and

insert sarah.

Move susy,

sarah and june

down and

insert bobby.

Move susy,

sarah and june

down and

insert judy.

Insert june

Figure 11.7 Inserting into a Sorted List

Notice that this algorithm works even if the list is empty. When the list is empty,numItems
is 0 and the body of the whileloop is not entered. Thus itemis stored into listItems[0], and
numItemsis incremented to 1. Does the algorithm work if itemis the smallest value? What about
the largest value? Let’s see. If itemis the smallest value, the loop body executes numItems
times and indexis 1. Thus itemis stored into position 0, where it belongs. If itemis the
largest value, the loop body is not entered. The value of indexremains numItems1, so item
is stored into listItems[numItems], where it belongs.
Are you surprised that the general case also takes care of the special cases? This situa-
tion does not happen all the time, but it occurs sufficiently often that it is good programming
practice to start with the general case. If we begin with the special cases, we may still gen-
erate a correct solution, but we may not realize that we don’t need to handle the special
cases separately. Thus we have this guideline: Begin with the general case, then treat as spe-
cial cases only those situations that the general case does not handle correctly.
The methods deleteand getNextItemmust maintain the sorted order—but they already
do! An item is deleted by removing it and shifting all of the items larger than the one deleted
up by one position; getNextItemmerely returns a copy of an item—it does not change an
item. Only insertneeds to be overridden in the derived class SortedList.

packagelist;
public classSortedList extendsList
{