Removing Elements

We can add elements and find them. Let’s add a remove that, given a value, deletes it from the collection if it is there.

Removing has two parts. First we find the value, and then we close the gap its removal would leave behind.

We must close the gap to maintain the class invariant. Our whole implementation depends on the invariant that the elements sit in slots 0 through size - 1, with nothing missing in between. If we deleted the element at index i and left the slot alone, that invariant would break. size would say we have one fewer element, but the elements after index i would still be where they were. Each of them would be one slot too far right, and the last one would sit outside the range that size describes. So every element after index i has to scooch one slot to the left.

Say we call remove(20) on [10, 20, 30, 40]. The search scans left to right and finds the target:

┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘
        ↑
      found

Now we close the gap: every element after the target scooches one slot left. We copy 30 one slot left, then we copy 40 one slot left. Copying does not erase the slot we copied from, so 40 is now in two slots. The one on the right is stale:

┌────┬────┬────┬────┐
│ 10 │ 30 │ 40 │░40░│
└────┴────┴────┴────┘
                  ↑
                stale

Finally we decrement size, and that effectively frees the stale slot, as the next add will write over it.

┌────┬────┬────┬────┐
│ 10 │ 30 │ 40 │  _ │
└────┴────┴────┴────┘
                  ↑
                freed

We can even set the vacated slot back to 0. With int this is mostly tidiness, since size already hides that slot from the client, but it is a good habit (and it will matter once our elements are objects).

┌────┬────┬────┬────┐
│ 10 │ 30 │ 40 │  0 │
└────┴────┴────┴────┘
                  ↑
                back to default

Here is the implementation of the remove method:

public boolean remove(int value) {
  for (int i = 0; i < size; i++) {
    if (arr[i] == value) {
      for (int j = i; j < size - 1; j++) {
        arr[j] = arr[j + 1];   // shift the rest one slot left
      }
      size--;                  // one fewer element
      arr[size] = 0;           // clear the now-unused slot
      return true;
    }
  }
  return false;                // value wasn't found
}

A few things to notice:

• We return a boolean so the caller knows whether anything was actually removed.
• We remove only the first occurrence. If the value appears twice, the second copy stays.

The cost of remove

There are two loops here. When one of them does more work, the other does less.

The search runs from the front until it finds the value, so it does more work the further right the value sits. The shift runs from the value to the end, so it does more work the further left the value sits. Together:

• Remove the last element: the search scans the whole array, but there is nothing after it to shift.
• Remove the first element: the search stops immediately, but we shift every other element one slot left.

Either way one of the two loops touches most of the array, so remove does work proportional to the number of elements no matter where the value sits. So the best case and worst case are the same, or rather have no distinction.

Notice that remove begins by doing exactly what contains does, scanning the array for a value. That is the same search written out twice, and we will tidy that up before we go on.