ArrayList can be said to be the most commonly used collection container in Java development, today to analyze the source of ArrayList, you can further understand the implementation principle of ArrayList.

Member variables of ArrayList:

// Initial capacity :10 private static final int DEFAULT_CAPACITY = 10; Private static Final Object[] EMPTY_ELEMENTDATA = {}; Private static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // ArrayList element transient Object[] elementData; // size is the size of the ArrayList. If elementData is not an empty array, size is the private int size less than elementData.length.Copy the code

It can also be seen from elementData that the interior of an ArrayList is realized through arrays. In fact, the addition, deletion, modification, and check of elements in an ArrayList are all operations on arrays.

Constructor of ArrayList:

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

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

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

When constructing an ArrayList, you can specify the container’s initialCapacity, initialCapacity, and construct an array of given initial size as the data set. When a no-parameter construct is used, an array with an empty default capacity is used as the initial data set. You can also use any other Collection as a construction parameter. As you can see from the source code, the Collection C is directly converted into an array as the data set (if the data set is not an Object array, such as a multidimensional array, the elements are copied into the data set). The construction of an ArrayList is essentially an initialization of its internal array.

The add method:

Public Boolean add(E E) {public Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! // add element e elementData[size++] = e; // add element e elementData[size++] = e;return true; } public void add(int index, E element) {// Check if the new position index is out of bounds; EnsureCapacityInternal (size + 1); // Make sure that the current set of data can hold the new element. // Increments modCount!! Arraycopy (elementData, index, elementData, index + 1, size-index); arrayCopy (elementData, index, elementData, index + 1, size-index); ElementData [index] = element; size++; }Copy the code

When an element is added, if the location is not specified, it is added to the last bit of the existing element in the internal array, at the end of the ArrayList. If the index position is specified, determine whether the index exceeds the boundary and whether to expand the capacity. Finally, move the element next to the index position and set the index position to the newly added element.

Note that the added elements are not nulled, so elements in an ArrayList can be null.

In the add method, ensureCapacityInternal(int minCapacity) is called to ensure that the set of data can hold the new element:

private void ensureCapacityInternal(int minCapacity) {
    if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code // If the minimum capacity required to add a new element is greater than the length of the array, it needs to be expandedif (minCapacity - elementData.length > 0)
        grow(minCapacity);
}Copy the code

Grow (int minCapacity)

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; NewCapacity: 1.5 times the oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: ElementData = array.copyof (elementData, newCapacity); }Copy the code

To expand an array, you create a new array of the desired size and copy the elements of the original array into the new array, which is specified as the internal data set of the ArrayList.

Summary: When an ArrayList adds an element, it determines whether the added position is out of bounds in the internal array. If it is, it throws an exception. If it does not, it checks whether the array can hold the newly added element. If it can, it will be directly placed in the array. If not, expand the array and save it to the array.

The remove method:

Public E remove(int index) {// Check rangeCheck(index); modCount++; E oldValue = elementData(index); Int numMoved = size-index - 1; // copy all elements after the position of the element to numMoved after the index position startedif(numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); ElementData [--size] = null; elementData[--size] = null; // clear tolet GC do its work
    return oldValue;
}Copy the code

Remove another overloaded method is to remove a given element. Its implementation is to traverse the array, find the index value of the element, and then call remove(int index) method, according to the index value to remove.

When an ArrayList deletes an element, it determines whether the index value is out of bounds. If the index value is out of bounds, it throws an exception. If the boundary is not crossed, take the element to be deleted, and then move all elements after that element forward one bit.

The set method:

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}Copy the code

The set method modifies the value of an element at a specified position in the list. The implementation is very simple: directly modify the value of the specified position in the array.

The get method:

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}Copy the code

The get method is very simple to implement and all you have to do is get the position of the heap to determine if it’s out of bounds, and then just take the value from the array.

Can be seen from the source of the above analysis, the realization of the ArrayList is an array of operation, at the time of adding and removing elements, will involve the expansion of an array of array element position and movement, relative to query and modify element is more complex, so the ArrayList is suitable for use in the query and modify are frequent, but under the circumstances of less add and delete.