Java Reference
In-Depth Information
return
result;
}
// end remove
20.7
The remaining methods.
We leave the rest of the dictionary implementation to you as an exer-
cise, since it is not difficult once you have reached this point. Note that an iteration, or traversal,
of the dictionary entries simply moves from location to location within the array. Since the
search keys are not sorted, the order of the iteration is not specified. Whatever order is easy to
implement is fine. Typically, you start with the first entry in the array and move sequentially
through the remaining entries.
20.8
Efficiency.
For this implementation, the worst-case efficiencies of the operations are as follows:
Addition
O(
n
)
Removal
O(
n
)
Retrieval
O(
n
)
Traversal
O(
n
)
Even though additions occur after the last entry in the array
dictionary
without shifting any data,
the search necessary to prevent duplicate search keys in the dictionary makes the overall operation
O(
n
). Deletions and retrievals use a similar search of the array, making them O(
n
) as well. Finally,
traversing an array is an O(
n
) operation.
Realize that if you fill the array of dictionary entries, you must allocate a new, larger array and
copy entries from the original array to the new array. This requirement adds overhead to any array-
based implementation that the previous analysis does not reflect. In Java, the array entries are refer-
ences to objects, so copying the array is fast. But for languages whose arrays contain objects
instead of references, copying can be quite time-consuming. Ideally, you want to choose a suffi-
ciently large array, but not one that wastes space because it is overly large.
Some of the implementation for an unsorted dictionary, as shown in Segment 20.2, is independent
of the order of the dictionary's entries, and so can be used for a sorted dictionary. However, the
search keys must belong to a class that implements the interface
Comparable
so that we can order
them. An outline for an implementation of a sorted dictionary appears in Listing 20-2. The notation
K
extends
Comparable<?
super
K>
, which was first introduced in Segment 8.2 of Chapter 8,
defines the generic type
K
. It allows us to compare objects of type
K
with either objects of type
K
or
objects of any superclass of
K
.
LISTING 20-2
An outline of the class
SortedArrayDictionary
import
java.util.Arrays;
import
java.util.Iterator;
import
java.util.NoSuchElementException;
/**
A class that implements a dictionary by using a sorted array.
@author Frank M. Carrano
*/
public class
SortedArrayDictionary<K
extends
Comparable<?
super
K>, V>
implements
DictionaryInterface<K, V>
