Implementing LinkedMap

Here is the Map interface:

public interface Map<K, V> {
  boolean put(K key, V value);  // stores value under key, replacing any old value;
                                // returns true if the key was not present before
  V get(K key);                 // returns the value stored under key, or null if key is absent
  boolean remove(K key);        // removes key and its value if key is present;
                                // returns true if the map changed
  boolean containsKey(K key);   // returns true if key is in the map
  int size();                   // returns the number of key-value pairs in the map
}

Every method that takes a key throws an IllegalArgumentException if the key is null. put also throws it if the value is null.

LinkedMap<K, V> implements the Map<K, V> interface with a singly linked list, one node per pair:

public class LinkedMap<K, V> implements Map<K, V> {

  private Node<K, V> head;  // the first node, or null when empty
  private int size;         // how many pairs the map holds

  private static class Node<K, V> {
    K key;
    V value;
    Node<K, V> next;

    Node(K key, V value) {
      this.key = key;
      this.value = value;
    }
  }

  public LinkedMap() {
    head = null;
    size = 0;
  }

  @Override
  public int size() {
    return size;
  }

  // the other operations go here
}

Solution

@Override
public V get(K key) {
  if (key == null) {
    throw new IllegalArgumentException();
  }
  Node<K, V> curr = head;
  while (curr != null) {
    if (key.equals(curr.key)) {
      return curr.value;
    }
    curr = curr.next;
  }
  return null;
}

Solution

@Override
public boolean put(K key, V value) {
  if (key == null || value == null) {
    throw new IllegalArgumentException();
  }
  Node<K, V> curr = head;
  while (curr != null) {
    if (key.equals(curr.key)) {
      curr.value = value;
      return false;
    }
    curr = curr.next;
  }
  Node<K, V> newNode = new Node<>(key, value);
  newNode.next = head;
  head = newNode;
  size++;
  return true;
}

Solution

@Override
public boolean remove(K key) {
  if (key == null) {
    throw new IllegalArgumentException();
  }
  Node<K, V> prev = null;
  Node<K, V> curr = head;
  while (curr != null) {
    if (key.equals(curr.key)) {
      if (prev != null) {
        prev.next = curr.next;
      } else {
        head = head.next;
      }
      size--;
      return true;
    }
    prev = curr;
    curr = curr.next;
  }
  return false;
}

Solution

size is $O (1)$ : it returns a field. get and containsKey are $O (n)$ : each is a linear search for the key. put is $O (n)$ : replacing a value or inserting at the head is $O (1)$ , but the search for the key comes first. remove is $O (n)$ : the unlink is $O (1)$ , but finding the node is a linear search.