The LinkedMap Class

Here is the class, with its Node class, fields, and constructor:

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;  // the map starts empty
    size = 0;
  }

  // ... the operations will go here
}

As in LinkedSet, every operation that adds or removes a node updates size, so size() returns the field:

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