Programming and Problem Solving with Java

11.3 S o rting the List Items | 539

11.3 Sorting the List Items

getNextItempresents the items to the user in the order in which they were inserted. Depending
on how we are using the list, sometimes we might want to rearrange the list components into
a certain order before an iteration. For example, if the list holds names for wed-
ding invitations, we might want to see the names in alphabetic order. Arranging
list items into order is a very common operation and is known in software ter-
minology as sorting.
If you were given a sheet of paper with a column of 20 names on it and were
asked to write them in ascending order, you would probably do the following:

1.Make a pass through the list, looking for the lowest name (the one that

comes first alphabetically).

2.Write it on the paper in a second column.

3.Cross the name off the original list.

4.Repeat the process, always looking for the lowest name remaining in the orig-

inal list.

5.Stop when all names have been crossed off.

We could implement this algorithm as client code, using getNextItemto go through the
list searching for the lowest value. When we found it, we could insert it into another list and
delete it from the original. However, we would need two lists—one to hold the original list
and a second to hold the sorted list. In addition, the client would have destroyed the origi-
nal list. If the list is large, we might not have enough memory to maintain two copies, even
if one is empty. A better solution is to derive a class from Listthat has a sort method that
rearranges the values in the list. Because the data fields in Listare declared protected, we
can inherit them. By accessing the values directly within the list, we can avoid maintaining
two lists.
Let’s call our derived class ListWithSort.

Responsibility Algorithms for Class ListWithSort

The constructor takes the maximum number of items and calls List’s constructor. None of
the other methods needs to be overridden.

Class Name: ListWithSort Superclass: List Subclasses:

Responsibilities Collaborations

Create itself (maxItems) super

Sort the items in the list String

Sorting Arranging the compo-

nents of a list into order (for in-

stance, words into alphabetical

order or numbers into ascend-

ing or descending order)