Tracing the ArraySet

Let’s trace a sequence of operations and watch the backing array and size change. We show only the filled part of the array. The capacity is 10, so the array is never full here.

We start with new ArraySet<>(): an empty array and a size of 0.

add(4) finds no match, so it appends at index 0 and returns true. The size is 1.

  ┌───┐
  │ 4 │            size = 1
  └───┘
    0

add(9) appends at the next free slot, index 1. The size is 2. Unlike the LinkedSet, which puts new items at the front, the array keeps them in arrival order. As before, the set does not guarantee that order, and nothing relies on it.

  ┌───┬───┐
  │ 4 │ 9 │        size = 2
  └───┴───┘
    0   1

add(6) appends at index 2. The size is 3.

  ┌───┬───┬───┐
  │ 4 │ 9 │ 6 │    size = 3
  └───┴───┴───┘
    0   1   2

add(9) searches and finds 9 at index 1, so it returns false. Nothing changes.

Now remove(9). The search finds 9 at index 1. Instead of shifting 6 left to close the gap, we copy the last item, 6, into index 1 and clear index 2. The size is 2.

  ┌───┬───┐
  │ 4 │ 6 │        size = 2
  └───┴───┘
    0   1

The array’s contents are no longer in arrival order.

remove(4) finds 4 at index 0 and does the same move: the last item, 6, goes into index 0, and index 1 is cleared. The size is 1.

  ┌───┐
  │ 6 │            size = 1
  └───┘
    0

Finally, contains(6) searches and returns true. contains(7) searches to the end and returns false. Neither call changes the array.