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

result = value currently associated with key
Replace key 's associated value with value

}
else
{

Allocate a new node containing key and value
Increment the size of the dictionary
if ( the chain is empty or the new entry belongs at the beginning of the chain )
Add the new node to the beginning of the chain

else

Insert the new node before the last node that was examined during the search

}
return result

20.24

Listing 20-5 shows the beginning of the class SortedLinkedDictionary and the implementation of
the method add . Implementations for the methods remove and getValue are similar to the imple-
mentation for add , but are a bit simpler. We leave them as exercises.

LISTING 20-5

The class SortedLinkedDictionary

import java.util.Iterator;
import java.util.NoSuchElementException;
/**

A class that implements a dictionary by using a sorted linked chain.
@author Frank M. Carrano

*/
public class SortedLinkedDictionary<K extends Comparable<? super K>, V>
implements DictionaryInterface<K, V>

{

private Node firstNode; // reference to first node of chain
private int numberOfEntries;

public SortedLinkedDictionary()
{

firstNode = null ;
numberOfEntries = 0;
} // end default constructor

public V add(K key, V value)
{

V result = null ;

// search chain until you either find a node containing key
// or pass the point where it should be
Node currentNode = firstNode;
Node nodeBefore = null ;
while ( (currentNode != null ) &&
key.compareTo(currentNode.getKey()) > 0 )