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

16.24

The implementation of getPosition . In the following implementation of getPosition , the while
loop finds anEntry 's position in the sorted list, and the if statement sees whether anEntry is in the list.

public int getPosition(T anEntry)
{

int position = 1;
int length = list.getLength();
// find position of anEntry
while ( (position <= length) &&
(anEntry.compareTo(list.getEntry(position)) > 0) )

{

position++;
} // end while
// see whether anEntry is in list
if ( (position > length) ||
(anEntry.compareTo(list.getEntry(position)) != 0) )

{

position = -position; // anEntry is not in list
} // end if
return position;
} // end getPosition

Question 12 Assume that the sorted list nameList contains the four names Brenda , Carlos ,
Sarah , and To m as strings. By tracing the code for getPosition , see what getPosition
returns when anEntry represents
a. Carlos b. Alan c. Wendy d. To m e. Jamie

Question 13 Since you can decide whether a given entry is in a particular sorted list by
testing the sign of the integer that getPosition returns, you can use getPosition to imple-
ment the method contains . Write such an implementation.

16.25

Each of the remaining methods— contains , remove , getEntry , clear , getLength , isEmpty , and
toArray —has the same specifications as in the ADT list. Each can simply invoke the corre-
sponding list method. For example, the method getEntry has the following implementation in
SortedList :

public T getEntry( int givenPosition)
{

return list.getEntry(givenPosition);
} // end getEntry

Question 14 You can implement the method contains by invoking either getPosition , as
Question 13 suggests, or the ADT list's contains method. Which of these implementations
will execute faster when the entry sought is not present in the sorted list? Why?

Efficiency Issues

Except perhaps for some subtle logic in getPosition , you can write the previous implementation
quickly and with few, if any, errors. Saving human time is an attractive feature of using an exist-
ing class to build another. But does the implementation use computer time efficiently? In this
particular implementation, several methods invoke getPosition , so their efficiency depends on
getPosition 's efficiency.