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.
 
 
Search WWH ::




Custom Search