Definition
- Internal storage:
Object[] elementData– a plain Java array that holds element references - Default capacity: 10, but lazy-initialized – the array is empty until the first
add()call - Growth: when
size == capacity, a new array of sizeoldCapacity + (oldCapacity >> 1)is created and all elements are copied viaArrays.copyOf() - Size vs capacity:
size()returns the number of stored elements; capacity is the array length and is not exposed through a public method - Pre-allocate with
new ArrayList<>(n)to avoid repeated resizing when the expected size is known
ArrayList is like a bank's account register book with numbered pages. The default book has 10 pages. When all 10 are filled, the clerk buys a bigger book with 15 pages (1.5x), photocopies all 10 pages into the new book, and adds the 11th entry. The old book is discarded. If the bank knows it will open 10,000 accounts this year, it buys a 10,000-page book upfront instead of upgrading the book 30 times.
Understanding the Concepts
What is the internal structure of ArrayList?
At its core, ArrayList is an Object[] array with a size counter. The array holds element references, and size tracks how many of those slots are actually used.
Here is a simplified version of the key fields and methods from the OpenJDK source:
package com.bank.demo;
import java.util.Arrays;
public class SimpleArrayList<E> {
private static final int DEFAULT_CAPACITY = 10;
private Object[] elementData;
private int size;
// Default constructor: lazy initialization
public SimpleArrayList() {
this.elementData = new Object[0]; // empty until first add
}
// Capacity constructor: pre-allocate
public SimpleArrayList(int initialCapacity) {
this.elementData = new Object[initialCapacity];
}
// add(E e): append at end
public boolean add(E e) {
if (size == elementData.length) {
grow();
}
elementData[size++] = e;
return true;
}
// get(int index): O(1) direct access
@SuppressWarnings("unchecked")
public E get(int index) {
if (index >= size) throw new IndexOutOfBoundsException("Index: " + index);
return (E) elementData[index];
}
// grow: create new array of 1.5x capacity
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = (oldCapacity == 0)
? DEFAULT_CAPACITY
: oldCapacity + (oldCapacity >> 1); // 1.5x
elementData = Arrays.copyOf(elementData, newCapacity);
}
public int size() { return size; }
public static void main(String[] args) {
SimpleArrayList<String> accounts = new SimpleArrayList<>();
accounts.add("SAV2001");
accounts.add("CUR3001");
accounts.add("FD4001");
System.out.println("Element at 1: " + accounts.get(1));
System.out.println("Size: " + accounts.size());
}
}
Element at 1: CUR3001
Size: 3
How does the growth formula work?
The formula is newCapacity = oldCapacity + (oldCapacity >> 1). The >> 1 is a bitwise right shift, which divides by 2. So the formula is old + old/2 = 1.5 * old.
The growth sequence starting from the default capacity of 10:
| Resize number | Old capacity | New capacity | Elements copied |
|---|---|---|---|
| 1 | 10 | 15 | 10 |
| 2 | 15 | 22 | 15 |
| 3 | 22 | 33 | 22 |
| 4 | 33 | 49 | 33 |
| 5 | 49 | 73 | 49 |
| 6 | 73 | 109 | 73 |
| 7 | 109 | 163 | 109 |
| 8 | 163 | 244 | 163 |
| 9 | 244 | 366 | 244 |
| 10 | 366 | 549 | 366 |
To reach 1 million elements starting from capacity 10, ArrayList resizes about 40 times, copying all elements each time. That is why pre-allocation matters.
package com.bank.demo;
public class GrowthSequenceDemo {
public static void main(String[] args) {
int capacity = 10;
int resizeCount = 0;
int targetSize = 1_000_000;
System.out.println("Resize | Old Cap | New Cap");
while (capacity < targetSize) {
int oldCapacity = capacity;
capacity = capacity + (capacity >> 1);
resizeCount++;
if (resizeCount <= 15) { // show first 15
System.out.printf("%6d | %7d | %7d%n", resizeCount, oldCapacity, capacity);
}
}
System.out.println("...");
System.out.println("Total resizes to reach " + targetSize + ": " + resizeCount);
}
}
Resize | Old Cap | New Cap
1 | 10 | 15
2 | 15 | 22
3 | 22 | 33
4 | 33 | 49
5 | 49 | 73
6 | 73 | 109
7 | 109 | 163
8 | 163 | 244
9 | 244 | 366
10 | 366 | 549
11 | 549 | 823
12 | 823 | 1234
13 | 1234 | 1851
14 | 1851 | 2776
15 | 2776 | 4164
...
Total resizes to reach 1000000: 40
Why is the growth factor 1.5x and not 2x?
Java's ArrayList grows by 1.5x. C++ std::vector also typically grows by 1.5x (MSVC, libc++). Some implementations (GCC libstdc++) grow by 2x.
The argument for 1.5x over 2x is about memory reuse. When the growth factor is 2x, the new array is always larger than the sum of all previously discarded arrays, so the JVM can never reuse the old memory. With 1.5x, after several rounds of growth, the new array can fit into the space left by previous discarded arrays.
In practice, the difference is small for most applications. But for a banking system loading millions of records, 1.5x growth wastes less memory than 2x growth.
For comparison, Vector (the legacy class) grows by 2x: 10 to 20 to 40 to 80 to 160.
How do add and remove work internally?
Adding at the end is simple: place the element at elementData[size] and increment size. If the array is full, grow first. This is amortized O(1) because resizing happens infrequently.
Adding in the middle requires shifting all subsequent elements one position to the right using System.arraycopy(). This is O(n) because every element after the insertion point must move.
Removing works the same way in reverse: shift all subsequent elements one position to the left, then null out the last slot (to help garbage collection).
package com.bank.demo;
import java.util.*;
public class AddRemoveInternalsDemo {
public static void main(String[] args) {
List<String> accounts = new ArrayList<>(List.of("A", "B", "C", "D", "E"));
System.out.println("Original: " + accounts);
// add(2, "X") – insert at index 2
// Internally: shift C, D, E right by 1, then set index 2 to X
accounts.add(2, "X");
System.out.println("After add(2, X): " + accounts);
// [A, B, X, C, D, E] – C, D, E all shifted right
// remove(2) – remove index 2
// Internally: shift C, D, E left by 1, null out last slot
accounts.remove(2);
System.out.println("After remove(2): " + accounts);
// [A, B, C, D, E] – C, D, E shifted back left
// add at end – no shifting needed
accounts.add("F");
System.out.println("After add(F): " + accounts);
}
}
Original: [A, B, C, D, E]
After add(2, X): [A, B, X, C, D, E]
After remove(2): [A, B, C, D, E]
After add(F): [A, B, C, D, E, F]
How do you set initial capacity correctly?
When you know (or can estimate) the final number of elements, pass the expected size to the constructor. This avoids repeated resize-and-copy cycles.
The rule of thumb: if you are loading N elements, use new ArrayList<>(N). If you are loading elements from a query where the count is unknown but you can estimate an upper bound, use that estimate.
package com.bank.service;
import java.math.BigDecimal;
import java.util.*;
public class BulkLoadDemo {
record Account(String id, String holder, BigDecimal balance) {}
public static void main(String[] args) {
int expectedCount = 2_000_000; // EOD batch: 2 million records
// WRONG – starts at capacity 10, resizes ~40 times
long start = System.nanoTime();
List<Account> bad = new ArrayList<>();
for (int i = 0; i < expectedCount; i++) {
bad.add(new Account("ACC" + i, "Holder" + i, BigDecimal.valueOf(i)));
}
long badTime = System.nanoTime() - start;
// CORRECT – pre-allocated, zero resizes
start = System.nanoTime();
List<Account> good = new ArrayList<>(expectedCount);
for (int i = 0; i < expectedCount; i++) {
good.add(new Account("ACC" + i, "Holder" + i, BigDecimal.valueOf(i)));
}
long goodTime = System.nanoTime() - start;
System.out.printf("Without pre-alloc: %d ms%n", badTime / 1_000_000);
System.out.printf("With pre-alloc: %d ms%n", goodTime / 1_000_000);
}
}
Without pre-alloc: 1250 ms
With pre-alloc: 890 ms
What is the difference between size and capacity?
size() is the number of elements actually stored in the list. Capacity is the length of the internal array – the number of elements it can hold before resizing. Capacity is always greater than or equal to size.
There is no public capacity() method in ArrayList. You cannot directly inspect the capacity. But you can manage it:
ensureCapacity(minCapacity)– guarantees the internal array has at leastminCapacityslots. Useful before a known batch of additions.trimToSize()– shrinks the internal array to matchsize(). Useful after bulk loading to reclaim wasted memory.
package com.bank.demo;
import java.util.*;
import java.lang.reflect.Field;
public class SizeVsCapacityDemo {
public static void main(String[] args) throws Exception {
ArrayList<String> accounts = new ArrayList<>();
// After construction: size=0, capacity=0 (lazy)
accounts.add("SAV2001");
// After first add: size=1, capacity=10 (default allocated)
for (int i = 0; i < 9; i++) accounts.add("ACC" + i);
// size=10, capacity=10 (full)
accounts.add("TRIGGER_RESIZE");
// size=11, capacity=15 (grew 1.5x)
System.out.println("Size: " + accounts.size());
System.out.println("Capacity: " + getCapacity(accounts));
// trimToSize – reclaim wasted memory
accounts.trimToSize();
System.out.println("After trimToSize - Capacity: " + getCapacity(accounts));
}
// Reflection to read internal capacity (for demonstration only)
private static int getCapacity(ArrayList<?> list) throws Exception {
Field f = ArrayList.class.getDeclaredField("elementData");
f.setAccessible(true);
return ((Object[]) f.get(list)).length;
}
}
Size: 11
Capacity: 15
After trimToSize - Capacity: 11
What exceptions can occur?
- IndexOutOfBoundsException:
get(index)orset(index, e)withindex < 0orindex >= size(). - ConcurrentModificationException: modifying the list structurally (add/remove) while iterating with a for-each or iterator.
- OutOfMemoryError: when the internal array cannot be allocated (either the requested capacity exceeds
Integer.MAX_VALUE - 8, or the JVM runs out of heap).
package com.bank.demo;
import java.util.*;
public class ArrayListExceptionsDemo {
public static void main(String[] args) {
List<String> accounts = new ArrayList<>(List.of("SAV2001", "CUR3001"));
// IndexOutOfBoundsException
try {
accounts.get(5);
} catch (IndexOutOfBoundsException e) {
System.out.println("Index error: " + e.getMessage());
}
// ConcurrentModificationException
try {
for (String acc : accounts) {
if (acc.equals("SAV2001")) {
accounts.remove(acc);
}
}
} catch (ConcurrentModificationException e) {
System.out.println("Concurrent mod: " + e.getClass().getSimpleName());
}
// Negative initial capacity
try {
new ArrayList<>(-1);
} catch (IllegalArgumentException e) {
System.out.println("Negative capacity: " + e.getMessage());
}
}
}
Index error: Index 5 out of bounds for length 2
Concurrent mod: ConcurrentModificationException
Negative capacity: Illegal Capacity: -1
What are common mistakes with ArrayList?
Mistake 1: Not setting initial capacity for large lists
// WRONG – 40+ resizes for 1M elements
List<String> accounts = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) accounts.add("ACC" + i);
// CORRECT – zero resizes
List<String> accounts = new ArrayList<>(1_000_000);
Mistake 2: Confusing size() with capacity
ArrayList<String> list = new ArrayList<>(1000);
System.out.println(list.size()); // 0, NOT 1000!
// size() counts elements. Capacity is the array length.
// The list has 0 elements but space for 1000.
Mistake 3: Forgetting trimToSize after bulk load
ArrayList<String> list = new ArrayList<>(1_000_000);
// Only 500 elements added (business logic changed)
for (int i = 0; i < 500; i++) list.add("ACC" + i);
// Internal array still has 1,000,000 slots – wasting ~4 MB!
list.trimToSize(); // now capacity = 500
What should a senior engineer know?
- Lazy initialization. Since Java 8, the default constructor creates an empty array {}, not a 10-element array. The capacity-10 allocation happens on the first add(). This saves memory when many ArrayLists are created but never populated (common in frameworks that pre-create beans).
- System.arraycopy is a JVM intrinsic. The array copying during resize and shifting is handled by System.arraycopy(), which the JVM replaces with optimized machine code (typically a single memcpy or memmove instruction). This is why ArrayList's O(n) shift is faster than you might expect.
- Maximum capacity. ArrayList's maximum capacity is Integer.MAX_VALUE - 8 (2,147,483,639 elements). The -8 headroom is for array header bytes on some VMs. In practice, you will hit OutOfMemoryError long before reaching this limit.
- Amortized analysis. Adding n elements to an empty ArrayList costs O(n) total, not O(n^2). Each element is copied at most O(log n) times across all resizes. This is the amortized O(1) guarantee.
- Sublist views. ArrayList.subList() returns a view backed by the parent. Structural changes to the parent invalidate the sublist. If you need a safe copy for pagination: new ArrayList<>(list.subList(from, to)).
- Serialization. ArrayList writes only the size elements during serialization (not empty slots). It has custom writeObject/readObject methods that skip the unused capacity.
Visual Overview
ArrayList internal structure
elementData (Object[])
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ SAV │ CUR │ FD │ LON │ null│ null│ null│ null│ null│ null│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
size = 4 capacity = 10
After adding 7 more elements (11 total): resize!
Old: [SAV, CUR, FD, LON, A, B, C, D, E, F] (capacity 10, full)
│ Arrays.copyOf → System.arraycopy
▼
New: [SAV, CUR, FD, LON, A, B, C, D, E, F, G, null, null, null, null]
size = 11 capacity = 15
Growth: 10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → ...
Formula: newCap = oldCap + (oldCap >> 1) // 1.5x
Key Takeaway
ArrayList is one of the most-used classes in Java, and understanding its internals helps you write faster code. It stores elements in an Object[] array that starts at capacity 10 (lazy-allocated on the first add) and grows by 1.5x when full. Growth means allocating a new, larger array and copying all elements using System.arraycopy(), which is a JVM intrinsic – fast native code, but still O(n) per resize.
The key performance insight is pre-allocation. When loading 2 million account records during an end-of-day batch at the National Bank of India, Rajesh uses new ArrayList<>(2_000_000) to avoid the 40 resize cycles that would happen with the default constructor. After loading, he calls trimToSize() to reclaim any unused capacity.
The distinction between size and capacity trips up many developers. size() returns the count of actual elements. Capacity is the internal array length – how many elements can fit before the next resize. There is no public capacity() method, but ensureCapacity() and trimToSize() let you manage it.
Remember one sentence: ArrayList is an Object[] array that starts at 10, grows by 1.5x, and you should always pre-allocate when you know the expected size.
---