public class SortedLinkedDictionary
1: import java.util.Iterator;
2: import java.util.NoSuchElementException;
3: /**
4: A class that implements a dictionary by using a sorted linked chain.
5: The dictionary has distinct search keys.
6:
7: @author Frank M. Carrano
8: @author Timothy M. Henry
9: @version 4.0
10: */
11: public class SortedLinkedDictionary<K extends Comparable<? super K>, V>
12: implements DictionaryInterface<K, V>
13: {
14: private Node firstNode; // Reference to first node of chain
15: private int numberOfEntries;
16:
17: public SortedLinkedDictionary()
18: {
19: initializeDataFields();
20: } // end default constructor
21:
22: public V add(K key, V value)
23: {
24: V result = null;
25:
26: // Search chain until you either find a node containing key
27: // or locate where it should be
28: Node currentNode = firstNode;
29: Node nodeBefore = null;
30:
31: while ( (currentNode != null) && (key.compareTo(currentNode.getKey()) > 0) )
32: {
33: nodeBefore = currentNode;
34: currentNode = currentNode.getNextNode();
35: } // end while
36:
37: if ( (currentNode != null) && key.equals(currentNode.getKey()) )
38: {
39: // Key in dictionary; replace corresponding value
40: result = currentNode.getValue(); // Get old value
41: currentNode.setValue(value); // Replace value
42: }
43: else // Key not in dictionary; add new node in proper order
44: {
45: // Assumes key and value are not null
46: Node newNode = new Node(key, value); // Create new node
47:
48: if (nodeBefore == null)
49: { // Add at beginning (includes empty dictionary)
50: newNode.setNextNode(firstNode);
51: firstNode = newNode;
52: }
53: else // Add elsewhere in non-empty list
54: {
55: newNode.setNextNode(currentNode); // currentNode is after new node
56: nodeBefore.setNextNode(newNode); // nodeBefore is before new node
57: } // end if
58: numberOfEntries++; // Increase length for both cases
59: } // end if
60:
61: return result;
62: } // end add
63: /* < Implementations of other methods in DictionaryInterface. >
64: . . . */
65:
66: /* < Private classes KeyIterator and ValueIterator (see Segment 20.20). >
67: . . . */
68:
69: private class Node
70: {
71: private K key;
72: private V value;
73: private Node next;
74: /* < Constructors and the methods getKey, getValue, setValue, getNextNode,
75: and setNextNode are here. There is no setKey. >
76: . . . */
77: } // end Node
78: } // end SortedLinkedDictionary
79: