Java ArrayList Internal Working

Every ArrayList operation you call — add(), get(), remove(), contains() — touches one thing: a plain Object[] array named elementData. Knowing what each method does to that array, when it copies the array, and why it sets slots to null after removal changes how you write collection code and how you answer the most common collection interview questions in Java.

What Is Inside an ArrayList?

ArrayList<E> is backed by a single resizable Object[] array. Three integer fields manage its state.

ARRAYLIST INTERNAL FIELDS (simplified from JDK source):

  transient Object[] elementData;   ← the backing array — stores all elements
  private int        size;           ← logical size: how many elements are stored
  private static final int DEFAULT_CAPACITY = 10;

  IMPORTANT DISTINCTION:
    elementData.length  = physical capacity (allocated array slots)
    size                = logical size     (elements actually stored)

    These two numbers are DIFFERENT until trimToSize() is called.

INITIAL STATE (new ArrayList<>()):
  elementData = {}       ← empty sentinel array (DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
  size        = 0
  capacity    = 0 (lazy — first add allocates the default 10-slot array)

INITIAL STATE (new ArrayList<>(5)):
  elementData = new Object[5]
  size        = 0
  capacity    = 5 (allocated immediately, even though size = 0)

AFTER add("A"), add("B"), add("C") on default ArrayList:
  elementData = ["A", "B", "C", null, null, null, null, null, null, null]
                  0     1     2     3     4     5     6     7     8     9
  size        = 3
  capacity    = 10  (elementData.length = 10)

  The 7 null slots at indices 3–9 are pre-allocated capacity.
  get(2) returns "C" directly from elementData[2] in O(1).

Basic Overview — How Each Core Method Touches elementData

METHOD         WHAT IT DOES TO elementData                 COMPLEXITY
─────────────────────────────────────────────────────────────────────
add(e)         elementData[size] = e; size++               O(1) amort
               (grows array if size == capacity)

add(i, e)      shift elements right from i to size-1       O(n)
               elementData[i] = e; size++

get(i)         return elementData[i]                        O(1)

set(i, e)      Object old = elementData[i]                  O(1)
               elementData[i] = e; return old

remove(i)      shift elements left from i+1 to size-1      O(n)
               elementData[--size] = null  ← GC help

remove(obj)    linear scan to find index, then shift        O(n)

contains(obj)  linear scan — indexOf(obj) >= 0             O(n)

size()         return size (the int field)                  O(1)

isEmpty()      return size == 0                             O(1)

clear()        fill elementData[0..size-1] with null        O(n)
               size = 0  ← frees element references for GC

toArray()      Arrays.copyOf(elementData, size)             O(n)

iterator()     returns new Itr() with cursor=0, modCount    O(1)
               stored at creation time

GROWTH (triggered when size == elementData.length):
               newCapacity = oldCapacity + (oldCapacity >> 1)  ≈ 1.5×
               elementData = Arrays.copyOf(elementData, newCapacity)  O(n)
               Then insert the new element

When Capacity Matters — Pre-Sizing

CAPACITY PLANNING DECISION:

  Loading N elements into default ArrayList:
    Grow events:   10 → 15 → 22 → 33 → 49 → 73 → 109 → ...
    For 10,000 elements: ~17 grow events = ~17 System.arraycopy calls
    Each copy is O(n) at that moment.
    Total extra work: n elements copied across all resizes ≈ 2n copies.

  Loading N elements into pre-sized ArrayList:
    new ArrayList<>(N) or new ArrayList<>(N/0.75) for safety
    0 grow events. 0 extra copies. Allocation pays once upfront.

  PRODUCTION RULE:
    If you know the expected element count before building the list:
      new ArrayList<>(expectedSize)
    If loading from a Collection of known size:
      new ArrayList<>(collection)  ← ArrayList(Collection) sizes exactly
    If building from a stream and final size is unknown:
      stream.collect(Collectors.toList())  ← runtime-resized automatically

How Each Operation Works Internally

add(E element) — Append to End

add("D") on a list [A, B, C] with capacity 10, size 3:

  Step 1: ensureCapacityInternal(size + 1)
          = ensureCapacityInternal(4)
          Required capacity 4 <= current capacity 10 → no resize needed

  Step 2: elementData[size] = e
          elementData[3] = "D"

  Step 3: size++  → size = 4

  elementData = ["A","B","C","D", null, null, null, null, null, null]
                  0    1    2    3    4      5      6      7      8      9
  size = 4,  capacity = 10

─────────────────────────────────────────────────────────────────────

add("K") on a list [A..J] with capacity 10, size 10 (full):

  Step 1: ensureCapacityInternal(11)
          size 11 > capacity 10 → GROW required

  GROW SEQUENCE:
    oldCapacity = 10
    newCapacity = 10 + (10 >> 1) = 10 + 5 = 15
    elementData = Arrays.copyOf(elementData, 15)  ← copies 10 elements, adds 5 null slots

  Step 2: elementData[10] = "K"
  Step 3: size++ → size = 11

  elementData = ["A","B","C","D","E","F","G","H","I","J","K", null, null, null, null]
                  0    1    2    3    4    5    6    7    8    9   10   11    12    13   14
  size = 11, capacity = 15

add(int index, E element) — Insert at Position

add(2, "X") on list ["A","B","C","D"], size=4, capacity=10:

  BEFORE: ["A","B","C","D", null, null, ...]
            0    1    2    3

  Step 1: Range check: index 2 is in [0, size=4] — valid
  Step 2: ensureCapacityInternal(5) → 5 <= 10, no grow needed
  Step 3: System.arraycopy(elementData, 2, elementData, 3, 2)
          Copies elements from index 2 RIGHTWARD by 1 position:
          elementData[3] = elementData[2] = "C"
          elementData[4] = elementData[3] = "D"

  DURING SHIFT: ["A","B","C","C","D", null, ...]
                  0    1    2    3    4

  Step 4: elementData[2] = "X"
  Step 5: size++ → 5

  AFTER: ["A","B","X","C","D", null, null, null, null, null]
           0    1    2    3    4
  size=5, capacity=10

remove(int index) — Remove by Position

remove(1) on list ["A","B","C","D"], size=4, capacity=10:

  BEFORE: ["A","B","C","D", null, null, ...]
            0    1    2    3

  Step 1: Range check: 0 <= index < size — valid
  Step 2: Object oldValue = elementData[1] = "B"  ← saved to return
  Step 3: numMoved = size - index - 1 = 4 - 1 - 1 = 2
  Step 4: System.arraycopy(elementData, 2, elementData, 1, 2)
          Copies elements from index 2 LEFTWARD by 1 position:
          elementData[1] = elementData[2] = "C"
          elementData[2] = elementData[3] = "D"

  DURING SHIFT: ["A","C","D","D", null, ...]
                  0    1    2    3

  Step 5: elementData[--size] = null
          elementData[3] = null  ← CRITICAL: clears stale reference for GC
          size = 3

  AFTER: ["A","C","D", null, null, null, null, null, null, null]
           0    1    2    3
  size=3, capacity=10

  WHY NULL THE LAST SLOT:
    elementData[3] still held a reference to "D" before the null.
    Even after the logical remove, the Object[] array held a strong
    reference. Setting it to null lets GC reclaim "D" if nothing else
    holds a reference to it. Without this null, the ArrayList would be
    a memory leak for removed elements.

grow() — Capacity Expansion

GROW FORMULA (Java 8+):
  private Object[] grow(int minCapacity) {
      int oldCapacity = elementData.length;
      if (oldCapacity > 0) {
          int newCapacity = ArraysSupport.newLength(
              oldCapacity,
              minCapacity - oldCapacity, // minimum growth
              oldCapacity >> 1           // preferred growth: 50%
          );
          return elementData = Arrays.copyOf(elementData, newCapacity);
      } else {
          return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
      }
  }

GROWTH SEQUENCE (from default capacity 10):
  size 10  → grow → capacity 15   (+5  = 50%)
  size 15  → grow → capacity 22   (+7  = 47%)
  size 22  → grow → capacity 33   (+11 = 50%)
  size 33  → grow → capacity 49   (+16 = 48%)
  size 49  → grow → capacity 73   (+24 = 49%)
  size 73  → grow → capacity 109  (+36 = 49%)
  size 109 → grow → capacity 163  (+54 = 50%)

  Each grow calls Arrays.copyOf() which calls System.arraycopy()
  — a native JVM operation, very fast but still O(n).
  Amortised across n insertions: each element is copied ≤ 2 times on average.

GROW FOR FIRST ADD ON DEFAULT ArrayList:
  Default ArrayList uses DEFAULTCAPACITY_EMPTY_ELEMENTDATA sentinel.
  First add(): elementData is empty → grow to DEFAULT_CAPACITY = 10.
  This lazy allocation saves memory when many ArrayLists are created
  but never populated (common in frameworks creating empty lists).

iterator() and Fail-Fast Behaviour

FAIL-FAST ITERATOR — how modCount works:

  ArrayList maintains: protected transient int modCount = 0;
  modCount increments on EVERY structural modification (add, remove, clear, grow)

  iterator() creates: new Itr() {
      int cursor = 0;
      int expectedModCount = modCount;  ← snapshot of modCount at creation
  }

  Itr.next():
      if (modCount != expectedModCount)
          throw new ConcurrentModificationException();
      return (E) elementData[cursor++];

  SCENARIO:
    list = ["A","B","C","D"], modCount = 5
    it = list.iterator()          → expectedModCount = 5
    it.next() → "A"               → modCount == 5 ✓
    list.add("E")                 → modCount = 6
    it.next()                     → modCount(6) != expectedModCount(5)
                                  → ConcurrentModificationException!

  SAFE REMOVAL DURING ITERATION:
    Use Iterator.remove() — it calls ArrayList.remove() then
    updates expectedModCount = modCount, keeping them in sync.

  SAFE ALTERNATIVE:
    list.removeIf(predicate) — manages its own modCount synchronisation internally.

Core Operations with Examples

Observing Capacity vs Size and Grow Events

Output:
=== Lazy allocation on default ArrayList ===
After new ArrayList<>()   : size=0 capacity=0
After first add()          : size=1 capacity=10

=== Growth sequence (default capacity 10) ===
  size=1   → GREW to capacity=10  (+10)
  size=11  → GREW to capacity=15  (+5)
  size=16  → GREW to capacity=22  (+7)
  size=23  → GREW to capacity=33  (+11)
  size=34  → GREW to capacity=49  (+16)
  size=50  → GREW to capacity=73  (+24)

=== Pre-sized ArrayList — zero grow events ===
After new ArrayList<>(50) : size=0 capacity=50
After 50 adds             : size=50 capacity=50
Zero grow events — no extra array copies

=== trimToSize() ===
Before trimToSize: size=3 capacity=100
After trimToSize : size=3 capacity=3

ModCount, Fail-Fast Iterator, and Safe Patterns

Output:
=== for-each with modification → CME ===
ConcurrentModificationException thrown as expected
List state after CME: [java, spring, redis, docker, java]

=== Iterator.remove() — safe removal during traversal ===
After it.remove(): [java, spring, docker, java]

=== removeIf() — clean predicate-based removal ===
After removeIf(): [spring, kafka, redis]

=== Collect + replace — clear rebuild pattern ===
Filtered (stream): [java, spring, kafka, docker, java]

=== modCount increments on structural modifications ===
Created list, take iterator snapshot:
After add(4) — iterator.next() will throw:
  ConcurrentModificationException (modCount changed)

Null Handling, Shift Costs, and Memory Effects

Output:
=== Null set after remove() — enables GC ===
Before remove: size=5
After remove(1): [A, C, D, E]

Raw array slots:
  [0] = A
  [1] = C
  [2] = D
  [3] = E
  [4] = null
  [5] = null
  [6] = null
  [7] = null
  [8] = null
  [9] = null
Slot 4 is null — GC can reclaim old 'E' reference

=== O(1) add at end vs O(n) add at front ===
add(element)     N=100,000: 4 ms
add(0, element)  N=100,000: 312 ms
Ratio: ~78x slower for front inserts

=== clear() releases all element references ===
Before clear: [X, Y, Z] capacity=10
After clear:  size=0 capacity=10
All slots null: true
(capacity preserved — array not freed, only elements nulled)

Real-World Example — Swiggy Order Processing Pipeline

A Swiggy order processing pipeline demonstrates how ArrayList's internals affect production decisions. A large batch of orders is loaded into a pre-sized ArrayList to avoid multiple grow operations. Orders are filtered via removeIf() (safe, O(n) in one pass). The pipeline uses get(i) for O(1) positional access at each processing stage. trimToSize() releases unused capacity before the list is passed to downstream services.

Output:
--- Building processing pipeline ---
  Created pipeline: size=0 capacity=12
  After addAll:     size=12 capacity=12
  After removeIf:   size=8 capacity=12
  Processing first 3 orders via get():
    get(0): [S001] C-Priya     Rs.   349  Koramangala CONFIRMED
    get(1): [S003] C-Ananya    Rs.   249  HSR Layout  CONFIRMED
    get(2): [S004] C-Karan     Rs.  1299  Whitefield  CONFIRMED
  After trimToSize: size=8 capacity=8 (no wasted slots)

--- Final pipeline (8 orders) ---
  [S001] C-Priya     Rs.   349  Koramangala CONFIRMED
  [S003] C-Ananya    Rs.   249  HSR Layout  CONFIRMED
  [S004] C-Karan     Rs.  1299  Whitefield  CONFIRMED
  [S006] C-Meera     Rs.   449  Indiranagar CONFIRMED
  [S007] C-Arjun     Rs.   799  HSR Layout  CONFIRMED
  [S009] C-Vijay     Rs.   899  Whitefield  CONFIRMED
  [S010] C-Kavya     Rs.   549  Koramangala CONFIRMED
  [S012] C-Pooja     Rs.   699  HSR Layout  CONFIRMED

--- Operation complexity context ---
  get(0):     O(1) — elementData[0] direct read
  contains(): O(n) — full scan via indexOf()
  remove(0):  O(n) — shifts all elements left by 1
  add():      O(1) amort — elementData[size] = e; size++
  size():     O(1) — return the 'size' int field
  contains(order): true

Performance Considerations

Every grow is O(n) but amortised to O(1). Over n insertions, the total work across all grows is O(n) — each element is copied at most a constant number of times. The amortised cost per insertion is O(1). The worst case for any single add() is O(n) — but this happens only when the backing array is full.

add(0, element) is the most expensive List operation per call. Inserting at index 0 requires shifting every existing element one position to the right via System.arraycopy. For a list of 100,000 elements, each front insertion moves 100,000 references. For frequent front insertions, LinkedList or ArrayDeque is the correct data structure.

Best Practices

Pre-size when the expected element count is known. new ArrayList<>(n) allocates an array of exactly n slots, eliminating all grow operations during loading. The formula new ArrayList<>(collection.size()) when building from another collection is correct and commonly used. For a count that is an upper bound: new ArrayList<>(upperBound) followed by trimToSize() after loading releases unused slots.

Use removeIf(predicate) instead of iterator removal or index-based removal in loops. removeIf() performs a single O(n) pass — it computes which elements to keep, uses System.arraycopy to close the gaps, and nulls the trailing slots in one sweep. Index-based removal in a loop is O(n²) — each remove(i) shifts all subsequent elements. This is a common performance mistake in fresher code reviews.

Avoid contains() in a hot loop. contains() is O(n). Calling it repeatedly inside a loop is O(n²). If membership testing is the primary operation, move to a HashSet for O(1) contains(). Keep the ArrayList for ordered access and the HashSet for fast lookup as two separate structures keyed on the same data.

Use List.copyOf() to create an immutable snapshot. After building an ArrayList, passing it directly to callers allows them to modify internal state. List.copyOf(list) creates a compact immutable copy that callers cannot modify. It uses a plain array internally with no wasted capacity — more memory-efficient than calling trimToSize() and returning the original.

Common Mistakes

Mistake 1 — Structural Modification During for-each Iteration

Mistake 2 — Repeated Front Insertions on Large Lists

Mistake 3 — Using contains() in a Membership-Test Loop

Mistake 4 — Not Pre-Sizing for Bulk Load

Interview Questions

Q1. What is the internal data structure of ArrayList in Java?

ArrayList<E> is backed by a transient Object[] elementData array. It maintains a size field tracking the logical element count, which differs from elementData.length (the physical capacity). On default construction, elementData is an empty sentinel array — the actual 10-slot array is allocated lazily on the first add(). The size field is what size() returns; elementData.length is the currently allocated capacity.

Q2. How does ArrayList resize when full?

When size == elementData.length, the next add() calls grow(). The new capacity is oldCapacity + (oldCapacity >> 1) — approximately 1.5 times the current capacity. Arrays.copyOf(elementData, newCapacity) creates a new array, copies all elements into it, and replaces elementData. This is O(n) for the grow operation but O(1) amortised per insertion because each element is copied at most a constant number of times across the full growth sequence.

Q3. Why does ArrayList.remove() set the last slot to null?

After remove(index), elements are shifted left by one position using System.arraycopy. The last meaningful slot (at the old size - 1 position) now holds a stale reference — the same object reference that was shifted left to fill the gap. Without nulling this slot, the Object[] array holds a strong reference to the removed element, preventing garbage collection even though it is logically gone from the list. Setting elementData[--size] = null releases the reference so the GC can reclaim the removed object.

Q4. What is modCount and how does it enable fail-fast iteration?

modCount is a protected transient int field inherited from AbstractList. It increments on every structural modification: add(), remove(), clear(), set() (sort), and any operation that changes the list's size or structure. When iterator() is called, the iterator captures modCount as expectedModCount. On every next() call, the iterator checks modCount == expectedModCount. If they differ — meaning a structural change occurred after the iterator was created — it throws ConcurrentModificationException. Iterator.remove() is the exception: it updates expectedModCount = modCount after performing the removal, keeping them in sync.

Q5. What is the difference between size() and capacity() in ArrayList?

size() returns the number of elements logically stored in the list. Capacity is the length of the underlying elementData array — the number of elements that can be stored before the next grow. size() is a public method. Capacity is not directly accessible through the public API — ensureCapacity(minCapacity) and trimToSize() manage it, but there is no capacity() getter. size() always ≤ capacity. After trimToSize(), size == capacity. The distinction matters for memory management and pre-sizing decisions.

Q6. When does ArrayList's add() perform in O(n) rather than O(1)?

add(element) is O(n) in two cases: when a grow is triggered (O(n) to copy all existing elements to the new array), and when using add(int index, E element) with any index other than size (O(n) to shift elements right). For add(element) at the end, grows are rare and amortised out — the average cost per insertion is O(1). For add(0, element) (front insertion), every call is O(n) — the entire list shifts right. Pre-sizing eliminates grows; using a different data structure (ArrayDeque, LinkedList) eliminates front-insertion cost.

FAQs

What is the default initial capacity of ArrayList?

The default initial capacity is 10 — but the array is not allocated until the first add(). A new ArrayList<>() stores a reference to a shared empty sentinel array (DEFAULTCAPACITY_EMPTY_ELEMENTDATA) to avoid the allocation cost for empty lists. The first add() triggers the creation of the 10-slot array. new ArrayList<>(0) uses a different empty sentinel (EMPTY_ELEMENTDATA) and grows to 1 on first add, not 10.

Does ArrayList allow null elements?

Yes. null can be added to any position, including multiple nulls. list.contains(null) returns true if any null element is present (uses e == null comparison). list.remove(null) removes the first null occurrence. list.indexOf(null) returns the index of the first null.

What is the difference between ArrayList.clear() and creating a new ArrayList?

clear() sets all elements to null and resets size to 0 but keeps the backing array allocated at its current capacity. A new ArrayList<>() starts with the empty sentinel array. clear() is appropriate when the list will be refilled soon — no reallocation needed. Creating a new instance releases the current backing array to GC. For lists with large allocated-but-unused capacity, a new instance uses less memory immediately; clear() retains the capacity for fast reuse.

Is ArrayList thread-safe?

No. Concurrent structural modifications from multiple threads corrupt the backing array — lost updates, stale reads, or ArrayIndexOutOfBoundsException during simultaneous resizes. Use Collections.synchronizedList(new ArrayList<>()) for a globally locked wrapper, or CopyOnWriteArrayList for read-heavy concurrent lists. Neither is equivalent in performance to a single-threaded ArrayList.

Why is ArrayList preferred over LinkedList for most use cases?

ArrayList's O(1) get(index) and cache-friendly contiguous memory make it faster for random access and sequential iteration — the two most common list operations. LinkedList's get(index) is O(n) because it must traverse the chain from head or tail. ArrayList's add(element) is O(1) amortised, competitive with LinkedList's O(1) addLast(). LinkedList adds overhead of two pointers per node (~24 bytes/node) versus ArrayList's 4-byte reference. LinkedList only wins when frequent O(1) insertions and removals at both ends are required alongside the List interface — ArrayDeque handles that better.

What happens to the backing array when ArrayList.clear() is called?

clear() iterates from index 0 to size-1, sets each slot to null, then sets size = 0. The backing elementData array itself is NOT freed — its length (capacity) is preserved. This means a cleared ArrayList still occupies the same heap memory as before. The advantage: immediately adding elements to a cleared list uses the existing array without triggering a grow. If memory should be reclaimed, call trimToSize() after clear() or assign a new ArrayList<>().

Summary

Every ArrayList operation is ultimately an operation on a transient Object[] elementData array. add(element) sets elementData[size++] and may trigger a 1.5× grow via Arrays.copyOf. get(index) reads elementData[index] in O(1). remove(index) shifts elements left with System.arraycopy and nulls the last slot for GC. contains() scans linearly. clear() nulls all element slots without releasing the backing array.

Three internal implementation details answer most ArrayList interview questions: the size vs capacity distinction (lazy allocation, pre-sizing benefit), the 1.5× growth formula (amortised O(1) for append), and modCount (fail-fast iterator contract). Understanding why remove(index) nulls the last slot — preventing memory leaks through stale object references — separates candidates who have read source code from those who have only read tutorials.

What to Read Next