import java.util.ArrayList; import stdlib.StdOut;

/** * * The LinkedListST class implements methods of the Ordered Symbol table API using * an *unordered* linked-list of generic key-value pairs. * The methods: put, get, and delete are already implemented * - note that you should be able to implement them as well. * * Complete the 4 (+1 optional A-Level) methods marked ToDo * All ToDo methods must operate directly on the underlying linked list. * * */

public class LinkedListST, Value> { public static boolean ALevelCompleted = true; // ToDo5 set to true if you complete the A-level private Node first; // the linked list of key-value pairs

// nested Node class for linked list 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 LinkedListST() { first = null; }

/** * Returns the value associated with the given key in this symbol table. */ public Value get(Key key) { if (key == null) throw new NullPointerException("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, 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. */ public void put(Key key, Value val) { if (key == null) throw new NullPointerException("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); }

/** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). */ public void delete(Key key) { if (key == null) throw new NullPointerException("argument to delete() is null"); first = delete(first, key); }

// delete key in sub-list beginning at Node x // return: the sub-list with the key removed // warning: function call stack too large if table is large private Node delete(Node x, Key key) { if (x == null) return null; if (key.equals(x.key)) { return x.next; } x.next = delete(x.next, key); return x; } /** * keys returns a Java Iterable of the Keys in the Symbol-Table instance. * You may find this useful in debugging * */ public Iterable keys() { ArrayList theKeys = new ArrayList(); for ( Node temp = first; temp != null; temp=temp.next) { theKeys.add(temp.key); } return theKeys; }

/** * size * * returns the number of key-value pairs in the symbol table. * it returns 0 if the symbol table is empty. */ public int size () { int N = 0; for(Node temp = first; temp != null; temp = temp.next){ N++;// ToDo 1 fix this method } return N; //for loop to find size of symbol table } /** * ceiling * * returns the smallest key in the symbol table that is greater than or equal to the given key. * it returns null if there is no such key. */ public Key ceiling (Key key) { // ToDo 2 fix this method Node current = first; //node is initialized as first while(current != null && current.key.compareTo(key) < 0) { //if not null and current key compared to key parameter current = current.next; //key is now next node } if(first == null || current == null) { return null; //if current node is empty return null } return current.key; //returns current key; } /** * rank * * returns the number of keys in this symbol table that are less than the parameter key. * your implementation should be recursive. You will want to create a helper function */ public int rank (Key key) { if(first == null) { return 0; //if first node has nothing return null }// ToDo 3 fix this method int ranked = 0; Node current = first; while(current != null && current.key.compareTo(key) < 0) { ranked++; current = current.next; } return ranked; }

/** * secondSmallestKey * * returns the second smallest key in the symbol table. * it returns null if the symbol table is empty or if it has only one key. * See if you can write it with only one loop * * You MUST document your solution for this ToDo by adding comments that * explain how each section of your method contributes to the solution. * * comments such as in the following example: * * count++; // add 1 to count * * are basically useless * instead, explain how adding one to count is used in your solution * */ public Key secondSmallestKey () { return null; // ToDo 4 fix and document this method }

/** * A level. * * select * * Complete the instance method to determine the key of rank : theRank * * Give the worst case Order of Growth for your method for a symbol table of size N on the next line. * Include a brief explanation. * * order of growth: * explanation: */ public Key select (int theRank) { if(first == null) { return null;// ToDo 5 fix this method } // and set the aLevelCompleted variable at the top of the file to true Node current = first; while(theRank > 0) { current = current.next; if(current == null) { return null; } theRank--; } return current.key; } }

Need help on the 4 to-do's, please don't alter anything from the code above (eclipse) and only change the methods in Italics. I started 3 of them but they're wrong. Thanks