|
| 1 | +/** |
| 2 | + * Symbol table implementation with sequential search in an unordered linked |
| 3 | + * list of key-value pairs. |
| 4 | + * The `SequentialSearchST` class represents an (unordered) symbol table of |
| 5 | + * generic key-value pairs. |
| 6 | + * It supports the usual `put`, `get`, `contains`, `delete`, `size`, and `is-empty` |
| 7 | + * methods. |
| 8 | + * It also provides a `keys` method for iterating over all of the keys. |
| 9 | + * A symbol table implements the `associative array` abstraction: when associating |
| 10 | + * a value with a key that is already in the symbol table, the convention is to |
| 11 | + * replace the old value with the new value. |
| 12 | + * The class also uses the convention that values can't be `null`. Setting the value |
| 13 | + * associated with a key to `null` is equivalent to deleting the key from the symbol |
| 14 | + * table. |
| 15 | + * |
| 16 | + * This implementation uses a singly-linked list and sequential search. |
| 17 | + * It relies on the `equals()` method to test whether two keys are equal. It does not |
| 18 | + * call either the `compareTo` or `hashCode()` method. |
| 19 | + * The `put` and `delete` operations take linear time; The `get` and `contains` operation |
| 20 | + * takes linear time in the worst case. The `size` and `is-empty` operation take constant |
| 21 | + * time. Construction takes constant time. |
| 22 | + * |
| 23 | + */ |
| 24 | +public class SequentialSearchST<Key, Value> { |
| 25 | + private int n; // number of key-value pairs |
| 26 | + private Node first; // the linked list of key-value pairs |
| 27 | + |
| 28 | + // helper linked list data type |
| 29 | + private class Node{ |
| 30 | + private Key key; |
| 31 | + private Value val; |
| 32 | + private Node next; |
| 33 | + |
| 34 | + public Node(Key key, Value val, Node next) { |
| 35 | + this.key = key; |
| 36 | + this.val = val; |
| 37 | + this.next = next; |
| 38 | + } |
| 39 | + } |
| 40 | + |
| 41 | + // Initializes an empty symbol table |
| 42 | + public SequentialSearchST() { |
| 43 | + // |
| 44 | + } |
| 45 | + |
| 46 | + // Returns the number of key-value pairs in this symbol table. |
| 47 | + public int size() { |
| 48 | + return n; |
| 49 | + } |
| 50 | + |
| 51 | + // Returns true if this symbol table is empty. |
| 52 | + public boolean isEmpty() { |
| 53 | + return size() == 0; |
| 54 | + } |
| 55 | + |
| 56 | + // Returns true if this symbol table contains the specified key. |
| 57 | + public boolean contains(Key key) { |
| 58 | + if(key == null) |
| 59 | + throw new IllegalArgumentException("argument to contains() is null"); |
| 60 | + return get(key) != null; |
| 61 | + } |
| 62 | + |
| 63 | + // Returns the value associated with the given key in this symbol table. |
| 64 | + public Value get(Key key) { |
| 65 | + if(key == null) |
| 66 | + throw new IllegalArgumentException("argument to get() is null"); |
| 67 | + for(Node x = first; x != null; x = x.next) { |
| 68 | + if(key.equals(x.key)) |
| 69 | + return x.val; |
| 70 | + } |
| 71 | + |
| 72 | + return null; |
| 73 | + } |
| 74 | + |
| 75 | + // Inserts the specified key-value pairs into the symbol table, overwriting |
| 76 | + // the old value with the new value if the symbol table already contains the |
| 77 | + // specified key. Deletes the specified key(and its associated value) from this |
| 78 | + // symbol table if the specified value is `null` |
| 79 | + public void put(Key key, Value val) { |
| 80 | + if(key == null) |
| 81 | + throw new IllegalArgumentException("first argument to put() is null"); |
| 82 | + if(val == null) { |
| 83 | + delete(key); |
| 84 | + return; |
| 85 | + } |
| 86 | + |
| 87 | + for(Node x = first; x != null; x = x.next) { |
| 88 | + if(key.equals(x.key)) { |
| 89 | + x.val = val; |
| 90 | + return; |
| 91 | + } |
| 92 | + } |
| 93 | + first = new Node(key, val, first); |
| 94 | + n++; |
| 95 | + } |
| 96 | + |
| 97 | + // Removes the specified key and its associated value from this symbol table(if |
| 98 | + // the key is in this symbol table). |
| 99 | + public void delete(Key key) { |
| 100 | + if(key == null) |
| 101 | + throw new IllegalArgumentException("argument to delete() is null"); |
| 102 | + first = delete(first, key); |
| 103 | + } |
| 104 | + |
| 105 | + // delete key in linked list beginning at Node x |
| 106 | + // warning: function call stack too large if table is large |
| 107 | + private Noed delete(Node x, Key key) { |
| 108 | + if(x == null) |
| 109 | + return null; |
| 110 | + if(key.equals(x.key)) { |
| 111 | + n--; |
| 112 | + return x.next; |
| 113 | + } |
| 114 | + x.next = delete(x.next, key); |
| 115 | + return x; |
| 116 | + } |
| 117 | + |
| 118 | + // Returns all keys in the symbol table as an `Iterable`. |
| 119 | + // To iterate over all of the keys in the symbol table named `st` |
| 120 | + // use the foreach notation: `for(Key key: st.keys())`. |
| 121 | + public Iterable<Key> keys() { |
| 122 | + Queue<Key> queue = new Queue<Key>(); |
| 123 | + for(Node x = first; x != null; x = x.next) |
| 124 | + queue.enqueue(x.key); |
| 125 | + return queue; |
| 126 | + } |
| 127 | + |
| 128 | + // test |
| 129 | + public static void main(String[] args) { |
| 130 | + SequentialSearchST<String, Integer> st = new SequentialSearchST<String, Integer>(); |
| 131 | + for(int i = 0; !StdIn.isEmpty(); i++) { |
| 132 | + String key = StdIn.readString(); |
| 133 | + st.put(key, i); |
| 134 | + } |
| 135 | + |
| 136 | + for(String s : st.keys()) { |
| 137 | + StdOut.println(s + " " + st.get(s)); |
| 138 | + } |
| 139 | + } |
| 140 | +} |
0 commit comments