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

16.22

The method remove . We also use getPosition when removing an object from a sorted list. This time,
however, we do need to know whether the given entry exists in the sorted list. If it does not exist, we can-
not remove it. In such cases, remove returns false. Also notice that the method uses the operation remove
of the ADT list to make the deletion. Thus, the method has the following implementation:

public boolean remove(T anEntry)
{

boolean result = false ;
int position = getPosition(anEntry);
if (position > 0)
{

list.remove(position);

result = true ;
} // end if
return result;
} // end remove

Question 11 If a sorted list contains five duplicate objects and you use the previous
method remove to remove one of them, what will be removed from the list: the first occur-
rence of the object, the last occurrence of the object, or all occurrences of the object?

16.23

The logic for getPosition . Implementing getPosition is somewhat harder than implementing
the previous two methods. To decide where in the list anEntry is or belongs, we need to compare
anEntry to the entries already in the list, beginning with the first one. If anEntry is in the list, we
obviously compare entries until we find a match. However, if anEntry is not in the list, we want to
stop the search at the point where it belongs in the sorted list. We take advantage of the sorted order
of the objects by using logic similar to that described in Segment 16.8.
For example, suppose that the sorted list contains the four names Brenda , Carlos , Sarah , and
To m . If we want to see where Jamie belongs in the sorted list, we discover that, as strings,
Jamie > Brenda
Jamie > Carlos
Jamie < Sarah
Thus, Jamie belongs after Carlos but before Sarah —that is, at position 3 in the sorted list, as
Figure 16-7 illustrates.
To compare anEntry to an entry in the sorted list, we first use the list operation getEntry to
return the entry at a given position within the sorted list. Then the expression

anEntry.compareTo(list.getEntry(position))

makes the comparison.

FIGURE 16-7

A sorted list in which Jamie belongs after Carlos but before Sarah

Brenda
Carlos
Sarah
To m

Jamie