edu.princeton.cs.algs4

Class SequentialSearchST<Key,Value>

Object

edu.princeton.cs.algs4.SequentialSearchST<Key,Value>

public class SequentialSearchST<Key,Value>
extends Object

The 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.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
SequentialSearchST() Initializes an empty symbol table.

Method Summary

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.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SequentialSearchST

public SequentialSearchST()

Initializes an empty symbol table.

Method Detail

size

public int size()

Returns the number of key-value pairs in this symbol table.

Returns:

the number of key-value pairs in this symbol table

isEmpty

public boolean isEmpty()

Returns true if this symbol table is empty.

Returns:

true if this symbol table is empty; false otherwise

contains

public boolean contains(Key key)

Returns true if this symbol table contains the specified key.

Parameters:

key - the key

Returns:

true if this symbol table contains key; false otherwise

Throws:

IllegalArgumentException - if key is null

get

public Value get(Key key)

Returns the value associated with the given key in this symbol table.

Parameters:

key - the key

Returns:

the value associated with the given key if the key is in the symbol table and null if the key is not in the symbol table

Throws:

IllegalArgumentException - if key is null

put

public 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. Deletes the specified key (and its associated value) from this symbol table if the specified value is null.

Parameters:

key - the key

val - the value

Throws:

IllegalArgumentException - if key is null

delete

public void delete(Key key)

Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).

Parameters:

key - the key

Throws:

IllegalArgumentException - if key is null

keys

public Iterable<Key> keys()

Returns all keys in the symbol table as an Iterable. To iterate over all of the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).

Returns:

all keys in the symbol table

main

public static void main(String[] args)

Unit tests the SequentialSearchST data type.

Parameters:

args - the command-line arguments