ArrayList implements the List interface, and its underlying data structure is an array, so the time complexity of obtaining the value of any element in the container is O(1), and the time complexity of adding or deleting elements is O(N). Each ArrayList instance has a capacity variable. Capacity is the size of the container used by The ArrayList to store elements. When a new element is added to the container, Capacity is automatically expanded. Note that ArrayList is a non-thread-safe container, which is prone to thread-safety issues in a multithreaded environment.

The source code

Member variables

private static final int DEFAULT_CAPACITY = 10; // The default capacity is 10

private static final Object[] EMPTY_ELEMENTDATA = {}; // Initialize an empty array with capacity 0

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // There is no specified capacity for initialization

transient Object[] elementData; // An array of elements

private int size; // The number of elements in the container
Copy the code

A constructor

public ArrayList(int initialCapacity) {
       // Create an array if the initial size is > 0
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}/** * Constructs an empty list with an initial capacity of ten. */
    public ArrayList(a) {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // The default array size is 10
    }
Copy the code

Add elements


public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

private void add(E e, Object[] elementData, int s) {
        // The number of container elements equals the length of the array triggers the expansion condition
        if (s == elementData.length)
          // Call the grow method for expansion
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

// The expansion logic calculates the size to be expanded, and copies the original array elements to the expanded array
private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0|| elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = newObject[Math.max(DEFAULT_CAPACITY, minCapacity)]; }}private Object[] grow() {
        return grow(size + 1);
    }
// Calculate the size of the expanded array
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0

        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            returnhugeLength(oldLength, minGrowth); }}Copy the code

According to the source code, before adding elements, judge the current container size and array length, decide whether to expand, otherwise directly add to the container. The length of the new array after expansion needs to be calculated. The length of the new array is 1.5 times the size of the original array.

Adds an element at the specified location

public void add(int index, E element) {
// Check whether the insertion position is valid
        rangeCheckForAdd(index);
// Record the number of times the container has been modified
        modCount++;
        final int s;
        Object[] elementData;
// Capacity expansion conditions
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
// Move the following elements back to make room
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }
Copy the code