Dynamic Array Trace

This page traces a DynamicArray: a collection of int values over a fixed-size backing array. The elements sit in slots 0 through size - 1, in the order they are added. add appends at the end; when the backing array is full, it first doubles the capacity by allocating a new array and copying the elements over. remove(value) deletes the first occurrence and shifts the later elements left to close the gap, then clears the vacated slot to 0.

For this trace, the backing array starts with capacity 4.

Exercise

Start from a freshly constructed dynamic array and perform, in order:

a.add(12);
a.add(27);
a.add(45);
a.add(31);
a.add(58);
a.remove(27);

After each operation, show the backing array’s contents, its capacity, and size. Mark where a grow happens.

Solution

A fresh array has capacity 4 and size = 0:

┌────┬────┬────┬────┐
│  0 │  0 │  0 │  0 │   size = 0
└────┴────┴────┴────┘

Uninitialized slots contain 0 (the default value for int). The number of slots is the capacity.

add(12) writes into slot 0:

┌────┬────┬────┬────┐
│ 12 │  0 │  0 │  0 │   size = 1
└────┴────┴────┴────┘

add(27):

┌────┬────┬────┬────┐
│ 12 │ 27 │  0 │  0 │   size = 2
└────┴────┴────┴────┘

add(45):

┌────┬────┬────┬────┐
│ 12 │ 27 │ 45 │  0 │   size = 3
└────┴────┴────┴────┘

add(31) fills the last slot:

┌────┬────┬────┬────┐
│ 12 │ 27 │ 45 │ 31 │   size = 4
└────┴────┴────┴────┘

add(58) finds no free slot (size == capacity), so it grows first: a new array of capacity 8 is allocated, the 4 elements are copied over, and then 58 is written into slot 4:

┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 12 │ 27 │ 45 │ 31 │ 58 │  0 │  0 │  0 │   size = 5
└────┴────┴────┴────┴────┴────┴────┴────┘

remove(27) finds 27 at index 1, shifts 45, 31, and 58 one slot left, decrements size, and clears the vacated slot:

┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 12 │ 45 │ 31 │ 58 │  0 │  0 │  0 │  0 │   size = 4
└────┴────┴────┴────┴────┴────┴────┴────┘