ArrayList — Building a Growable Array

ArrayList is an array, a size, and a rule for what to do when the array fills up. That is the whole class. Writing it is the shortest route to understanding why add is O(1) when the resize inside it is obviously O(n).

The two fields

    private Object[] items;
    private int size;

Capacity is not size. items.length is how many elements there is room for; size is how many there actually are. The slots between them exist and are null. Every bug in a hand-written list comes from confusing the two.

Appending

    /** Amortised O(1). The resize is O(n) but happens on a vanishing fraction of calls. */
    public void add(E item) {
        if (size == items.length) {
            grow();
        }
        items[size++] = item;
    }

    private void grow() {
        // Doubling is the whole trick. See the class comment.
        items = Arrays.copyOf(items, items.length * 2);
    }

Why doubling makes it O(1)

This is the part worth being able to derive rather than recite.

Start with capacity 1 and add n elements. Copies happen at capacity 1, 2, 4, 8, … and each copies that many elements. The total copying work is:

1 + 2 + 4 + 8 + ... + n/2 + n  =  2n - 1

That is the geometric series, and it sums to less than 2n — linear in total, not quadratic. Spread over n adds, that is under 2 copies per add: a constant. Hence amortised O(1).

Now grow by one instead. Every add copies everything, so the total is 1 + 2 + 3 + … + n = n(n+1)/2, which is O(n²). Same class, same interface, and building a million-element list goes from instant to hours.

The growth schedule is asserted, not assumed:

        DynamicArray<String> list = new DynamicArray<>(2);
        list.add("a");
        list.add("b");
        Check.eq(list.capacity(), 2, "capacity before growth");
        list.add("c");
        Check.eq(list.capacity(), 4, "capacity doubles, not +1");

And at the other end of the scale — ten doublings from 1 gets you to 1024:

        DynamicArray<Integer> counted = new DynamicArray<>(1);
        for (int i = 0; i < 1024; i++) {
            counted.add(i);
        }
        Check.eq(counted.capacity(), 1024, "1 doubled ten times");

The JDK's own ArrayList grows by 50%, not 100% — the series still converges, so it is still amortised O(1), and it wastes less memory on large lists.

Insert and remove in the middle

    /** O(n) - every element from index onwards shifts up one slot. */
    public void add(int index, E item) {
        checkIndexForAdd(index);
        if (size == items.length) {
            grow();
        }
        System.arraycopy(items, index, items, index + 1, size - index);
        items[index] = item;
        size++;
    }

Removal is the mirror image, and contains the one line people leave out:

    /** O(n) for the same reason as insert: the tail closes the gap. */
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        checkIndex(index);
        E removed = (E) items[index];
        System.arraycopy(items, index + 1, items, index, size - index - 1);
        // Null the vacated slot. Without this the array keeps a reference to an object nobody
        // can reach any more, and it never becomes garbage - a real leak in a long-lived list.
        items[--size] = null;
        return removed;
    }

That = null is a real memory leak if omitted. After the shift, the last slot still holds a reference to an object the list no longer contains. It is past size, so no caller can ever see it — and it is reachable from the array, so the collector will never free it. The list "works" perfectly while quietly pinning objects. The JDK's ArrayList.remove has the identical line for the identical reason.

Size against capacity, in practice

Two consequences worth knowing:

• Pre-size it when you know the count. new ArrayList<>(10_000) skips every intermediate copy. It changes capacity, not size — the list is still empty.
• A list never shrinks on its own. Add a million elements and remove them all and the backing array is still a million long. trimToSize() exists for that, and is almost never called.

ArrayList or LinkedList?

Use ArrayList. The theoretical O(1) front insertion is real but rarely what an application does, and it is paid for at every read and every iteration. If you truly need cheap insertion at both ends, ArrayDeque beats both.

The classic disaster is calling get(i) in a loop over a LinkedList: each call walks from the head, so the loop is O(n²) while looking exactly like the ArrayList version that is O(n).

What to remember

• Capacity is room; size is contents. They are not the same number.
• Doubling makes append amortised O(1); growing by one makes it O(n²).
• Null the vacated slot on removal, or the list leaks.
• Pre-size when you know the count; lists never shrink by themselves.
• Reach for ArrayList by default.