Java Reference
In-Depth Information
The addition or removal of an entry is an O(
n
) operation regardless of whether you use an
array, a vector, or a chain to implement a dictionary. Realize, however, that an array requires you to
shift its elements, whereas a linked chain does not. Also, the preceding linked implementation does
not require a good estimate of the dictionary's ultimate size. When you use an array that is too
small, you can expand it by copying its entries to a new, larger array, but this takes time. If you use
an array that is larger than necessary, you waste space. The same is true if you use a vector, but nei-
ther of these situations occur with a linked implementation.
C
HAPTER
S
UMMARY
•
You can implement a dictionary by using either an array, a vector, or a chain of linked nodes. A linked
implementation does not require a good estimate of the dictionary's ultimate size. When you use an array
that is too small, you need to copy its entries to a new, larger array. If you use an array that is larger than nec-
essary, you waste space. The same is true if you use a vector, but neither of these situations occur with a
linked implementation.
•
The worst-case efficiencies of the dictionary operations for array-based and linked implementations are as
follows:
Array-Based
Linked
Unsorted
Sorted
Unsorted
Sorted
Addition
Removal
Retrieval
Traversal
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(log
n
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
•
For a sorted or unsorted dictionary, the addition or removal of an entry is an O(
n
) operation regardless of
whether you use an array, a vector, or a chain to implement it. Realize, however, that an array or vector
requires the shifting of its entries, whereas a linked chain does not.
•
Using either an array or a vector to implement a sorted dictionary allows for an efficient retrieval operation
because you can use a binary search.
•
To implement the method
getKeyIterator
or
getValueIterator
, define a private inner class for the dic-
tionary class. This private class should implement the interface
java.util.Iterator
.
P
ROGRAMMING
T
IP
•
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. Con-
versely, if you rarely use an operation, you can afford to use a class that has an inefficient implementation of
that operation.
•
Include comments in a class's implementation that advertise the efficiencies of its methods.
E
XERCISES
1.
Begin an array-based implementation of the ADT dictionary according to the data structure illustrated in
Figure 20-1b. Declare the data fields, define the constructors, and define the method
add
for unsorted data. Use
arrays that you can resize during execution.