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. Its contract promises that elements stay in the order they were added. 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 a cheaper removal that avoids shifting: move the last element into the gap.

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;
}

Is this version correct for our DynamicArray? For what kind of structure would it be the right choice?

Solution

No. Our contract promises that elements stay in the order they were added, and moving the last element into the gap breaks that order: removing 20 from [10, 20, 30, 40] leaves [10, 40, 30] instead of [10, 30, 40]. It is the right choice for a structure whose contract says nothing about order, because it removes in one move regardless of where the value is.