Growing the Array

grow is the resize operation from earlier, moved inside the class. The resize operation expected a newSize argument. Here, we make the new capacity always double the old one. That seems like an arbitrary decision but it is not. You will have to wait until the chapter on Complexity Analysis to learn the reason behind it.

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

Note that we copy only the first size elements, since the slots past size hold nothing we need. Moreover, look at the last line. arr = bigger points the field at the new array. From that line on, arr means the bigger array everywhere in the class.

What happens to the old array?

At the point where arr = bigger is executed, the old array is still in memory, but it is no longer accessible through the arr variable. In fact, there is no variable that refers to it anymore.

In Java, an array or object that no variable points to becomes eligible for garbage collection, and the runtime reclaims its memory at some later point. I assume you have met this idea before. For a quick overview, see my blog post on Garbage Collection in Java.

In some programming languages, like C or C++, you might need to manually free memory, but in Java, the garbage collector handles this for you.

Note that grow is private. The client never asks for more capacity, because the client does not know capacity exists.

Let’s walk through what happens when we add(18) to a full array. Suppose the backing array already holds four elements and has no room left.

┌────┬────┬────┬────┐
│ 10 │ 25 │  7 │ 42 │
└────┴────┴────┴────┘

The array is full, so grow() allocates a bigger array (twice the capacity) and copies the existing elements over into it:

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

Now that there is room, 18 is written into the next open slot:

┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 10 │ 25 │  7 │ 42 │ 18 │  _ │  _ │  _ │
└────┴────┴────┴────┴────┴────┴────┴────┘
Solution

Both implementations are correct. The alternative grows the array eagerly, as soon as the last slot is filled, while the earlier implementation grows it lazily, only when the next add has no slot to write into.

Suppose the array is full but we never add another element. The lazily growing implementation does not allocate a new array. The eagerly growing implementation already allocated one, and that allocation is wasted.

The cost of add

Most of the time, add does one write and one increment. This time it allocated a new array and copied all four elements before writing the new one. If the array had held a million elements, it would have copied a million elements.

So the same operation, add, sometimes does a tiny amount of work and sometimes does a lot of work. From the client’s side the two calls look identical. numbers.add(18) is what you write either way, and nothing in the interface tells you which one you are getting.

After the grow, the capacity is twice the size, so half the slots are free. That is four free slots here, which means four more cheap adds before we have to grow again. The larger the array gets, the more free slots a doubling gives us. So the expensive adds get further apart.

Doubling also costs us space. Right after a grow, half the backing array is empty, so we can be holding roughly twice the memory we are actually using. We accept some wasted space. In exchange, most adds are just a write and an increment.

Is “further apart” far enough apart that the copying stops mattering? To answer that we need a way to measure cost, and we do not have one yet. The chapter on complexity comes back to this. It works out what a whole sequence of adds costs, and it shows why doubling is the right choice rather than, say, adding one slot at a time.