How Java ArrayList Works Internally: Resizing, Growth Factor, and Memory

The 1.5x growth formula, what System.arraycopy does, how memory can linger, and why appends are amortized O(1).

Before you start: this article assumes you can read a simple Java class. It briefly explains arrays (and counting positions from 0), references, generics and casting, exceptions, the binary shift, and Big-O as they come up.

A list is an ordered collection that grows as you add items, like a shopping list you keep adding to. An array is a fixed-size row of numbered slots, and Java’s ArrayList is a list built on top of one: you call add() to append an item and get(i) to read the item at position i. The reason to want a list is that you often don’t know in advance how many items you will have, and a plain array can’t grow. Behind the scenes, an ArrayList swaps in a bigger array when it runs out of room. “Pre-sizing” means telling it up front how many slots to reserve.

The usual advice is to pre-size your lists. Before building one, I measured what that advice buys.

The test adds 500,000 references to a list, once with new ArrayList<>() and once with new ArrayList<>(500_000). Setup: OpenJDK 25.0.2, a 512 MB heap, an Intel Core i9-9880H, 200 warm-up rounds, then the median of 301 runs:

default   median 3.95 ms   p90 5.35 ms
presized  median 4.04 ms   p90 4.81 ms

A few terms from that setup. The heap is the memory area where Java objects live. Warm-up rounds run the code first so Java’s optimizer has settled before timing starts. The median is the middle result when all the runs are sorted from fastest to slowest. The p90 is the value that 90 percent of the runs were at or below, so it shows the slower runs.

Same speed. The presized list came out a hair slower, which is within the run-to-run noise. In time, the resizing costs almost nothing. Time here means how long the loop took to run. The next measurement looks at memory instead.

It costs memory. I measured allocated bytes for the same two loops:

default   6.48 MB
presized  2.00 MB

That’s 3.2 times the allocation for an identical list. Every array except the last one is dead the moment its contents are copied, and the garbage collector has to reclaim it. The garbage collector is the part of Java that automatically frees memory held by objects nothing refers to any more. I measured allocated bytes here, not GC time, so I can’t tell you what that costs in your service.

The rest of this article builds the thing that produces those numbers.

The problem a plain array has

Think of an array as a row of numbered lockers (0, 1, 2, …). You choose how many when you buy the row, and you can’t bolt more on later.

Create an array of 10 and add an 11th element, and Java throws ArrayIndexOutOfBoundsException. Throwing an exception means Java stops the program with an error message unless the code handles it. The length is locked at creation.

You could allocate a million slots up front and never worry. With compressed references that’s about 4 MB per list, whether it holds a million elements or three. A reference is a slot’s pointer to an object, and compressed references let the JVM (the program that runs Java code) store each one in 4 bytes instead of 8.

ArrayList is the compromise: a normal array inside, replaced by a bigger one when it fills. Replacing means making a brand-new, larger array, copying every item from the old one into it, and using the new one from then on. The old array is abandoned.

What’s inside

Think of a row of numbered mailboxes with a sticky note saying how many have mail. The row is the array and the note is the count. Two fields do all the work:

Object[] elementData holds the elements. Object[] is an array whose slots can each hold a reference, meaning a pointer to an object that lives elsewhere in memory, to any kind of Java object.
int size counts how many you’ve added.

In the picture below, null means “this slot points at nothing”. Capacity is the number of slots in the array. Size is how many of them hold real items.

After adding "A" and "B" to a list with capacity 4:

elementData:  [ "A" | "B" | null | null ]
size:         2
capacity:     4   (elementData.length)

size is what the caller sees. elementData.length is how much room exists before the next resize. They are different numbers, and the code below keeps them apart.

Growing the array

Picture moving house when your boxes no longer fit in the van: you hire a bigger van, move everything across, and give the old one back. The list does the same with arrays.

When size == elementData.length the buffer (the internal array) is full, and the next add() does three things: allocate a bigger array, copy the old elements across with System.arraycopy(), and point elementData at the new one. System.arraycopy() is a built-in Java method that copies a range of slots from one array to another, or within the same array, in one call.

BEFORE (full, capacity 4):
[ 10 | 20 | 30 | 40 ]

AFTER (capacity 6 = 4 + 4/2), then 50 goes in the first free slot:
[ 10 | 20 | 30 | 40 | 50 | null ]

The JDK grows by 1.5 times:

$\text{newCapacity} = \text{oldCapacity} + (\text{oldCapacity} \gg 1)$

Computers store whole numbers in binary (base 2). Shifting right by one bit moves every binary digit one place to the right, which halves the number without a division and drops any remainder. For example, 10 >> 1 is 5 (binary 1010 becomes 101), and 5 >> 1 is 2. So with an old capacity of 10, the new capacity is 10 + 5 = 15.

A bigger factor means fewer copies but more empty slots after each jump. At 1.5, a list that has just resized is about a third empty, and that is the worst case. For example, a full list of 1,000 slots grows to 1,500. Once the 1,001st item is in, 499 slots are empty, and 499 of 1,500 is about a third.

One difference from the real class: new ArrayList<>() doesn’t allocate 10 slots. In the OpenJDK source it starts with a shared empty array and only grows to 10 on the first add(). The version below allocates 10 eagerly because that’s easier to read.

The implementation

A few pieces of Java syntax show up below. MyArrayList<T> uses <T> as a placeholder for the element type, so MyArrayList<String> holds strings and MyArrayList<Integer> holds integers. private means only code inside this class can touch a field, and static final makes a constant shared by the whole class. this refers to the object being built or used. The array stores plain Objects, so (T) is a cast that tells the compiler to treat a value as type T, and @SuppressWarnings("unchecked") silences the compiler’s warning that it cannot verify that cast. Arrays.copyOf(a, n) returns a new array of length n holding a’s items, padded with null if n is larger. An index is an item’s position number, starting at 0.

import java.util.Arrays;

public class MyArrayList<T> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;
    private int size;

    public MyArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }

    public MyArrayList(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Capacity cannot be negative: " + initialCapacity);
        }
        this.elementData = new Object[initialCapacity];
        this.size = 0;
    }

    public void add(T element) {
        ensureCapacity(size + 1);
        elementData[size++] = element;
    }

    @SuppressWarnings("unchecked")
    public T get(int index) {
        checkBounds(index);
        return (T) elementData[index];
    }

    @SuppressWarnings("unchecked")
    public T remove(int index) {
        checkBounds(index);
        T oldValue = (T) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }

        elementData[--size] = null; // clear the vacated slot
        return oldValue;
    }

    public int size() {
        return size;
    }

    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length) {
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x growth
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

    private void checkBounds(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
}

Walking through it

Start with list.add("A") on a new list. ensureCapacity(1) sees that 1 is not more than the 10 slots, so it does nothing. Then elementData[size++] = element stores “A” in slot 0 and bumps size from 0 to 1. The ++ after size means “use the current value as the index, then add 1”, so storing the element and updating the count happen in one line.

Now suppose the list holds 10 items and you add an 11th. ensureCapacity(11) finds that 11 is more than 10, so newCapacity becomes 10 + (10 >> 1) = 15. Arrays.copyOf builds a new 15-slot array holding the old 10 items, with null in the rest, and elementData now points at it. The old array has nothing pointing at it any more. Then the 11th item goes into slot 10.

Now remove(1) on [A, B, C, D], where size is 4. checkBounds(1) passes because 1 is at least 0 and less than 4. oldValue is “B”. Then numMoved = 4 - 1 - 1 = 2, the two items after the gap:

before:  [ A | B | C | D ]
copy C, D one slot left (from index 2 into index 1):
after:   [ A | C | D | D ]
then --size makes size 3 and nulls slot 3:
final:   [ A | C | D | null ]

If you ask for get(3) now, checkBounds throws IndexOutOfBoundsException, because 3 is not less than size.

The line that stops a leak

Imagine you take a book off a library shelf but leave its card in the catalogue. The library still believes the book is in use, so it never clears the space. A leftover slot in the array does the same thing to the garbage collector.

Look at the last statement in remove():

elementData[--size] = null;

Here --size subtracts 1 from size first and uses the new value as the index. After removing “B” from [A, B, C, D] and shifting, the array is [A, C, D, D] and size is 4. The statement makes size 3 and sets slot 3 (the stale second “D”) to null, giving [A, C, D, null].

Drop the = null and keep only the --size, and the array still holds a reference to the removed object. No public method can reach it. The garbage collector can’t know that; it sees a live reference and keeps the object alive. Objects kept alive this way are called loitering objects.

Why `add()` is still O(1)

Big-O notation describes how the work grows as the number of items grows. $O(1)$ means the work stays about the same however many items there are. $O(N)$ means it grows in proportion to $N$ , the number of items. Think of paying a small bill every day versus a huge bill once a year: the yearly bill is big, but spread over 365 days it is a small daily cost.

One resize copies the whole array, which is $O(N)$ . So how can add() be constant time?

Because resizes get rarer as the list grows. I simulated the JDK’s growth rule from 10 slots up to 500,000 elements and counted: 27 resizes, 1,080,430 element copies in total. That’s 2.16 copies per insert, spread over half a million inserts.

It’s no accident that the number sits near 2. Each resize copies the old size, and with a 1.5 factor those old sizes form a geometric series:

$\frac{N}{1.5} + \frac{N}{1.5^2} + \frac{N}{1.5^3} + \dots \approx 2N$

Each term is the previous one divided by 1.5, so the terms shrink quickly. A series like that adds up to its first term divided by $(1 - 1/1.5)$ . The first term is $N/1.5$ and $1 - 1/1.5$ is $1/3$ , so the total is $(N/1.5) \div (1/3) = 2N$ . For example, with $N = 600$ the copies are 400, then 267, then 178, and so on, and the running total creeps toward 1,200.

Total copying is bounded by about $2N$ for $N$ inserts. The cost per insert is a constant, which is what amortized $O(1)$ means. Amortized means averaged over a long run of operations: a few add() calls are expensive, but the average cost per call stays constant. Individual calls can still be slow; the average can’t.

What I’d do with this

If you know the final size, pre-size. In my benchmark it didn’t speed up the loop, but it cut allocation from 6.48 MB to 2.00 MB. If you don’t know the size, leave it alone; the growth rule handles it.

And if you write your own list, put the null in remove().

Quick summary

A size field and a flat array make a list. Everything else is bookkeeping.
Full means resize by 1.5 times with Arrays.copyOf(). 27 resizes take it from 10 slots to 500,000 elements.
Resizing barely moved the timing; it tripled the memory allocated.
remove() shifts elements left, then nulls the last slot so nothing loiters.