Search and Removal

The questions on this page are about a DynamicArray class: a collection of int values over a fixed-size backing array, with the elements in slots 0 through size - 1. Assume the constructor, size, add, get, and grow are already written:

public class DynamicArray {
  private int[] arr;   // the backing fixed-size storage
  private int size;    // how many elements have been added

  // constructor, size(), add(value), get(index), grow() already written
}

Solution

public int indexOf(int value) {
  for (int i = 0; i < size; i++) {
    if (arr[i] == value) {
      return i;
    }
  }
  return -1;
}

-1 is not a valid index, so it cannot be confused with a real answer.

Solution

public boolean contains(int value) {
  return indexOf(value) != -1;
}

The search lives in exactly one place. If the search ever changes, we change indexOf and every caller gets the improvement; there is no duplicated loop to keep in sync.

Solution

public boolean remove(int value) {
  int i = indexOf(value);
  if (i == -1) {
    return false;
  }
  for (int j = i; j < size - 1; j++) {
    arr[j] = arr[j + 1];
  }
  size--;
  arr[size] = 0;
  return true;
}

The cost is proportional to the number of elements no matter where the value is: the search does more work the further right the value is, the shift does more work the further left it is, and together they touch about size slots.

Exercise

Here is another way to write remove.

public boolean remove(int value) {
  int i = indexOf(value);
  if (i == -1) {
    return false;
  }
  arr[i] = arr[size - 1];
  size--;
  arr[size] = 0;
  return true;
}

Compare this version to the shifting remove you wrote above. Both delete the value. How do their results differ, and what decides which one is correct for a given data structure? Which is correct for our DynamicArray?

Solution

The shifting version keeps the remaining elements in their original order. This version moves the last element into the gap, which changes the order: removing 20 from [10, 20, 30, 40] leaves [10, 40, 30] instead of [10, 30, 40]. The structure’s contract decides. If it promises that elements stay in the order they were added, only the shifting version is correct. If it says nothing about order, this version is the right choice, because it removes in one move regardless of where the value is. Our DynamicArray promises order, so the shifting version is the correct one.