Java Reference
In-Depth Information
<
Data fields as shown in Listing 20.1 of Segment 20.2
>
. . .
<
Constructors analogous to those in Listing 20.1
>
. . .
public
V add(K key, V value)
{
. . .
<
See Segment 20.11.
>
}
// end add
<
Implementations of other methods in
DictionaryInterface
>
. . .
<
The private class
Entry
, as shown in Listing 20.1.
>
}
// end SortedArrayDictionary
20.10
Adding an entry.
When the dictionary's key-value entries are sorted by their search keys, adding a
new entry requires a search of the array of entries to see where the new entry belongs. After you deter-
mine the correct position for the new entry, you must make room for it in the array. You do this by
shifting subsequent array entries up by one position, beginning at the last entry, as Figure 20-4 shows.
You then insert the new entry into the array so it is in its proper order by search key.
The following algorithm for adding an entry has similarities to the one given in Segment 20.4
for an unsorted dictionary:
Algorithm
add(key, value)
//
Adds a new key-value entry to the dictionary and returns
null
. If
key
already exists
//
in the dictionary, returns the corresponding value and replaces it with
value
.
result
=
null
Search the array until you either find an entry containing
key
or locate the point where it
should be
if
(
an entry containing
key
is found in the array
)
{
result =
value currently associated with
key
Replace
key
's associated value with
value
}
else
//
insert new entry
{
if
(
array is full
)
Double size of array
Make room in the array for a new entry at the index determined by the previous search
Insert a new entry containing
key
and
value
into the vacated location of the array
Increment the size of the dictionary
}
return
result
