ReviseAlgo Logo

Collections Framework

ArrayList

Analyze ArrayList internal structures, array copy mechanics, resizing logic, and random access execution.

Interview: Focuses on array growth factor (1.5x), System.arraycopy usage, O(1) indexing, and initial capacity optimization.

Last Updated: June 13, 2026 • 10 min read

An ArrayList is a resizable-array implementation of the List interface. It is backed by a native heap array that dynamically grows when elements exceed the array's capacity.

Random Access

Implements RandomAccess, providing constant-time O(1) lookup complexity for elements using integer index keys.

Dynamic Resizing

When capacity is reached, ArrayList allocates a new array of size oldCapacity + (oldCapacity gg 1) (1.5x size) and copies elements using native code.

Insertion Cost

Adding to the end is amortized O(1). Inserting or deleting from the middle takes O(N) time due to array copy operations.

Internal Growth & Array Copy

Understanding the resizing mechanism is key to optimizing application performance:

  1. The default initial capacity is 10 (allocated lazily on the first element addition).
  2. When the array fills up, a new array is calculated: newCapacity = oldCapacity + (oldCapacity >> 1).
  3. JVM invokes Arrays.copyOf, which calls native System.arraycopy to transfer elements into the new array.
  4. The old array is dereferenced and cleaned up by GC.

Common Pitfalls

  • Frequent Resizing: Adding millions of elements to an ArrayList initialized with default capacity, triggering dozens of array allocations and garbage collections.
  • Inserting at index 0: Repeatedly calling list.add(0, item) in a loop, which forces shifting all existing array elements, causing O(N²) aggregate latency.

Best Practices

  • Pre-size initial capacity: Always specify the expected size in the constructor (e.g. new ArrayList<>(expectedSize)) when size is predictable.
  • Use trimToSize(): Invoke list.trimToSize() after collection population to reduce unused capacity elements and conserve memory.

Interview-Relevant Information

Q1: How does ArrayList calculate its new capacity on expansion?
Answer: It increases the current capacity by approximately 50% using bit-shifting arithmetic: int newCapacity = oldCapacity + (oldCapacity >> 1).

Q2: Why does ArrayList implement RandomAccess?
Answer: RandomAccess is a marker interface. It signals that the collection supports constant-time (O(1)) element retrieval by index. This allows algorithms to choose index loops over iterators for performance.

Quick Checklist

Can you state the default capacity of an empty ArrayList, calculate the size after expansion, and explain why inserting at the front is expensive? If yes, you understand ArrayList.

Use Cases

Storing and fetching data records that require rapid indexing lookup operations.

Building memory-cached database rows where capacity sizes are predictable.

Common Mistakes

Initializing empty collections when storing millions of data structures.

Inserting elements at index 0 repeatedly in high-throughput data pipelines.