Dictionary Implementations - Data Structures and Abstractions with Java - page 503

FIGURE 20-5

Removing an entry from a sorted array-based dictionary:
(a) search; (b) shift entries

(a)

Before removal

Search from the beginning
to find the entry to remove

(b)

1 2

After removal

To remove this entry, shift the contents of
subsequent array locations toward the
beginning of the array in the order indicated

The following algorithm describes the remove operation:
Algorithm remove(key)
// Removes an entry from the dictionary, given its search key, and returns its value.
// If no such entry exists in the dictionary, returns null .
result = null
Search the array for an entry containing key
if ( an entry containing key is found in the array )
{

result = value currently associated with key
Shift any entries that are after the located one to the next lower position in the array
Decrement the size of the dictionary

}
return result
We leave the implementation of this algorithm as an exercise. Defining the following private method
will be helpful:

// Removes an entry at a given index by shifting array
// entries toward the entry to be removed.
private void removeArrayEntry( int keyIndex)

20.14

The remaining methods. At the heart of the method getValue , which retrieves the value in an
existing entry given its search key, is the method locateIndex , as described earlier. Since the array
of entries is sorted, locateIndex can use a binary search, as Question 3 indicated.
An iteration, or traversal, of the entries in the dictionary starts with the first entry in the array
and moves sequentially through the remaining entries. This part of the implementation can be the