Inheritance and Lists - Data Structures and Abstractions with Java - page 430

In an attempt to avoid this duplication of effort, Chapter 16 used an instance of the ADT list
to contain the entries of the sorted list. This list was a data field of the class implementing the
sorted list. The result was an implementation that you could write quickly, because the imple-
mentation of the list had done most of the work. But since the sorted list operations used the list
in the same way that a client would, these operations were inefficient of time when the ADT list
had a linked implementation.
But what if, instead of using composition, as we did in Chapter 16, we use inheritance? This
chapter looks at the implications of deriving a sorted list from a list. In doing so we'll find that a
subclass (derived class) can be more efficient if it can access the underlying data structures of its
superclass (base class). This is possible if the superclass includes methods that enable future sub-
classes to examine or modify its data fields. A class designer should plan for the future use of a
class as well as the present need.

Using Inheritance to Implement a Sorted List

17.1

Recall the implementation of the class SortedList that we developed in Chapter 16 beginning at
Segment 16.20. SortedList has an instance of another class, LList in this case, as a data field.

SortedList and LList have a has-a relationship. Several of SortedList 's methods—namely
remove (by position), getEntry , contains , clear , getLength , isEmpty , and toArray —behave like
LList 's methods. If SortedList inherited these methods from LList , we would not have to imple-
ment them again, as we did in the previous chapter. Thus, we could revise SortedList as follows:

VideoNote

Inheritance and ADT
implementations

public class SortedList<T extends Comparable<? super T>>
extends LList<T> implements SortedListInterface<T>

{

public void add(T newEntry)
{

int newPosition = Math.abs(getPosition(newEntry));
super .add(newPosition, newEntry);
} // end add
< Implementations of remove(anEntry) and getPosition(anEntry) go here. >
. . .
} // end SortedList

The notation T extends Comparable<? super T> , introduced in Segments 8.1 and 8.2,
defines the generic type T . The class that T represents must implement the interface Comparable.
Writing ? super T , which means any superclass of T , allows some flexibility when using the method
compareTo .
You can see that SortedList is derived from LList . Also notice that we have omitted the data
field list and the default constructor that appeared in Segment 16.20. To revise the add method
given in Segment 16.21, we simply replaced list with super . That is, we wrote

super .add(newPosition, newEntry);

to invoke the add operation of the ADT list, instead of
list.add(newPosition, newEntry);