1. Overview of ArrayList

1.1ArrayList features

• ArrayList is a dynamic array that implements the List interface
• ArrayList can allow element to be Null
• ArrayList is thread unsafe

1.2 ArrayList data structure

The underlying data structure of ArrayList is array. The array element type is Object type, which means all types of data can be stored

2. Source code analysis of ArrayList

2.1 attribute

private static final int DEFAULT_CAPACITY = 10; / / the default size is 10,
		In fact, when the parameterless constructor is called for initialization, the data in which the data is stored is an empty array,
		It is only initialized when add is called

private static final Object[] EMPTY_ELEMENTDATA = {}; 
		 //Use the constructor with parameters for initialization, if the initcapacity is 0, or the incoming collection
			When empty, points to the array

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
		// Use this array when calling the parameterless constructor

transient Object[] elementData;  // Array of real data

private int size;  // Number of array elements

2.2 construction method

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

The construction method with initialCapacity. If initialCapacity=0, elementData points to an empty array; if elementData > 0, elementData initializes

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

Default construction method. Execute default empty array

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

A construction method with parameters can be passed into a collection. If there are no elements in the collection, point to an empty array; otherwise, copy the elements in the collection to the elementData array. The underlying layer calls the local method System.arraycopy().

2.3 main methods

2.3.1add(): add this element to the end of the list

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

First, determine whether the current elementData array can hold the new elements. If there is not enough space, you need to expand the capacity first, and then insert the elements.
Size is the number of data in an array. To add an element, you must first determine whether the array can fit (size+1) elements

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

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

The calculateCapacity() method is used to calculate capacity. First, determine whether elementData is the default empty array (constructed with no parameter constructor)

• If elementData is the default empty array, this is the first time to add elements. Then size=0, minCapacity=size+1=1. By calling the Math.max() method, minCapacity=DEFAULT_CAPACITY=10 will be returned
• If elementData is an empty array, this is the first time to add an element. Then size=0, minCapacity=size+1=1, the Math.max() method will not be called, and minCapacity=1 will be returned
• If elementData is not an empty array and is not the default empty array, then size!=0, minCapacity=size+1, the Math.max() method will not be called, and minCapacity=size+1 will be returned

// Determine whether to expand
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    
    if (minCapacity - elementData.length > 0)
        // Capacity expansion
        grow(minCapacity);
}

modCount: the operand (the attribute in the parent class AbstractList) indicates that the ArrayList has been operated on.
In the insureexplicitcapacity() method, the first step is to increase the number of operands by 1, and compare the required minimum space capacity with the current actual length of the array:

• If elementData is the default empty array, the capacity it needs now is 10, but elementData.length=0, so it needs to be expanded
• If elementData is an empty array, it now needs 1, but elementData.length=0, so it needs to be expanded
• If elementData is a non empty array, if it needs more capacity after adding an element than the original array, it needs to be expanded; otherwise, it does not need to be expanded.

 private void grow(int minCapacity) {
   
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

The grow() method is expanded to ensure that the ArrayList can store at least minCapacity elements.
For the first expansion, the new capacity is 1.5 times of the original
After the first expansion, if the capacity is still smaller than minCapacity, the capacity will be expanded to minCapacity. If at this time the capacity has exceeded the maximum capacity of ArrayList, integer.max-value – 8, then the maximum newCapacity is integer.max-value

Then we call Arrays.copyOf(elementData, newCapacity) to copy the old array, and the bottom call is System.arraycopy, which is a native method.

Therefore, to avoid expansion as much as possible, array replication is very performance intensive! And the old array needs GC!