Internal Working of ArrayList
1. The Foundation: Dynamic Array
An ArrayList is essentially a wrapper around a standard Java Array. Unlike a
regular array which has a fixed size, an ArrayList can grow dynamically.
Initial State (Default Capacity = 10)
0 1 2 3 4 ... 9
Internal array is created with default capacity, but 'size' is 0.
2. Adding Elements & The "Size" Variable
There is a difference between Capacity (the length of the internal array) and
Size (how many elements you've actually added).
A B C 3 4
Size: 3 | Capacity: 10
3. The Resizing Logic (Growth Factor)
When the array becomes full (size == capacity), ArrayList performs the following
steps:
1. Calculates new capacity: New Capacity = Old Capacity + (Old Capacity
>> 1). (Essentially 1.5x the old size).
2. Creates a New Array with the larger size.
3. Uses [Link]() to move elements from the old array to the
new one.
4. The old array is garbage collected.
Visualizing Resize (from 10 to 15)
Old Array (Full):
1 ... 10
New Array (1.5x larger):
1 ... 10 11 12 13 14 15
4. Performance Implications (Interview Talk)
• Add (End): Amortized O(1). Fast, unless a resize is triggered.
• Add (Middle/Start): O(n). Requires Shifting all subsequent elements
to the right.
• Get (Index): O(1). Direct memory access.
• Remove: O(n). Requires Shifting elements to the left to fill the gap.
5. Internal Code Snippet
// Simplified internal representation
transient Object[] elementData; // The actual array
private int size; // The number of elements
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}