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

An Unsorted Linked Dictionary
20.22

Since the entries in an unsorted dictionary are in no particular order, you add a new entry in the
most efficient manner. When the entries are in a linked chain, such as the one in Figure 20-6c, the
fastest addition is at the beginning of the chain, as Figure 20-7 shows. (If the class also maintains a
tail reference to the last node of the chain, adding an entry after the last node would be equally fast.)
While this aspect of an addition is O(1), preventing duplicate search keys would require a sequen-
tial search from the beginning of the chain.

FIGURE 20-7

Adding to an unsorted linked dictionary

Insert a new node at the beginning of the chain

firstNode

Just as you would for an array, you would have to look at all the search keys in the chain to learn
that a particular entry was not present. Removing or retrieving an entry uses a similar search. A tra-
versal of either the search keys or the values involves the entire chain. Thus, for this implementa-
tion, the worst-case efficiencies of the operations are as follows:

Addition O( n )

Removal O( n )

Retrieval O( n )

Traversal O( n )

Question 5 To remove an entry from an unsorted array-based dictionary, we replaced the
removed entry with the last entry in the array (see Segment 20.6). Should we use the same
strategy to remove an entry from an unsorted linked dictionary? Explain.

A Sorted Linked Dictionary
20.23

Adding an entry. When the nodes in a chain are sorted by their search keys, adding a new entry to
the dictionary requires a sequential search of the chain from its beginning to determine the correct
location for the new node. Since the search keys are sorted, you can detect that a desired search key
does not exist in the chain as soon as you pass the node that should have contained it. That is, you do
not have to look at the entire chain, as you would if the search keys were unsorted. Segments 18.8 and
18.22 in Chapter 18 describe this variation of a sequential search.
The following algorithm adds a new entry to a sorted linked 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 chain until either you find a node containing key or you pass the point where
it should be
if ( a node containing key is found in the chain )
{