Dynamic Array Operations

The questions on this page are about a DynamicArray class: a collection of int values that grows automatically as values are added. Elements stay in the order they were added. The class wraps a fixed-size backing array and a counter:

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

  public DynamicArray() { ... }        // starts empty, with a small initial storage
  public int size() { ... }            // number of elements added so far
  public void add(int value) { ... }   // appends value at the end; never runs out of room
  public int get(int index) { ... }    // returns the element at index; throws
                                       //   IndexOutOfBoundsException for an invalid index
  private void grow() { ... }          // doubles the backing array's capacity
}

Solution

arr.length is the capacity: how many slots the storage currently has. size is the logical size: how many of those slots hold real elements. The elements sit in slots 0 through size - 1; the slots from size up to arr.length - 1 are allocated but unused. The client only ever sees size; capacity is internal to the class.

Solution

public DynamicArray() {
  arr = new int[10];
  size = 0;
}

public int size() {
  return size;
}

Solution

public void add(int value) {
  if (size == arr.length) {
    grow();
  }
  arr[size] = value;
  size++;
}

private void grow() {
  int[] bigger = new int[arr.length * 2];
  for (int i = 0; i < size; i++) {
    bigger[i] = arr[i];
  }
  arr = bigger;
}

A normal add is one write and one increment, regardless of how many elements are stored. A growing add copies every element into the new array first, so its cost is proportional to the number of elements.

Solution

public int get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  return arr[index];
}

A slot at an index past size exists in the backing array, but it is not an element of the collection. It is unused space. Checking against arr.length would let the client read those slots as if they held real elements.

Solution

size() now reports 100 elements that were never added. get(50) throws an out-of-bounds exception (slot 50 does not exist), and the next add tries to write to arr[100] and throws the same exception. The invariant is 0 <= size <= arr.length, with the real elements sitting in slots 0 through size - 1. With private fields, the only way to change the object is through its methods, and every method keeps the invariant true.