Tracing the LinkedSet

Let’s trace a sequence of operations and see how head, the nodes, and size change.

We start with new LinkedSet<>(). The set is empty, so head is null and size is 0.

          (empty set — head is null, size is 0)

add(4) finds nothing to match, so it links a new node at the head and returns true. The size is now 1.

          ┌───┐
head ───▶ │ 4 │ ──▶ null
          └───┘

add(9) also inserts at the head, so 9 goes in front of 4. New elements always go to the front, so the linked list runs newest to oldest. The set does not guarantee that order, and nothing relies on it. The size is 2.

          ┌───┐     ┌───┐
head ───▶ │ 9 │ ──▶ │ 4 │ ──▶ null
          └───┘     └───┘

add(6) also inserts at the head. The size is 3.

          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 6 │ ──▶ │ 9 │ ──▶ │ 4 │ ──▶ null
          └───┘     └───┘     └───┘

The next call is add(9). Its duplicate check traverses the linked list and finds the 9, so add changes nothing and returns false. The size stays 3. The set guarantees no duplicates, so a second 9 cannot be added.

contains(4) visits 6, then 9, then 4, finds a match, and returns true, leaving the set unchanged.

remove(6) finds its target at the first node. The first node has no predecessor, so remove advances head to the node holding 9. The size is 2.

          ┌───┐     ┌───┐
head ───▶ │ 9 │ ──▶ │ 4 │ ──▶ null
          └───┘     └───┘

remove(4) finds its target at the last node. The traversal has kept prev pointing at the node holding 9, so it unlinks the node holding 4 by setting the next of the node holding 9 to null. The size is 1.

          ┌───┐
head ───▶ │ 9 │ ──▶ null
          └───┘

Finally, remove(7) traverses the whole linked list without a match, returns false, and changes nothing.