Adding Elements

We have the backing array and the size field. Now we need a way for the client to put values in.

After we add some elements, they occupy slots 0 through size - 1. So the next free slot is exactly at index size. To add a value, we write it at that slot and increment the size counter:

public void add(int value) {
  arr[size] = value;  // place the value in the next free slot
  size++;             // one more element now lives in the array
}

Retrieving a value is just an array access:

// Assume index is valid
public int get(int index) {
  return arr[index];
}

Let’s trace a few adds on a fresh dynamic array. The diagrams below use a backing array with room for 4 instead of 10, just so they fit on the page; the logic is identical.

A fresh array is empty, so size is 0 and the next free slot is index 0:

┌────┬────┬────┬────┐
│  _ │  _ │  _ │  _ │
└────┴────┴────┴────┘
    ↑
  size

Now add(10) places 10 in the next free slot, index 0, then increments size to 1:

┌────┬────┬────┬────┐
│ 10 │  _ │  _ │  _ │
└────┴────┴────┴────┘
        ↑
      size

add(25) writes 25 into the slot size points at, index 1, and size becomes 2:

┌────┬────┬────┬────┐
│ 10 │ 25 │  _ │  _ │
└────┴────┴────┴────┘
             ↑
           size

add(7) does the same at index 2, leaving size at 3:

┌────┬────┬────┬────┐
│ 10 │ 25 │  7 │  _ │
└────┴────┴────┴────┘
                  ↑
                size

Each add does one write and one increment. Nothing is copied and nothing is shifted, no matter how many elements are already in the array.

When the array fills up

Keep going with the trace above. One more add writes into index 3 and leaves size at 4. The backing array has exactly 4 slots, so every slot is now taken, and size points one past the end of the array.

The next add tries to write to arr[4], an index that does not exist, and Java throws an ArrayIndexOutOfBoundsException. (I assume you are familiar with Java’s Exception system. For a quick refresher, see my blog post.)

So add needs to check for this before it writes. If there is no free slot, it has to get more storage first. Call that job grow:

public void add(int value) {
  if (size == arr.length) {
    grow();           // dynamically increase the array size
  }
  arr[size] = value;  // place the value in the next free slot
  size++;             // one more element now lives in the array
}

The condition size == arr.length is the test for “no free slot left”, since the last usable index is arr.length - 1 and size is the index we are about to write to.