Dynamic arrays

When size reaches capacity, a dynamic array allocates a bigger buffer, copies the existing elements and continues. The copy costs O(size), but it happens rarely. Try the three growth policies in the animation and watch the copy counters.

Doubling is the textbook rule; java.util.ArrayList grows by 50%.

1void add(int x) {
2    if (size == data.length) data = Arrays.copyOf(data, Math.max(1, data.length * 2));
3    data[size++] = x;
4}

1void add(int x) {
2    if (size == data.length) {                        // buffer is full
3        data = Arrays.copyOf(data, newCapacity());     // allocate bigger, copy size elements
4    }
5    data[size++] = x;
6}
7int removeLast() {
8    int x = data[--size];
9    if (size <= data.length / 4) data = Arrays.copyOf(data, Math.max(1, data.length / 2));   // optional shrink
10    return x;
11}

Geometric growth multiplies the capacity by a constant factor (2, 1.5, ...). Because the capacities form a geometric series, the total copy work for n appends is a constant multiple of n: with doubling, 1 + 2 + 4 + ... + n/2 < n. Growing by a fixed step (+10) instead makes the copies add up to about n²/20.

Pick the growth policy and compare the total copies.

1void add(int x) {
2    if (size == data.length) {                          // full: allocate a bigger array
3        data = Arrays.copyOf(data, newCapacity(data.length));   // copies `size` elements
4    }
5    data[size++] = x;                                   // the cheap part: 1 write
6}
7// doubling: newCapacity = 2 * capacity;  grow-by-1: capacity + 1;  Java ArrayList: capacity + capacity / 2

An individual append can cost O(n) when it triggers a resize, but any sequence of n appends costs O(n) in total, so the amortised cost per append is O(1). The guarantee is about the whole sequence, not about the average input.

The chart plots the cost of each append; the occasional tall bar is paid for by the many cheap ones.

1void add(int x) {
2    if (size == data.length) {                          // full: allocate a bigger array
3        data = Arrays.copyOf(data, newCapacity(data.length));   // copies `size` elements
4    }
5    data[size++] = x;                                   // the cheap part: 1 write
6}
7// doubling: newCapacity = 2 * capacity;  grow-by-1: capacity + 1;  Java ArrayList: capacity + capacity / 2

Size is how many elements the user has stored; capacity is how many the buffer can hold. Always size ≤ capacity. ArrayList.size() reports the size and there is no public capacity getter, but you can reserve with ensureCapacity and release spare room with trimToSize.

Presizing with the expected count avoids every intermediate resize.

1List<Integer> xs = new ArrayList<>(1000);   // capacity 1000, size 0
2xs.add(1);                                  // size 1
3ArrayList<Integer> big = new ArrayList<>();
4big.ensureCapacity(5000);                   // one allocation up front
5big.trimToSize();                           // capacity shrinks to size

1void add(int x) {
2    if (size == data.length) {                        // buffer is full
3        data = Arrays.copyOf(data, newCapacity());     // allocate bigger, copy size elements
4    }
5    data[size++] = x;
6}
7int removeLast() {
8    int x = data[--size];
9    if (size <= data.length / 4) data = Arrays.copyOf(data, Math.max(1, data.length / 2));   // optional shrink
10    return x;
11}

Inside, a dynamic array is just an array plus a counter. ArrayList keeps an Object[] elementData and an int size; its first add allocates capacity 10, and growth is old + (old >> 1). Elements at index size and beyond are null so the garbage collector can reclaim removed objects.

A minimal version shows every part.

1class IntList {
2    private int[] data = new int[4];
3    private int size;
4    void add(int x) {
5        if (size == data.length) data = Arrays.copyOf(data, size * 2);
6        data[size++] = x;
7    }
8    int get(int i) {
9        if (i < 0 || i >= size) throw new IndexOutOfBoundsException("index " + i + ", size " + size);
10        return data[i];
11    }
12    int size() { return size; }
13}

Shrinking releases memory after many removals. A naive rule, halve when size drops to half of capacity, can thrash: alternating add and remove at the boundary would resize every time. The standard fix is to shrink only when size falls to a quarter of capacity, halving the buffer so it ends up half full.

Use the removal field in the doubling policy to see the shrink step. ArrayList itself never shrinks automatically; call trimToSize() if memory matters.

1void add(int x) {
2    if (size == data.length) {                        // buffer is full
3        data = Arrays.copyOf(data, newCapacity());     // allocate bigger, copy size elements
4    }
5    data[size++] = x;
6}
7int removeLast() {
8    int x = data[--size];
9    if (size <= data.length / 4) data = Arrays.copyOf(data, Math.max(1, data.length / 2));   // optional shrink
10    return x;
11}

A dynamic array wastes the spare capacity: right after a doubling the buffer is only half full, so up to 50% of the slots are unused (33% for ×1.5). During a resize both the old and the new buffer exist, so peak memory is about 1.5× to 3× the final size. On top of that, ArrayList<Integer> stores references plus a boxed object per element.

For large primitive data prefer int[] with your own size counter.