Understanding ArrayList's Core Implementation

Analyzing source code effectively requires focusing on specific questions rather than reading sequentially. For ArrayList, a fundamental Java collection class, several key aspects merit examination:

• How does ArrayList handle capacity expansion when adding elements?
• What specific implementation details make ArrayList thread-unsafe?
• What underlying data structure supports ArrayList operations?

Class Hierarchy and Interface Implemantation

ArrayList extends AbstractList and implements several key interfaces:

• List: Provides core collection operations
• Cloneable: Enables object duplication through clone()
• RandomAccess: Supports efficient element access by index
• Serializable: Allows object serialization

Initialization and Default Capacity

The default constructor creates an empty list with initial capacity handling:

public ArrayList() {
    this.internalArray = DEFAULT_EMPTY_STORAGE;
}

Two empty array constants serve different purposes:

• DEFAULT_EMPTY_STORAGE: Used when no initial capacity specified
• EMPTY_STORAGE: Used when explicitly creating zero-capacity lists

The distinction ensures proper capacity expansion behavior during first element addition.

Element Addition and Capacity Management

The add() method implemantation:

public boolean add(E element) {
    ensureSufficientCapacity(elementCount + 1);
    internalArray[elementCount++] = element;
    return true;
}

Capacity verification occurs through multiple methods:

private void ensureSufficientCapacity(int requiredCapacity) {
    if (internalArray == EMPTY_STORAGE) {
        requiredCapacity = Math.max(DEFAULT_CAPACITY, requiredCapacity);
    }
    verifyCapacity(requiredCapacity);
}

private void verifyCapacity(int requiredCapacity) {
    modificationCount++;
    if (requiredCapacity - internalArray.length > 0)
        expandCapacity(requiredCapacity);
}

Capacity Expansion Mechanism

The expansion algorithm uses a growth factor of 1.5x:

private void expandCapacity(int requiredCapacity) {
    int currentCapacity = internalArray.length;
    int newCapacity = currentCapacity + (currentCapacity >> 1);
    
    if (newCapacity < requiredCapacity)
        newCapacity = requiredCapacity;
    
    if (newCapacity > MAX_STORAGE_SIZE)
        newCapacity = calculateMaxCapacity(requiredCapacity);
    
    internalArray = Arrays.copyOf(internalArray, newCapacity);
}

For extremely large capacity requirements:

private static int calculateMaxCapacity(int minCapacity) {
    if (minCapacity < 0) throw new OutOfMemoryError();
    return (minCapacity > MAX_STORAGE_SIZE) ? 
        Integer.MAX_VALUE : MAX_STORAGE_SIZE;
}

The maximum array size constant accounts for JVM overhead:

private static final int MAX_STORAGE_SIZE = Integer.MAX_VALUE - 8;

This offset accommodates array metadata storage requirements and prevents integer overflow during capacity caclulations.