The LinkedSet Class

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

public class LinkedSet<T> implements Set<T> {

  private Node<T> head;  // the first node, or null when empty
  private int size;      // how many items the set holds

  private static class Node<T> {
    T value;
    Node<T> next;

    Node(T value) {
      this.value = value;
    }
  }

  public LinkedSet() {
    head = null;  // the set starts empty
    size = 0;
  }

  // ... the operations will go here
}

As with LinkedList, size must always match the actual number of nodes, so every operation that adds or removes a node updates it.

That makes the size method a one-liner:

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