ArrayList Internal Working

An ArrayList looks like it grows forever, but inside it is just an ordinary array. When that array is full, ArrayList creates a bigger array and copies all the elements into it. Understanding this explains why get is fast, why adding at the end is usually fast, and why inserting at the front is slow. In this lesson, you will learn how ArrayList stores elements, how its capacity grows, and how much each operation costs.

The Internal Array

An ArrayList keeps two things:

• elementData: an Object[] array that holds the elements.
• size: how many slots of that array are actually used.

The length of elementData is called the capacity. It is always at least as large as the size; the extra slots are free space for future elements.

How the Capacity Grows

The JDK's ArrayList follows these rules:

1. new ArrayList<>() starts with an empty array (capacity 0), so unused lists cost almost nothing.
2. The first add allocates a capacity of 10.
3. When the array is full, the new capacity is old capacity + old capacity / 2, that is, about 1.5 times bigger.
4. All existing elements are copied into the new array with Arrays.copyOf, and the old array is discarded.

We can watch the capacity by reading the private field with reflection. Java blocks this by default, so the program must be run with an extra option:

import java.lang.reflect.Field;
import java.util.ArrayList;
 
public class Capacity {
    static int capacity(ArrayList<?> list) throws Exception {
        Field f = ArrayList.class.getDeclaredField("elementData");
        f.setAccessible(true);
        return ((Object[]) f.get(list)).length;
    }
 
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();
        System.out.println("empty: capacity " + capacity(list));
        int last = -1;
        for (int i = 1; i <= 50; i++) {
            list.add(i);
            int cap = capacity(list);
            if (cap != last) {
                System.out.println("size " + list.size() + ": capacity " + cap);
                last = cap;
            }
        }
    }
}

javac Capacity.java
java --add-opens java.base/java.util=ALL-UNNAMED Capacity

empty: capacity 0
size 1: capacity 10
size 11: capacity 15
size 16: capacity 22
size 23: capacity 33
size 34: capacity 49
size 50: capacity 73

Explanation: The capacity jumps only when the array is full: at the 1st, 11th, 16th, 23rd, 34th and 50th elements. Between those moments, add just places the element in a free slot. The --add-opens option allows reflection into java.util; without it, Java throws InaccessibleObjectException. This is only for learning, never for real code.

Cost of Each Operation

"O(1)" means the time doesn't depend on the list size; "O(n)" means it grows with the number of elements. The algorithms lessons later in the course explain this notation.

Common Mistakes

Inserting at the front of a large ArrayList in a loop. Each insert shifts everything; build the list in order, or use an ArrayDeque.

Thinking new ArrayList<>(100) creates 100 elements. It creates an empty list with room for 100; size() is 0.

Calling get(i) beyond size() because the capacity is larger. Only indexes below size() are valid.

Interview Corner

Practice

1. Easy: Using the growth rule, work out the capacity after adding 100 elements to new ArrayList<>(), then check it with the Capacity program.
2. Harder: Time adding 100,000 elements at the end of an ArrayList, then time adding them at index 0. Explain the difference.

Key Takeaways