Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 138

class. Unfortunately, this obligation is hidden within the code of the dictionary (and
possibly in the user's manual) rather than exposed in the dictionary's interface. As
a result, some users of the dictionary might neglect to implement the overloading,
with unexpected results. Again, the compiler will not catch this problem.
The Java Comparable interface provides an approach to solving this prob-
lem. In a key-value pair implementation, the keys can be required to implement
the Comparable interface. In other applications, the records might be required
to implement Comparable
The most general solution is to have users supply their own definition for com-
paring keys. The concept of a class that does comparison (called a comparator)
is quite important. By making these operations be generic parameters, the require-
ment to supply the comparator class becomes part of the interface. This design
is an example of the Strategy design pattern, because the “strategies” for compar-
ing and getting keys from records are provided by the client. Alternatively, the
Comparable class allows the user to define the comparator by implementing the
compareTo method. In some cases, it makes sense for for the comparator class
to extract the key from the record type, as an alternative to storing key-value pairs.
We will use the Comparable interface in Section 5.5 to implement compari-
son in heaps, and in Chapter 7 to implement comparison in sorting algorithms.

4.5 Further Reading

For more discussion on choice of functions used to define the List ADT, see the
work of the Reusable Software Research Group from Ohio State. Their definition
for the List ADT can be found in [SWH93]. More information about designing
such classes can be found in [SW94].

4.6 Exercises

4.1 Assume a list has the following configuration:

hj 2; 23; 15; 5; 9 i:

Write a series of Java statements using the List ADT of Figure 4.1 to delete
the element with value 15.
4.2 Show the list configuration resulting from each series of list operations using
the List ADT of Figure 4.1. Assume that lists L1 and L2 are empty at the
beginning of each series. Show where the current position is in the list.

(a) L1.append(10);
L1.append(20);
L1.append(15);