public class SequentialSearchST<Key,Value> extends Object
SequentialSearchST
class represents an (unordered)
symbol table of generic key-value pairs.
It supports the usual put, get, contains,
delete, size, and is-empty methods.
It also provides a keys method for iterating over all of the keys.
A symbol table implements the associative array abstraction:
when associating a value with a key that is already in the symbol table,
the convention is to replace the old value with the new value.
The class also uses the convention that values cannot be null
. Setting the
value associated with a key to null
is equivalent to deleting the key
from the symbol table.
It relies on the equals()
method to test whether two keys
are equal. It does not call either the compareTo()
or
hashCode()
method.
This implementation uses a singly linked list and sequential search. The put and delete operations take Θ(n). The get and contains operations takes Θ(n) time in the worst case. The size, and is-empty operations take Θ(1) time. Construction takes Θ(1) time.
For additional documentation, see Section 3.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
SequentialSearchST()
Initializes an empty symbol table.
|
Modifier and Type | Method and Description |
---|---|
boolean |
contains(Key key)
Returns true if this symbol table contains the specified key.
|
void |
delete(Key key)
Removes the specified key and its associated value from this symbol table
(if the key is in this symbol table).
|
Value |
get(Key key)
Returns the value associated with the given key in this symbol table.
|
boolean |
isEmpty()
Returns true if this symbol table is empty.
|
Iterable<Key> |
keys()
Returns all keys in the symbol table as an
Iterable . |
static void |
main(String[] args)
Unit tests the
SequentialSearchST data type. |
void |
put(Key key,
Value val)
Inserts the specified key-value pair into the symbol table, overwriting the old
value with the new value if the symbol table already contains the specified key.
|
int |
size()
Returns the number of key-value pairs in this symbol table.
|
public SequentialSearchST()
public int size()
public boolean isEmpty()
true
if this symbol table is empty;
false
otherwisepublic boolean contains(Key key)
key
- the keytrue
if this symbol table contains key
;
false
otherwiseIllegalArgumentException
- if key
is null
public Value get(Key key)
key
- the keynull
if the key is not in the symbol tableIllegalArgumentException
- if key
is null
public void put(Key key, Value val)
null
.key
- the keyval
- the valueIllegalArgumentException
- if key
is null
public void delete(Key key)
key
- the keyIllegalArgumentException
- if key
is null
public Iterable<Key> keys()
Iterable
.
To iterate over all of the keys in the symbol table named st
,
use the foreach notation: for (Key key : st.keys())
.public static void main(String[] args)
SequentialSearchST
data type.args
- the command-line arguments