Note: the jdk versions used in this series of articles are java8

The ArrayList class diagram is as follows:

The bottom layer of ArrayList is realized by array. Array is characterized by fixed size, while ArrayList realizes dynamic capacity expansion.

Some variables of ArrayList are as follows, which will be used in the following analysis.

/**
 * Default capacity
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * Empty object array
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * Empty array created by parameterless constructor
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * Cache variable of array storing data
 */
transient Object[] elementData;
/**
 * Number of elements
 */
private int size;

1, Initialize ArrayList

The following two constructors are generally used to initialize ArrayList

1.1 parameterless constructor

If no size is specified when initializing ArrayList, an empty array will be created.

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

1.2 constructor for specifying array size

Create an array with an estimated size. After specifying the size, you only specify the size of the initial value of the array, which does not affect the subsequent expansion. The advantage of specifying is that you can save memory and time.

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);
    }
}

2, Add elements and dynamically expand capacity

ArrayList. Add (e e e) source code:

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

elementData[size++] = e in add() is easy to understand, that is, insert the element into the size position, and then set size++. Let's focus on the ensureCapacityInternal(size + 1) method;

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

In the ensureCapacityInternal() method, judge whether the cache variable elementData is empty, that is, whether the element is added for the first time. If the element is added for the first time, set the initialization size to the default capacity of 10. Otherwise, it is an incoming parameter. The purpose of this method is to get the initialization array capacity. Call the ensureExplicitCapacity(minCapacity) method after obtaining the initialization capacity;

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

The ensueexplicitcapacity (minCapacity) method is used to determine whether capacity expansion is required. If the minCapacity is 10 and the elementData capacity is 0 when adding elements for the first time, capacity expansion is required. Call the grow(minCapacity) method.

// Maximum capacity of array
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // The expansion size is 1.5 times of the original array length
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // If the capacity to be expanded is smaller than the length to be expanded, the capacity to be expanded is used
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // If the expansion capacity is larger than the maximum array length, the maximum integer length is used
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

The grow(minCapacity) method resizes the array. The resizing size is 1.5 times that of the original array. If the calculated resizing capacity is smaller than the required capacity, the resizing size is the required capacity. If the resizing capacity is larger than the maximum capacity of the array, call the hugeCapacity(minCapacity) method to expand the array to the maximum length of an integer, and then point the elemetData array to the newly resized memory space and copy the elements to the new space.

When the required collection capacity is very large, a capacity expansion of 1.5 times will consume a lot of space. Therefore, it is recommended to estimate a capacity size during initialization.

3, Delete element

ArrayList provides two methods to delete elements, which can be deleted by index and element. The two deletions are similar. After deleting an element, move the following element forward once.

ArrayList.remove(int index) source code:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

When deleting an element, first judge whether the index is larger than the size of the ArrayList. If the index range is correct, assign the next element in the index position to the index position, and then -1 the size of the ArrayList. Finally, return the removed element. The operation diagram is as follows. Suppose I want to remove the element with index 1:

4, Summary

The bottom layer of ArrayList is implemented by array. It can be dynamically expanded by 1.5 times the original size. Although it can be dynamically expanded, it will waste space when the array is very large. Therefore, it is recommended to estimate the array size during initialization. ArrayList allows you to insert duplicate values and null values. ArrayList implements the RandomAccess interface and supports fast random access, that is, it can quickly find an element through the index. Therefore, it is more efficient to use the for loop during traversal. ArrayList is thread unsafe and can be accessed through collections Synchronizedlist turns it into a thread safe collection, but it is generally not used. Vector and CopyOnWriteArrayList are thread safe. Vector performance is average, and is gradually replaced by CopyOnWriteArrayList.

Pay attention and don't get lost

If you think the article is good, you are welcome to pay attention, like and collect. Your support is the driving force of my creation. Thank you.

If there is any problem with the article, please don't save your writing. Please leave a message and point it out. I will check and modify it in time.

If you want to see more things, you can search "Java journey" on wechat to follow. "Java journey" has sorted out various middleware tutorials and various Java related interview questions. These data can be obtained by scanning the QR code below for attention.