PHASE 9Intermediate ~34 min· topic 2 of 13

Topic 9.2

ArrayList Inside Out

In one line

ArrayList is a growable array: an Object[] plus a size counter. Reading by index is O(1), adding at the end is amortised O(1) because the array grows by 1.5x when full, and inserting or removing in the middle is O(n) because System.arraycopy shifts every later element.

Think of it like this

A row of numbered lockers in a school corridor. Finding locker 37 is instant: walk straight to number 37. Adding a new pupil at the end is easy while there are empty lockers. When the row is full, the school builds a new, longer row and moves every pupil's things across, which is a big job but rare. And if a new pupil must go into locker 3, everyone from locker 3 onwards has to move one locker along. That's exactly how an ArrayList behaves.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Backing array: The plain Java array hidden inside an ArrayList where the elements are really stored.
Capacity: How many elements the backing array can hold before it must grow. Not the same as size.
Size: How many elements the list actually contains right now.
Grow: Make a bigger backing array and copy the old elements into it.
System.arraycopy: A fast built-in method that copies a range of one array into another (or within the same array).
Amortised O(1): Usually constant time, with rare expensive steps whose cost, spread across all the cheap ones, still averages out to a constant.
Shift: Move a block of elements one position left or right inside the array to open or close a gap.
modCount: A counter inside the list that goes up on every structural change. Iterators use it to spot illegal changes (Topic 9.9).

Step by step

01Two fields: the array and the size

After List<String> l = new ArrayList<>(); l.add("a"); l.add("b"); the list object on the heap holds a reference to an Object[10] and size = 2. Slots 2 to 9 exist but hold null and are invisible to you: l.get(5) throws, because it checks against size, not against the array length.

The elements themselves aren't in the array: the array holds references to String objects elsewhere on the heap. Copying the array on a grow copies references (4 or 8 bytes each), never the objects.

Two fields: the array and the sizediagram

Rendering diagram…

02add at the end: the common, cheap case

add(e) increments modCount, checks whether size == elementData.length, and if there's room stores e at elementData[size] and increments size. Two field writes and an array store: O(1).

Only when the array is full does it call grow, which computes the new length and calls Arrays.copyOf(elementData, newLength).

ArrayList.java (simplified from the JDK)whole filejava

public boolean add(E e) {
    modCount++;
    if (size == elementData.length)
        elementData = grow(size + 1);
    elementData[size] = e;
    size = size + 1;
    return true;
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity == 0 && elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        return elementData = new Object[Math.max(10, minCapacity)];   // first add
    int newCapacity = oldCapacity + Math.max(minCapacity - oldCapacity, oldCapacity >> 1);
    return elementData = Arrays.copyOf(elementData, newCapacity);    // 1.5x
}

03Why 1.5x, and why it's still O(1) on average

Growing by a constant factor is what makes appends cheap on average. If the list grew by a fixed amount (say +10 each time), adding n elements would copy 10 + 20 + 30 + ... ≈ n²/20 references: quadratic. Growing by a factor makes the copies a geometric series that sums to a small multiple of n.

Why 1.5 and not 2? A smaller factor wastes less unused capacity (at most a third of the array is empty right after a grow, versus half with 2x). It also lets freed old arrays be reused by later grows in some allocators. Each choice is a trade-off between wasted memory and how often you copy.

old >> 1 is a right shift: old / 2 rounded down. So 10 becomes 15, 15 becomes 22, 22 becomes 33.

Why 1.5x, and why it's still O(1) on averagediagram

Rendering diagram…

04Insert or remove in the middle: shifting

add(1, "x") on [a, b, c] must open a gap at index 1. It calls System.arraycopy(elementData, 1, elementData, 2, size - 1), which moves b and c one place right, then stores x at index 1. The number of moves is size - index.

remove(1) does the opposite: System.arraycopy(elementData, 2, elementData, 1, size - 2) slides everything after index 1 left, then sets the old last slot to null. Without that null, the array would keep the last object reachable and it could never be garbage-collected: a small memory leak.

System.arraycopy handles overlapping ranges correctly (as if it copied through a temporary buffer) and is an intrinsic: the JIT turns it into a tight memory move. That's fast, but it's still O(n): removing from the front of a million-element list moves a million references.

Insert or remove in the middle: shiftingdiagram

Rendering diagram…

05Pre-size when you know the count

If you'll add 100,000 elements, new ArrayList<>(100_000) allocates once. Starting from 10 instead means about 23 grows and roughly 300,000 reference copies, plus all the discarded arrays the garbage collector must clean up.

ensureCapacity(n) does the same for an existing list before a batch, and addAll(collection) grows once to fit the whole batch. After a big shrink, trimToSize() releases the spare slots, which helps for long-lived lists that won't grow again.

Main.javawhole filejava

List<Order> orders = new ArrayList<>(expectedCount);  // one allocation
ArrayList<String> log = new ArrayList<>();
log.ensureCapacity(50_000);                           // grow once before a batch
// ... later, after removing most entries:
log.trimToSize();                                     // capacity = size

06remove(int) vs remove(Object)

List has two remove methods: remove(int index) and remove(Object o). With a List<Integer>, list.remove(10) picks remove(int) because an exact int match beats boxing in overload resolution (Topic 3.4). It removes the element at index 10, not the value 10.

To remove the value, make the argument an object: list.remove(Integer.valueOf(10)) or list.remove((Integer) 10).

terminal

$ java Main

── expected output ──

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 10 out of bounds for length 3

at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:100)

...

at java.base/java.util.ArrayList.remove(ArrayList.java:551)

at Main.main(Main.java:6)

07What the costs add up to

get, set, size: O(1). add(e) at the end: amortised O(1). add(i, e), remove(i): O(n - i). contains, indexOf, remove(Object): O(n) with equals. removeIf: O(n) in one pass, however many elements go. Sorting with list.sort: O(n log n), done on the backing array directly.

Memory: the array of references (4 bytes each with compressed pointers, 8 without) plus up to a third spare capacity, plus the element objects. It's the most compact general-purpose list Java has, and CPU caches love it because the references sit side by side.

Try it yourself

1
Pre-size and count copies
In the first example, start capacity at 1000 instead of 10. Predict the number of grows and copies before running. (Zero and zero: the array never fills.)
2
Grow the mini list by 2x
In the mini ArrayList, change the growth to data.length * 2. Predict which grow lines print for five adds, and the final capacity, then run.
3
Fix the forward loop
In the removal example, keep the forward loop but add i--; right after a.remove(i);. Predict the output. Then explain why removeIf is still the better choice for large lists.

Code & diagrams

Watch the capacity grow by 1.5x New tab

Under 3 copies per add on average: that's what amortised O(1) means in practice.

Expected output

first capacities: 10 -> 15 -> 22 -> 33 -> 49 -> 73 -> 109 -> 163 -> 244
grows for 1000 adds: 12
final capacity: 1234
references copied in total: 2456
copies per add: 2.456

Build a mini ArrayList New tab

Removing at the front shifted every element; removing at the end shifted none. The capacity didn't shrink.

Expected output

  grow 2 -> 3
  grow 3 -> 4
  grow 4 -> 6
[a, b, c, d, e] capacity 6
  removed a, shifted 4
  removed e, shifted 0
[b, c, d] capacity 6

The remove(int) vs remove(Object) trap New tab

Expected output

after remove(1): [10, 30, 1, 2]
after remove(Integer.valueOf(1)): [10, 30, 2]
remove(30): Index 30 out of bounds for length 3
after remove((Integer) 30): [10, 2]

Removing in a loop: the skipping bug and the right ways New tab

removeIf marks the doomed elements first, then compacts the array once, so it's O(n) instead of O(n²).

Expected output

forward loop: [4, 5, 8]
backward loop: [5]
removeIf: [5]

Converting to an arrayjava

List<String> names = new ArrayList<>(List.of("asha", "ravi"));
String[] a = names.toArray(new String[0]);      // preferred: JDK sizes the array itself
String[] b = names.toArray(String[]::new);      // Java 11 overload, same result
Object[] c = names.toArray();                   // Object[], not String[]

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Read index 0 of an empty list

Write List<String> names = new ArrayList<>(); String first = names.get(0);.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0

at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:100)

at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:106)

at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:302)

at java.base/java.util.Objects.checkIndex(Objects.java:385)

at java.base/java.util.ArrayList.get(ArrayList.java:427)

at Main.main(Main.java:6)

Break #2

Remove a value from a List<Integer> by number

With List<Integer> ids = new ArrayList<>(List.of(10, 20, 30));, call ids.remove(10); meaning the value 10.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 10 out of bounds for length 3

at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:100)

at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:106)

at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:302)

at java.base/java.util.Objects.checkIndex(Objects.java:385)

at java.base/java.util.ArrayList.remove(ArrayList.java:551)

at Main.main(Main.java:6)

Myth vs fact

Myth

new ArrayList<>() allocates an array of 10 straight away.

Fact

Since Java 8 it starts with a shared empty array; the first add allocates 10. new ArrayList<>(0) grows differently: 1, 2, 3, 4, 6, 9, ...

Myth

ArrayList doubles its capacity.

Fact

It grows by 1.5x: old + (old >> 1). HashMap doubles; ArrayList doesn't.

Myth

Removing elements frees the memory.

Fact

The removed objects can be collected, but the backing array keeps its capacity. Call trimToSize() if a long-lived list shrank a lot.

Myth

LinkedList is faster than ArrayList for inserting.

Fact

Only if you're already holding an iterator at the right spot. Finding the spot is O(n) in a linked list, and System.arraycopy shifting is so cache-friendly that ArrayList usually wins anyway (Topic 9.3).

Interview problem

The problem

Remove all inactive users from a huge list

You have an ArrayList<User> with 2 million users, and about half are inactive. A teammate's code removes them with for (int i = 0; i < users.size(); i++) if (!users.get(i).active()) users.remove(i--);. It takes minutes. Explain why and fix it.

You're given

Keep the original list object (other code holds a reference to it).
Keep the remaining users in their original order.

The interviewer follows up

Why does removeIf not throw ConcurrentModificationException while a for-each with remove does?

Would a LinkedList make the original loop fast?

When it breaks

An ArrayList shared between request threads

What you see

Elements silently disappear or are overwritten (two threads write the same slot), size ends up wrong, and occasionally ArrayIndexOutOfBoundsException appears from inside ArrayList.add during a concurrent grow. The bug is rare and impossible to reproduce on a laptop.

Fix & prevent

Don't share mutable lists between threads. Confine them to one thread, or use Collections.synchronizedList with external locking for iteration, CopyOnWriteArrayList for read-mostly data, or a ConcurrentLinkedQueue for producer-consumer patterns (Topic 13.8).

A batch job builds a huge list without pre-sizing

What you see

Memory spikes at each grow because the old and new arrays coexist, garbage collection runs long, and near the end the job fails with OutOfMemoryError: Java heap space even though the final list would have fit.

Fix & prevent

Pre-size with new ArrayList<>(expected), or stream the data in chunks instead of collecting all of it. Monitor heap usage after GC rather than total heap.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Since JDK 17 the growth is computed by jdk.internal.util.ArraysSupport.newLength(oldLength, minGrowth, prefGrowth), which also handles overflow: lists can't exceed about Integer.MAX_VALUE - 8 elements (SOFT_MAX_ARRAY_LENGTH), and requesting more ends in OutOfMemoryError.
▸
elementData is transient. ArrayList has its own writeObject that serialises size and only the used elements, not the spare capacity, and readObject allocates exactly size slots.
▸
During a grow the old and new arrays are both alive, so the peak memory is about 2.5x the old array. For a list of 100 million references that's a 400 MB array plus a 600 MB one at the same moment, a classic cause of surprising OutOfMemoryError on big batch jobs. Pre-sizing avoids it.
▸
removeIf and removeAll/retainAll use a batch algorithm: one pass to find the survivors, one compaction, then the tail is cleared to null. Calling remove(i) in a loop for k elements costs O(k·n) instead.

Remember this

1
Inside, an ArrayList has two fields: Object[] elementData (the backing array) and int size (how many slots are really in use). The array's length is the capacity; size is never bigger than it. get(i) checks i < size and returns elementData[i]: one array read, O(1), however long the list.
2
new ArrayList<>() doesn't allocate ten slots straight away. Since Java 8 it points at a shared empty array, and the first add allocates the default capacity of 10. This saves memory for the many lists that stay empty. new ArrayList<>(1000) allocates 1000 slots up front.
3
When add finds the array full, it grows: the new capacity is old + (old >> 1), which is 1.5 times the old one (10, 15, 22, 33, 49, 73, ...). Arrays.copyOf allocates the bigger array and copies every reference across with System.arraycopy, a native bulk copy. The old array becomes garbage. Each grow costs O(n), but grows get rarer as the list gets bigger.
4
That's why appending is amortised O(1): "amortised" means averaged over many operations. Adding n elements one by one copies at most about 3n references in total across all the grows (n + 2n/3 + 4n/9 + ... = 3n), so each add costs a constant on average even though an unlucky single add is O(n).
5
add(index, e) and remove(index) call System.arraycopy to shift every element after index one place right or left: O(n - index). Adding or removing at the end is cheap; at the front it moves everything. remove also sets the vacated last slot to null so the removed object can be garbage-collected. contains and indexOf scan from the start with equals: O(n).
6
The array never shrinks by itself: remove a million elements and the capacity stays. trimToSize() cuts the array down to size, and ensureCapacity(n) grows it once ahead of a big batch. ArrayList isn't thread-safe: two threads adding at once can lose elements or throw ArrayIndexOutOfBoundsException (Topic 13.8 shows the safe options).

Explain it without notes

Describe how ArrayList.add works, including what happens when the array is full.

Why is appending to an ArrayList amortised O(1) when a single add can be O(n)?

What is the difference between capacity and size, and how do ensureCapacity and trimToSize relate to them?

Why is ArrayList usually faster than LinkedList even for some insert-heavy workloads?

What is the cost of add(0, e), remove(0), contains(e) and get(i) on an ArrayList of n elements?

Practice

Write static List<Integer> capacities(int adds) that returns the capacity sequence an ArrayList goes through (starting from 10 at the first add) while adding adds elements. Print the result for 100 adds.

Given List<String> words = new ArrayList<>(List.of("a", "bb", "ccc", "dd", "e")), remove every word of length 2 in a single O(n) pass without removeIf, by compacting in place with a write index, then trimming the tail.

Show that list.subList(1, 3).clear() removes elements from the original list. Start with [0, 1, 2, 3, 4] and print the list after the call.

Trade-offs

↔
1.5x growth wastes less memory than 2x but copies a little more often. If you know the final size, pre-sizing beats either.
↔
ArrayList is the best default list, but front insertions and removals are O(n). For a queue or stack, use ArrayDeque (Topic 9.7), which is O(1) at both ends.
↔
Holding a large list of boxed numbers costs several times the memory of a primitive array. For hot numeric data, an int[] with your own size counter is the ArrayList idea without the boxing.

Done when you can

Done when you can draw an ArrayList's fields and its backing array on the heap.
Done when you can state the default capacity, the 1.5x growth formula and when the first allocation happens.
Done when you can prove appends are amortised O(1).
Done when you can give the Big-O of get, add, add(i, e), remove(i) and contains.
Done when you avoid the remove(int) trap and remove in loops correctly.
Done when you pre-size lists whose size you know.

Command Palette

Words you'll meet

Step by step

01Two fields: the array and the size

02add at the end: the common, cheap case

03Why 1.5x, and why it's still O(1) on average

04Insert or remove in the middle: shifting

05Pre-size when you know the count

06remove(int) vs remove(Object)

07What the costs add up to

Try it yourself

Pre-size and count copies

Grow the mini list by 2x

Fix the forward loop

Code & diagrams

Break it on purpose

Read index 0 of an empty list

Remove a value from a List<Integer> by number

Myth vs fact

Interview problem

Remove all inactive users from a huge list

When it breaks

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can