The Remove Contract

Our remove shifts every later element down by one to close the gap. That shift is the expensive part of the operation. We could do this in a different way to circumvent shifting!

What we need is the invariant: elements in slots 0 through size - 1, with no gap in the middle. The shift is one way to restore that, but it is not the only way. We could take the last element and move it into the gap instead. That fills the gap. It also empties a slot at the end, and that is the slot that falls outside the range once size goes down by one.

public boolean remove(int value) {
  int i = indexOf(value);
  if (i == -1) {
    return false;
  }
  arr[i] = arr[size - 1];  // move the last element into the gap
  size--;
  arr[size] = 0;
  return true;
}

This is much cheaper. There is no shifting at all, just one move, and the cost does not depend on where the value sits in the array. So why did we not write it this way to begin with?

Two correct removals

Trace both on [10, 20, 30, 40], removing 20. Both start from the same state:

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

The shift version slides every later element down by one to close the gap:

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

The swap-with-last version moves the last element into the gap instead:

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

Both versions remove 20, and both leave a collection of the right size holding the right elements. The two differ in the order of what is left. The shift version leaves [10, 30, 40]. The swap version leaves [10, 40, 30], because it moved 40 ahead of 30.

So which one is right? It depends on a question we have never answered: does DynamicArray promise to keep elements in the order they were added?

The contract

This is the idea of a contract (or specification): the set of promises a data structure makes about how it behaves.

The contract is not visible in any single line of code. It is a decision we make about what the structure means, and then the code has to match it. If our contract says elements stay in insertion order, then the swap version is wrong. If our contract says nothing about order, then both versions are correct.

For our DynamicArray, we commit to the promise that elements stay in the order they were added. That means we keep the shifting version of remove.

The swap version is the right removal for a structure whose contract says nothing about order, because it does not incur the cost of shifting.