Sorted Lists - Data Structures and Abstractions with Java - page 421

FIGURE 16-6

An instance of a sorted list that contains a list of its entries

Ann
Ben
Meg
Rob

An instance of a list

An instance of a sorted list

16.20

Our class SortedList will implement the interface SortedListInterface . We begin this class by
declaring a list as a data field and defining a default constructor. We assume that the class LList , as
discussed in Chapter 14, is an implementation of the interface ListInterface for the ADT list.
Thus, our class begins as follows:

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

{

private ListInterface<T> list;
public SortedList()
{

list = new LList<T>();
} // end default constructor
. . .
} // end SortedList

Note our use of the generic type T when we declare the data field list and create an instance of LList .

16.21

The method add . The implementations of the operations of the ADT sorted list are brief, as the list
does most of the work. To add a new entry to the sorted list, we first use the method getPosition ,
which is an operation of the sorted list. We assume that it is already implemented, even though we
have not written it yet. Recall that getPosition finds the position of an existing entry within a
sorted list, or the position at which we should insert a new entry that does not occur in the sorted
list. The method sets the sign of the integer it returns to indicate whether the entry exists in the list
already. When adding an entry to a sorted list that can contain duplicate entries, it does not matter
whether the entry exists in the sorted list already. Thus, we can ignore the sign of the integer that
getPosition returns. Notice that the following implementation uses the method abs of the class
Math to discard this sign. It also uses the add operation of the ADT list. (In this section, calls to
ADT list operations are highlighted.)

public void add(T newEntry)
{

int newPosition = Math.abs(getPosition(newEntry));

list.add(newPosition, newEntry);

} // end add

Question 9 Repeat Question 5, using the method add that was just given.

Question 10 Can a client of SortedList invoke the operation add(position, entry) of
the ADT list? Explain.