Java Reference
In-Depth Information
If your application creates a list and then at some point needs to sort the list's entries into
numerical or alphabetical order, for example, you can add a sort operation to the ADT list. You can
use one of the algorithms given in Chapters 8 and 9 to implement this operation. But when your
application requires only sorted data, having an ADT that orders the data for you would be more
convenient than the ADT list. The sorted list is such an ADT.
When you either add an entry to or remove an entry from a sorted list, you provide only
the entry. You do not specify where in the list the entry belongs or exists. The ADT determines
this for you.
This chapter describes the operations of the ADT sorted list, provides examples of using a
sorted list, and presents two possible Java implementations. One of these implementations uses the
ADT list, but it is not especially efficient. The next chapter addresses the reuse of a class and pro-
vides a more efficient implementation of the sorted list as it discusses the use of inheritance.
16.1
The ADT list leaves it up to the client to arrange the objects in a given collection. The client can
maintain the objects in any order that meets its needs. Suppose that you want a list of names or
other strings that are in alphabetical order. You could certainly use the ADT list for this task, but
you would have to determine the position that each string should have within the list. Wouldn't it be
more convenient if the list itself alphabetized the entries as you added them? What you need is a
different ADT, namely the
sorted list
.
Recall that to use the
add
operation of the ADT list, you must specify both the new entry and
its desired position within the list. Such an operation is not desirable for the ADT sorted list, since
the sorted list is responsible for organizing its entries. If you were allowed to specify a new entry's
position, you might destroy the order of the sorted list's entries. Instead, the
add
operation of the
ADT sorted list requires only the new entry. The operation compares the new entry to other entries
in the sorted list to determine the new entry's position. Thus, the entries in a sorted list must be
objects that can be compared with one another.
What, then, can you place in a sorted list? One possibility is strings, since the class
String
pro-
vides a
compareTo
method for comparing two strings. In general, you can have a sorted list of any
objects of a class that has a
compareTo
method. As you saw in Segment D.20 of Appendix D and
again at the beginning of Chapter 8, such classes implement the interface
Comparable
. Since Java's
wrapper classes, such as
Integer
and
Double
, implement the
Comparable
interface, you can place
instances of them into a sorted list.
16.2
Let's examine the possible operations for this ADT. For simplicity, we will allow the sorted list to
contain duplicate items. Insisting that the sorted list contain only unique items is somewhat more
complicated, and we will leave this variation as an exercise.
We've already mentioned that you can add an entry to the sorted list. Since the sorted list deter-
mines the position of a new entry, you could ask the ADT for this position. That is, you could ask
for the position of an existing entry or for the position in which a proposed entry would occur if you
added it to the list. You could also ask the ADT whether it contained a particular entry. And clearly
you should be able to remove an entry.
Let's specify these operations more carefully.
