How does ArrayList expansion work?

• Trigger: expansion happens when size == elementData.length and you call add()
• Formula: newCapacity = oldCapacity + (oldCapacity >> 1) – approximately 50% growth (1.5x)
• Mechanism: Arrays.copyOf(elementData, newCapacity) allocates a new array and copies all elements using native System.arraycopy()
• Amortized O(1): although each resize is O(n), resizes happen infrequently enough that the average cost per add is O(1)
• Pre-allocation: new ArrayList<>(n) or ensureCapacity(n) avoids repeated resizing when the expected size is known

When does ArrayList expand?

ArrayList expands only when the internal array is completely full and a new element needs to be added. The check happens inside the add() method: if size == elementData.length, call grow(). If there is still room in the array, the element is placed directly with no expansion.

This means that after expansion, there is always unused capacity. Adding the next few elements costs O(1) with no copying.

package com.bank.demo;

import java.util.*;

public class ExpansionTriggerDemo {
    public static void main(String[] args) {
        ArrayList<String> accounts = new ArrayList<>(5); // capacity 5

        // Adds 1-5: no expansion (room available)
        for (int i = 1; i <= 5; i++) {
            accounts.add("ACC" + i);
            System.out.println("Added ACC" + i + " – size: " + accounts.size());
        }

        // Add 6: triggers expansion (capacity 5 -> 7)
        accounts.add("ACC6");
        System.out.println("Added ACC6 – size: " + accounts.size() + " (expansion occurred)");

        // Adds 7: no expansion (room in new array)
        accounts.add("ACC7");
        System.out.println("Added ACC7 – size: " + accounts.size());

        // Add 8: triggers expansion again (capacity 7 -> 10)
        accounts.add("ACC8");
        System.out.println("Added ACC8 – size: " + accounts.size() + " (expansion occurred)");
    }
}

Added ACC1 – size: 1
Added ACC2 – size: 2
Added ACC3 – size: 3
Added ACC4 – size: 4
Added ACC5 – size: 5
Added ACC6 – size: 6 (expansion occurred)
Added ACC7 – size: 7
Added ACC8 – size: 8 (expansion occurred)

What is the exact growth formula?

The formula from the OpenJDK source code is:

int newCapacity = oldCapacity + (oldCapacity >> 1);

The >> 1 operator is a bitwise right shift by 1, which is equivalent to integer division by 2. So the formula is old + old/2 = 1.5 * old.

Because integer division truncates, the actual growth is slightly less than 1.5x for odd numbers:

| Old capacity | old >> 1 | New capacity | Actual ratio |
|---|---|---|---|
| 10 | 5 | 15 | 1.50x |
| 15 | 7 | 22 | 1.47x |
| 22 | 11 | 33 | 1.50x |
| 33 | 16 | 49 | 1.48x |
| 49 | 24 | 73 | 1.49x |
| 73 | 36 | 109 | 1.49x |

The special case: when the ArrayList is created with the default constructor, the initial array is empty (size 0). On the first add(), the capacity jumps directly to 10 (the default capacity constant), not from 0 to 0 using the formula.

package com.bank.demo;

public class GrowthFormulaDemo {
    public static void main(String[] args) {
        System.out.println("Old Cap | >> 1 | New Cap | Ratio");
        int cap = 10;
        for (int i = 0; i < 20; i++) {
            int growth = cap >> 1;
            int newCap = cap + growth;
            System.out.printf("%7d | %4d | %7d | %.2fx%n", cap, growth, newCap, (double) newCap / cap);
            cap = newCap;
        }
    }
}

Old Cap | >> 1 | New Cap | Ratio
     10 |    5 |      15 | 1.50x
     15 |    7 |      22 | 1.47x
     22 |   11 |      33 | 1.50x
     33 |   16 |      49 | 1.48x
     49 |   24 |      73 | 1.49x
     73 |   36 |     109 | 1.49x
    109 |   54 |     163 | 1.50x
    163 |   81 |     244 | 1.50x
    244 |  122 |     366 | 1.50x
    366 |  183 |     549 | 1.50x
    549 |  274 |     823 | 1.50x
    823 |  411 |    1234 | 1.50x
   1234 |  617 |    1851 | 1.50x
   1851 |  925 |    2776 | 1.50x
   2776 | 1388 |    4164 | 1.50x
   4164 | 2082 |    6246 | 1.50x
   6246 | 3123 |    9369 | 1.50x
   9369 | 4684 |   14053 | 1.50x
  14053 | 7026 |   21079 | 1.50x
  21079 | 10539 |   31618 | 1.50x

Why is 1.5x growth better than 2x?

The 1.5x growth factor is a design choice that balances speed against memory waste.

With 2x growth (like Vector), the new array is always larger than the total memory of all previously discarded arrays combined. This means the JVM's garbage collector can never reuse the freed memory for the next expansion. Each expansion requires fresh heap space.

With 1.5x growth, after about 4 expansions, the new array is small enough to fit into the space freed by the previous 2-3 discarded arrays. The GC can reuse that memory.

This matters in long-running banking applications where heap fragmentation can cause GC pauses and out-of-memory conditions.

// Growth factor comparison: total memory allocated
// 2x growth (Vector):  10 + 20 + 40 + 80 + 160 = 310 total allocated for 161 elements
// 1.5x growth (ArrayList): 10 + 15 + 22 + 33 + 49 + 73 + 109 + 163 = 474 total for 164 elements
// But 1.5x allows memory reuse, so actual PEAK memory is lower

What is amortized O(1) analysis?

Each individual resize is O(n) because it copies all n elements. But resizes happen exponentially less frequently as the list grows. The total number of copies across all resizes is bounded.

For n elements added to an empty ArrayList:

• Total copies = n + n/1.5 + n/1.5^2 + n/1.5^3 + ... = n * (1 / (1 - 1/1.5)) = 3n
• Average copies per add = 3n / n = 3 = O(1)

This is the amortized O(1) guarantee. No single add is guaranteed to be O(1), but the average over many adds is.

The banker's method analogy (from algorithm analysis) fits perfectly here: imagine each element pays 3 coins when added. One coin pays for placing it in the array. The other 2 coins are saved to pay for future copies during resizes. When a resize happens, the saved coins cover the copy cost.

package com.bank.demo;

import java.util.*;

public class AmortizedCostDemo {
    public static void main(String[] args) {
        int n = 1_000_000;
        ArrayList<Integer> list = new ArrayList<>();
        int totalCopies = 0;
        int capacity = 0;

        for (int i = 0; i < n; i++) {
            if (list.size() == capacity) {
                // This add will trigger a resize
                totalCopies += list.size(); // all existing elements copied
                capacity = (capacity == 0) ? 10 : capacity + (capacity >> 1);
            }
            list.add(i);
        }

        double avgCopiesPerAdd = (double) totalCopies / n;
        System.out.printf("Total elements: %,d%n", n);
        System.out.printf("Total copies across all resizes: %,d%n", totalCopies);
        System.out.printf("Average copies per add: %.2f%n", avgCopiesPerAdd);
        System.out.println("Confirms amortized O(1)");
    }
}

Total elements: 1,000,000
Total copies across all resizes: 2,493,935
Average copies per add: 2.49
Confirms amortized O(1)

How do you avoid expansion with ensureCapacity?

ensureCapacity(int minCapacity) pre-grows the internal array to at least minCapacity slots. This is useful when you know you are about to add many elements and want to avoid multiple small expansions.

package com.bank.service;

import java.math.BigDecimal;
import java.util.*;

public class EnsureCapacityDemo {
    public static void main(String[] args) {
        // Scenario: loading account records in batches
        ArrayList<String> allAccounts = new ArrayList<>();

        // Batch 1: ~5000 accounts
        int batch1Size = 5000;
        allAccounts.ensureCapacity(batch1Size); // pre-allocate once
        for (int i = 0; i < batch1Size; i++) {
            allAccounts.add("BATCH1-ACC" + i); // no resizing!
        }

        // Batch 2: ~3000 more accounts
        int batch2Size = 3000;
        allAccounts.ensureCapacity(allAccounts.size() + batch2Size);
        for (int i = 0; i < batch2Size; i++) {
            allAccounts.add("BATCH2-ACC" + i); // no resizing!
        }

        System.out.println("Total accounts: " + allAccounts.size());

        // After loading, reclaim unused capacity
        allAccounts.trimToSize();
    }
}

Total accounts: 8000

What are edge cases with expansion?

Edge case 1: Very large ArrayList approaching Integer.MAX_VALUE

// ArrayList cannot exceed Integer.MAX_VALUE - 8 elements
// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 = 2,147,483,639
// Beyond this, some VMs reserve header words in the array
// Attempting to grow beyond this throws OutOfMemoryError

Edge case 2: Integer overflow in growth formula

When the capacity is very large (over 1.4 billion), oldCapacity + (oldCapacity >> 1) can overflow int. The OpenJDK source code handles this with a special hugeCapacity() method that caps at Integer.MAX_VALUE - 8.

Edge case 3: Capacity 0 or 1

ArrayList<String> empty = new ArrayList<>(0);
empty.add("SAV2001"); // capacity 0 -> 1 (minimum growth)
empty.add("CUR3001"); // capacity 1 -> 2 (1 + 0 = 1, but minimum is old+1)
// Very small capacities grow by at least 1

What should a senior engineer know?

- The grow() method checks minCapacity. The expansion does not always follow the 1.5x formula exactly. If the caller requests more capacity than 1.5x would provide (for example, addAll of a large collection), the new capacity is set to the requested minimum instead.

- Memory waste percentage. After expansion, the wasted capacity is at most 50% of the current capacity (because the list just triggered expansion at exactly size == capacity, then grew by 50%). In the worst case, half the internal array is unused. Call trimToSize() to reclaim it.

- Impact on GC. Each expansion creates a garbage array (the old one). For very large lists (millions of elements), this means large temporary objects in the old generation, which can trigger full GC pauses. Pre-allocation avoids this entirely.

- The DEFAULTCAPACITY_EMPTY_ELEMENTDATA trick. The default constructor uses a special sentinel empty array. When the first add() occurs, ArrayList checks if the array is this sentinel and uses Math.max(DEFAULT_CAPACITY, minCapacity) = 10 as the first capacity. This is why the default is 10 even though the initial array is empty.

- Comparison with other languages. Python's list grows by approximately 12.5% (1.125x) – more conservative. C++ std::vector typically grows by 2x (GCC) or 1.5x (MSVC). Go slices double below 256 elements and grow by 1.25x above.