ArrayList is a widely used implementation of the List interface that stores elements in an Object array. It's optimized for frequent read operations but does not provide thread safety.

• Insertion/Deletion Performance: These operations are relatively slow because they require shifting elements and potentially resizing the underlying array.
• Access Speed: Elements can be accesssed quickly using index-based lookup due to the contiguous memory allocation of arrays.
• Data Structure: Internally, ArrayList uses a dynamic array structure that automatically adjusts its size as needed.

Core Implementation Details

Key instance variables:

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;

Main constructors:

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Invalid capacity: " + initialCapacity);
    }
}

public ArrayList(Collection<? extends E> collection) {
    Object[] arrayCopy = collection.toArray();
    if ((size = arrayCopy.length) != 0) {
        if (collection.getClass() == ArrayList.class) {
            elementData = arrayCopy;
        } else {
            elementData = Arrays.copyOf(arrayCopy, size, Object[].class);
        }
    } else {
        elementData = EMPTY_ELEMENTDATA;
    }
}

Resizing Process Analysis

Element addition triggers the resizing mechanism:

public boolean add(E element) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = element;
    return true;
}

private void ensureCapacityInternal(int requiredCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, requiredCapacity));
}

private static int calculateCapacity(Object[] data, int minCapacity) {
    if (data == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0) {
        expandArray(minCapacity);
    }
}

private void expandArray(int minCapacity) {
    int currentLength = elementData.length;
    int expandedCapacity = currentLength + (currentLength >> 1);
    
    if (expandedCapacity - minCapacity < 0) {
        expandedCapacity = minCapacity;
    }
    
    if (expandedCapacity - MAX_ARRAY_SIZE > 0) {
        expandedCapacity = determineHugeCapacity(minCapacity);
    }
    
    elementData = Arrays.copyOf(elementData, expandedCapacity);
}

Resizing Characteristics

• Initial Allocation: New ArrayList instances start with a default capacity of 10 elements.
• Growth Factor: When expansion occurs, the new capacity becomes approximately 1.5 times the current size.
• Trigger Condition: Resizing happens automatically when the number of elements exceeds the current array capacity.
• Expansion Strategy: A larger array is created, existing elements are copied over, and internal references are updated to point to the new storage.

The rseizing workflow follows these steps: First, the system checks if sufficient space exists for new elements. If not, it calculates a new capacity based on the growth factor, allocates a new array, copies all existing elements, updates internal pointers, and finally adds the new element to the expanded array.