Using java:

Modify the 3 methods, put, get, and delete in RSequentialSearchST.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. All of these functions must use recursion. This means each one will need a private helper function that takes a node (the front of the list) as an additional argument. Your code cannot contain any loops except in the keys() method and the checkInvariant() method which you are not changing. You also may not use the keys() method in your code. 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.

import java.util.LinkedList;

public class RSequentialSearchST, 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 RSequentialSearchST() {

}

/**

* 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. Also, solve this using recursion. To do this, you will need to

// add a recursive helper function that takes the front of a list (Node) as an argument

// and returns the correct value.

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! Also, solve this using recursion.

// To do this, you will need to add a recursive helper function that takes the front of a

// list (Node) as an argument and returns the front of the modified list (Node).

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.

// As this code already uses recursion, the private helper function is

// already present below, but it will need to be changed to terminate

// early when appropriate.

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

// Modify this to terminate early when possible.

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;

}

}