Java ArrayList Deep Dive — Internals and Performance

4 minute read

ArrayList is Java’s most-used collection. It’s backed by a resizable array that provides O(1) random access and amortized O(1) appends. Understanding its internals helps you write faster, more memory-efficient code.

How ArrayList Works Internally

ArrayList<String> list = new ArrayList<>();

Internally:
┌────────────────────────────────────┐
│ Object[] elementData               │
│ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │
│ │ A │ B │ C │   │   │   │   │   │ │  ← capacity = 8
│ └───┴───┴───┴───┴───┴───┴───┴───┘ │
│ int size = 3                       │  ← actual elements
└────────────────────────────────────┘
  • elementData — the internal Object[] array.
  • size — the number of actual elements (≤ capacity).
  • Capacity — the length of the backing array.

Initial Capacity and Growth

Default Behaviour

new ArrayList<>()    // initial capacity: 0 (empty array)
                      // first add() → grows to 10

Growth Factor

When the array is full, ArrayList creates a new array 1.5× the old size and copies elements:

Capacity growth:  0 → 10 → 15 → 22 → 33 → 49 → 73 → ...
Formula:          newCapacity = oldCapacity + (oldCapacity >> 1)
                              = oldCapacity * 1.5

The Cost of Growing

add("A") → size 1, capacity 10     (one-time allocation)
add("B") → size 2, capacity 10     (no resize)
...
add("J") → size 10, capacity 10    (no resize)
add("K") → size 11, capacity 15    (resize! copy 10 elements)

Each resize is O(n) — but it happens infrequently, so appends are amortized O(1).

Pre-sizing with ensureCapacity()

If you know the approximate size, pre-allocate:

// ❌ BAD — many resizes for large lists
List<String> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add("item " + i);  // multiple resize + copy operations
}

// ✅ GOOD — single allocation
List<String> list = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) {
    list.add("item " + i);  // no resizing needed
}

You can also call ensureCapacity() after creation:

list.ensureCapacity(500_000);

Trimming Excess Capacity

list.trimToSize();  // shrinks backing array to match size

Useful after bulk loading when no more elements will be added.

Big-O Complexity

Operation Time Notes
get(index) O(1) Direct array access
set(index, element) O(1) Direct array access
add(element) (end) O(1) amortized O(n) on resize
add(index, element) O(n) Shifts elements right
remove(index) O(n) Shifts elements left
remove(Object) O(n) Search + shift
contains(Object) O(n) Linear search
indexOf(Object) O(n) Linear search
size() O(1) Stored field
isEmpty() O(1) Checks size == 0

Iterating Over ArrayList

Enhanced for-loop (Preferred)

for (String item : list) {
    System.out.println(item);
}

Index-based (Fast for ArrayList)

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));  // O(1) per access
}

Index-based loop is fine for ArrayList (implements RandomAccess), but terrible for LinkedList — O(n²) total.

Iterator

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    if (item.equals("remove-me")) {
        it.remove();  // safe removal during iteration
    }
}

ListIterator (Bidirectional)

ListIterator<String> lit = list.listIterator(list.size()); // start at end
while (lit.hasPrevious()) {
    System.out.println(lit.previous());  // iterate backwards
}

ConcurrentModificationException

Modifying a list while iterating with for-each triggers this:

// ❌ THROWS ConcurrentModificationException
for (String item : list) {
    if (item.startsWith("X")) {
        list.remove(item);  // structural modification during iteration!
    }
}

Safe Ways to Remove During Iteration

// 1. Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("X")) {
        it.remove();
    }
}

// 2. removeIf() — cleanest (Java 8+)
list.removeIf(item -> item.startsWith("X"));

// 3. Collect and remove
List<String> toRemove = list.stream()
    .filter(item -> item.startsWith("X"))
    .toList();
list.removeAll(toRemove);

Memory Implications

Memory Per Element

ArrayList:
  Each element = 1 object reference (4 or 8 bytes)
  + possible wasted capacity (empty slots)

LinkedList:
  Each element = Node object (16 bytes header + prev + next + item = ~40 bytes)

For 1 million Strings:

  • ArrayList: ~8 MB (references) + String objects
  • LinkedList: ~40 MB (nodes) + String objects

Wasted Space

// After removing 900,000 elements from a 1M list:
// size = 100,000, but capacity might still be 1,000,000
// Call trimToSize() to reclaim memory
list.trimToSize();

ArrayList vs Array

Feature int[] / String[] ArrayList<Integer> / ArrayList<String>
Size Fixed Dynamic
Primitives ✅ Direct ❌ Autoboxing (Integer, not int)
Type safety Limited Full generics
API Minimal Rich (sort, search, stream)
Memory Compact Higher overhead
Performance Slightly faster Slightly slower (autoboxing)

Use arrays for fixed-size primitive collections where performance matters. Use ArrayList for everything else.

Practical Example: Building a Dynamic Log

public class ActivityLog {
    private final List<String> entries = new ArrayList<>(100);

    public void log(String event) {
        String entry = LocalDateTime.now() + " — " + event;
        entries.add(entry);
    }

    public List<String> getRecent(int count) {
        int from = Math.max(0, entries.size() - count);
        return List.copyOf(entries.subList(from, entries.size()));
    }

    public List<String> search(String keyword) {
        return entries.stream()
                .filter(e -> e.contains(keyword))
                .toList();
    }

    public int size() {
        return entries.size();
    }
}

Best Practices

  1. Pre-size when you know the approximate count — avoids unnecessary resizes.
  2. Program to List, not ArrayList — List<String> list = new ArrayList<>().
  3. Use removeIf() instead of manual iteration + removal.
  4. trimToSize() after bulk loading if memory matters.
  5. Prefer List.of() for small immutable lists.
  6. Use index-based iteration only for RandomAccess lists.
  7. Never use raw types — always ArrayList<String>, never ArrayList.

Key Takeaways

  1. ArrayList is backed by a resizable Object[] array that grows by 1.5×.
  2. O(1) random access and amortized O(1) append make it the default choice.
  3. Insert/remove in the middle is O(n) due to element shifting.
  4. Pre-size with the constructor or ensureCapacity() for large lists.
  5. Use Iterator.remove() or removeIf() to avoid ConcurrentModificationException.

What’s Next?

Next: LinkedList Deep Dive — doubly-linked node structure, when it’s appropriate, and why it’s rarely the right choice.

Updated:

You may also enjoy