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