public class KeyValueList<Key,Value> implements SymbolTable<Key,Value>{

   private class Node {
      Key   key;
      Value val;
      Node  next;

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

   private Node first;
   private int size;
   
   public void put(Key key, Value val) {
      for (Node x = first; x != null; x = x.next) // Check if key is
         if (key.equals(x.key)) {                 // already present.
            x.val = val;                          // Update value if
            return;                               // it is
         }
      first = new Node(key,val,first);  // Inserting at beginning of list
                                        // minimizes insertion cost.
      size++;
   }

   public boolean contains(Key key) {
      return get(key) != null;
   }

   public Value get(Key key) {
      for (Node n = first; n != null; n = n.next)
         if (key.equals(n.key))
            return n.val;
      return null;
   }

   public void delete(Key key) {
      if (first == null)
         return;

      if (key.equals(first.key))
         first = null;

      for (Node n = first; n.next != null; n = n.next)
         if (key.equals(n.next.key)) {
            n.next = n.next.next;
            size--;
         }
   }

   public boolean isEmpty() {
      return (first == null);
   }

   public int size() {
      return size;
   }
   
   public Iterable<Key> keys() {
       java.util.Stack<Key> stack = new java.util.Stack<Key>();
       for (Node n = first; n != null; n = n.next) {
           stack.add(n.key);
       }
       return stack;
   }
   
   public String toString() {
       StringBuilder sb = new StringBuilder("");
       for (Node n = first; n != null; n = n.next) {
           sb.append("("+n.key+","+n.val+")");
           if (n.next != null)
               sb.append("->");
       }
       return sb.toString();
   }
}