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

Coincidentally, SortedList 's add method overrides the other add method in LList that adds to the
end of a list.
We would make similar changes to the methods remove and getPosition . The remaining
methods of the sorted list are inherited from LList , and so they do not appear explicitly in
SortedList .

Question 1 Although SortedList inherits the method contains from LList , the method is
not as efficient as it could be. Why? Show how you could override contains with a more
efficient version.

17.2

A pitfall. This implementation contains a pitfall that is the direct result of using inheritance.
Although SortedList conveniently inherits methods such as isEmpty from LList , it also inherits
two methods that a client can use to destroy the order of a sorted list. These two methods appear in
ListInterface as follows:
/** Adds newEntry to the list at position newPosition. */
public boolean add( int newPosition, T newEntry);

/** Replaces the entry at givenPosition with newEntry. */
public boolean replace( int givenPosition, T newEntry);

If a client writes
SortedList<String> sList = new SortedList<String>();
for example, sList can invoke any method declared in either SortedListInterface or
ListInterface , including the previous methods add and replace . Thus, a client could
destroy the order of the entries in a sorted list either by adding an entry out of order or
by replacing an entry.

17.3

Possible ways to avoid the pitfall. What can we do to avoid this pitfall? Here are three possibilities:

•

Use SortedListInterface in the declaration of the sorted list. For example, if the
client contains
SortedListInterface<String> sList = new SortedList<String>();
sList can invoke only methods declared within SortedListInterface . Notice that the list
operations add and replace do not appear in SortedListInterface . Although this can be a
good programming practice, that is all it is. A client need only ignore this practice and define
the data type of sList as SortedList to have all operations of the ADT list available to it.
You have already seen how a client can sabotage the sorted list in this case.

• Implement the list's add and replace methods within the class SortedList , but have them

return false. For example, add could appear as follows:
public boolean add( int newPosition, T newEntry)
{

return false ;
} // end add
This version of add overrides the version that LList implements. If the client invokes this
method, the sorted list will remain unchanged. The client can detect that the method was
unsuccessful, but not why.