Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 137

/ ** @returnListsize * /
publicintsize()
{returnlist.length();}
}
Figure4.33 (continued)
As an alternative, we could implement the dictionary using a linked list. The
implementation would be quite similar to that shown in Figure 4.33, and the cost
of the functions should be the same asymptotically.
Another alternative would be to implement the dictionary with a sorted list. The
advantage of this approach would be that we might be able to speed up the find
operation by using a binary search. To do so, first we must define a variation on
the List ADT to support sorted lists. A sorted list is somewhat different from
an unsorted list in that it cannot permit the user to control where elements get
inserted. Thus, the insert method must be quite different in a sorted list than in
an unsorted list. Likewise, the user cannot be permitted to append elements onto
the list. For these reasons, a sorted list cannot be implemented with straightforward
inheritance from the List ADT.
The cost for find in a sorted list is (log n) for a list of length n. This is a
great improvement over the cost of find in an unsorted list. Unfortunately, the
cost of insert changes from constant time in the unsorted list to (n) time in
the sorted list. Whether the sorted list implementation for the dictionary ADT is
more or less efficient than the unsorted list implementation depends on the relative
number of insert and find operations to be performed. If many more find
operations than insert operations are used, then it might be worth using a sorted
list to implement the dictionary. In both cases, remove requires (n) time in the
worst and average cases. Even if we used binary search to cut down on the time to
find the record prior to removal, we would still need to shift down the remaining
records in the list to fill the gap left by the remove operation.
Given two keys, we have not properly addressed the issue of how to compare
them. One possibility would be to simply use the basic == , <= , and >= operators
built into Java. This is the approach taken by our implementations for dictionar-
ies shown in Figure 4.33. If the key type is int , for example, this will work
fine. However, if the key is a pointer to a string or any other type of object, then
this will not give the desired result. When we compare two strings we probably
want to know which comes first in alphabetical order, but what we will get from
the standard comparison operators is simply which object appears first in memory.
Unfortunately, the code will compile fine, but the answers probably will not be fine.
In a language like C ++ that supports operator overloading, we could require
that the user of the dictionary overload the == , <= , and >= operators for the given
key type. This requirement then becomes an obligation on the user of the dictionary