Java Reference
In-Depth Information
same as for an unsorted dictionary. But here, since the array is sorted, the iteration will traverse the
dictionary in sorted search-key order.
We leave the completion of this implementation to you as an exercise.
20.15
Efficiency.
When
locateIndex
uses a binary search in the sorted array-based implementation, the
worst-case efficiencies of the dictionary operations are as follows:
Addition O(
n
)
Removal O(
n
)
Retrieval O(log
n
)
Traversal O(
n
)
This implementation is suitable for an application that creates a dictionary and then makes
many retrievals. This point from Chapter 14 bears repeating here:
Programming Tip:
When choosing an implementation for an ADT, you should consider
the operations that your application requires. If you use a particular ADT operation frequently,
you want its implementation to be efficient. Conversely, if you rarely use an operation, you can
afford to use a class that has an inefficient implementation of that operation.
Programming Tip:
Include comments in a class's implementation that advertise the effi-
ciencies of its methods.
Question 4
When the sorted array-based implementation of a dictionary uses a binary
search, its retrieval operation is O(log
n
). Since
add
and
remove
use a similar search, why
are they not O(log
n
) as well?
20.16
An implementation that uses an instance of Java's class
Vector
is similar in spirit to an array-
based implementation. You can use one or two vectors, much like the one or two arrays pictured
in Parts
a
and
b
of Figure 20-1. Since the underlying implementation of the class
Vector
is array
based, the algorithms for the dictionary operations and their efficiencies are essentially the same
whether you use an array or a vector.
With a vector, you do not need the private methods
ensureCapacity
,
makeRoom
, and
removeArrayEntry
that are in the array-based implementations. A vector accommodates the
addition of a new entry—expanding as necessary—without any extra effort by us. A vector
also shifts its entries if necessary when you either add or remove an entry. Lastly, a vector
counts its entries, so you do not have to.
20.17
As an example of how to use a vector to implement a dictionary, consider the sorted implementa-
tion outlined in Listing 20-3. The type parameters
K
and
V
of
SortedVectorDictionary
are like
those for
SortedArrayDictionary
shown in Listing 20-2 of Segment 20.9. The inner class
Entry
uses these type parameters, whereas the definition of
Entry
within
SortedArrayDictionary
(see
Listing 20-1 of Segment 20.2) defines its own type parameters. Although we could use either defi-
nition here, this simpler one is fine because we are not allocating an array of
Entry
objects.