Tracing the Two Sets

Here is a sequence of operations on a set of integers that starts out empty:

set.add(31);
set.add(58);
set.add(46);
set.add(72);
set.add(58);
set.remove(58);
set.remove(72);
set.remove(64);
set.add(19);

add and remove return true if the call changed the set and false if it did not.

Solution

add(31) returns true. size = 1

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

add(58) returns true. size = 2

          ┌────┐     ┌────┐
head ───▶ │ 58 │ ──▶ │ 31 │ ──▶ null
          └────┘     └────┘

add(46) returns true. size = 3

          ┌────┐     ┌────┐     ┌────┐
head ───▶ │ 46 │ ──▶ │ 58 │ ──▶ │ 31 │ ──▶ null
          └────┘     └────┘     └────┘

add(72) returns true. size = 4

          ┌────┐     ┌────┐     ┌────┐     ┌────┐
head ───▶ │ 72 │ ──▶ │ 46 │ ──▶ │ 58 │ ──▶ │ 31 │ ──▶ null
          └────┘     └────┘     └────┘     └────┘

add(58) returns false. 58 is already in the set, so the list does not change.

remove(58) returns true. size = 3

          ┌────┐     ┌────┐     ┌────┐
head ───▶ │ 72 │ ──▶ │ 46 │ ──▶ │ 31 │ ──▶ null
          └────┘     └────┘     └────┘

remove(72) returns true. size = 2

          ┌────┐     ┌────┐
head ───▶ │ 46 │ ──▶ │ 31 │ ──▶ null
          └────┘     └────┘

remove(64) returns false. 64 is not in the set, so the list does not change.

add(19) returns true. size = 3

          ┌────┐     ┌────┐     ┌────┐
head ───▶ │ 19 │ ──▶ │ 46 │ ──▶ │ 31 │ ──▶ null
          └────┘     └────┘     └────┘

Solution

add(31) returns true. size = 1

┌────┐
│ 31 │
└────┘
   0

add(58) returns true. size = 2

┌────┬────┐
│ 31 │ 58 │
└────┴────┘
   0    1

add(46) returns true. size = 3

┌────┬────┬────┐
│ 31 │ 58 │ 46 │
└────┴────┴────┘
   0    1    2

add(72) returns true. size = 4

┌────┬────┬────┬────┐
│ 31 │ 58 │ 46 │ 72 │
└────┴────┴────┴────┘
   0    1    2    3

add(58) returns false. 58 is already in the set, so the array does not change.

remove(58) returns true. The last item, 72, moves into index 1. size = 3

┌────┬────┬────┐
│ 31 │ 72 │ 46 │
└────┴────┴────┘
   0    1    2

remove(72) returns true. The last item, 46, moves into index 1. size = 2

┌────┬────┐
│ 31 │ 46 │
└────┴────┘
   0    1

remove(64) returns false. 64 is not in the set, so the array does not change.

add(19) returns true. size = 3

┌────┬────┬────┐
│ 31 │ 46 │ 19 │
└────┴────┴────┘
   0    1    2