****Modify the 3 methods, put, get, and delete in SequentialSearchST.java so that the list is maintained in increasing order of the keys. When implementing get and delete, make sure to take advantage of the fact that the list is in order to avoid looking at all the items in the list. None of the functions should use recursion. You also may not use the keys() method. Note: You are modifying the implementation of the methods, but not their interface. To the external world, the methods should behave exactly as before. Make sure you code takes advantage of the sorted order. We will be checking for this and you will receive no credit for a method that blindly checks the entire list when it isnt necessary.****

import java.util.LinkedList;

public class SequentialSearchST, Value> { private int n; // number of key-value pairs private Node first; // the linked list of key-value pairs

// a helper linked list data type private class Node { private Key key; private Value val; private Node next;

public Node(Key key, Value val, Node next) { this.key = key; this.val = val; this.next = next; } }

/** * Initializes an empty symbol table. */ public SequentialSearchST() { }

/** * Returns the number of key-value pairs in this symbol table. * * @return the number of key-value pairs in this symbol table */ public int size() { return n; }

/** * Returns true if this symbol table is empty. * * @return {@code true} if this symbol table is empty; * {@code false} otherwise */ public boolean isEmpty() { return size() == 0; }

/** * Returns true if this symbol table contains the specified key. * * @param key the key * @return {@code true} if this symbol table contains {@code key}; * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */ public boolean contains(Key key) { if (key == null) throw new IllegalArgumentException("argument to contains() is null"); return get(key) != null; }

/** * Returns all keys in the symbol table as an {@code Iterable}. * To iterate over all of the keys in the symbol table named {@code st}, * use the foreach notation: {@code for (Key key : st.keys())}. * * NOTE: Java's LinkedList was use in place of the book's Queue class. * * @return all keys in the symbol table */ public Iterable keys() { LinkedList queue = new LinkedList(); for (Node x = first; x != null; x = x.next) queue.add(x.key); return queue; }

/** * Returns the value associated with the given key in this symbol table. * Takes advantage of the fact that the keys appear in increasing order to terminate * early when possible. * * @param key the key * @return the value associated with the given key if the key is in the symbol table * and {@code null} if the key is not in the symbol table * @throws IllegalArgumentException if {@code key} is {@code null} */ public Value get(Key key) { // TODO // Change this code to make use of the fact the list is sorted to terminate early // when possible. if (key == null) throw new IllegalArgumentException("argument to get() is null"); for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) return x.val; } return null; }

/** * Inserts the specified key-value pair into the symbol table while maintaining the * ordering of keys. Overwrites 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 {@code null}. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */ public void put(Key key, Value val) { // TODO // Change this code to make sure the list remains sorted! if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { delete(key); return; }

for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) { x.val = val; return; } } first = new Node(key, val, first); n++; }

/** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). Takes advantage of the fact that the * keys appear in increasing order to terminate` early when possible. * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */ public void delete(Key key) { // TODO // Change this code to make use of the fact that the list is sorted to // terminate early when possible. // Also use a loop instead of recursion! So remove the recursive helper // function below. if (key == null) throw new IllegalArgumentException("argument to delete() is null"); first = delete(first, key); }

// delete key in linked list beginning at Node x // warning: function call stack too large if table is large private Node delete(Node x, Key key) { // TODO // Remove this function. Delete should no longer be recursive. if (x == null) return null; if (key.equals(x.key)) { n--; return x.next; } x.next = delete(x.next, key); return x; } public boolean checkInvariant() { if (first == null) return true; Node current = first; Node next = first.next; while (next != null) { if (current.key.compareTo(next.key) > 0) return false; current = next; next = current.next; } return true; }

}