More Java container source code analysis can be consulted: Java Container Source Analysis Series (ongoing updates!)

(1) Overview of ArrayList

• ArrayList is a dynamic array, based on array implementation, its capacity can automatically grow.
• ArrayList implements Random Access interface, supports fast random access, implements Serializable interface, so it supports serialization, serialization and deserialization, implements Cloneable interface, and can be cloned.

(2) Class names

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Analysis: ArrayList inherits from AbstractList, and implements List interface, Random Access interface, Clonable interface and Serial ZABLE interface.

• AbstractList: It also inherits the List interface and implements the methods in the List interface.

1. Perhaps you will have a question about why ArrayList does not directly implement the List interface, but rather implements the List interface through AbstractList, and then inherits it. This is mainly concerned with the knowledge of design patterns. When AbstractList has implemented the List interface, it has achieved most of the required functionality. ArrayList only needs to complete some desired extensions. Reduce code duplication.
2. What's more strange is that. Why has AbstractList implemented the List interface? ArrayList has to implement the List interface again. According to the author of Array List, this was mainly caused by his own mistakes at that time, which was supposed to pave the way for future expansion of functions, but actually had no effect.

//Source code for AbstractList
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

• Random Access: Random Accss is actually an empty interface, just for identification purposes.

//Source code for Random Acces interface
public interface RandomAccess {
}

1. It mainly plays the role of identification. Random access is supported as long as this interface is implemented. We can look at the binary Search method in the Collections class, which determines whether List implements the Random Access method, and if so, use the indexed binarySearch (ordinary for loop traversal). If the Random Access interface is not implemented, iterator binarySearch is used.
2. If you are interested in it, you can check the source code of the two traversals further and test it. It will be found that ArrayList is more efficient to traverse with a normal for loop and LinkedList is more efficient to traverse with an iterator. Friends who want to know more about it can read this article: What role does the ArrayList collection play in implementing the Random Access interface? Why did the LinkedList collection not implement this interface?

#BiarySearch Method in Collections Class
public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    	#Determine whether Random Access is implemented
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

• Cloneable: Cloneable interface is implemented to achieve cloning
• Serializable: Serializable interface is implemented to implement serialization and deserialization

(3) Attributes

//Serialized version number
 private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initialization capacity
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * An empty array when the length of the ArrayList is set to zero
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
    * An empty array when the length of the ArrayList is not specified at initialization
    */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
    * transient Representation cannot be serialized. This array is used to save data
    */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList Actual array length in
     *
     * @serial
     */
    private int size;

1. DEFAULT_CAPACITY: The default initialization capacity is 10.
2. EMPTY_ELEMENTDATA: An empty array when the length of the ArrayList is set to zero.
3. DEFAULTCAPACITY_EMPTY_ELEMENTDATA: An empty array when the length of the ArrayList is not specified at initialization.
4. elementData: transient means that it cannot be serialized. This array is used to save data.
5. size: The actual length of the array.

(4) Construction method

   /**
     * A parameter constructor that specifies the initialization capacity
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        	//If the specified capacity is greater than 0, create an array of the specified length
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        	//If the specified capacity is 0, an empty array is created
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        	//If the specified capacity is less than 0, an exception is thrown
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * Parametric-free construction method, create an empty array, automatic initialization capacity of 10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * The method of constructing Collection as a parameter is mainly to realize the replication function.
     */
    public ArrayList(Collection<? extends E> c) {
    	//First, convert Collection to an array and assign values
        elementData = c.toArray();
        //Determine whether the length of the array is equal to 0
        if ((size = elementData.length) != 0) {
            // To determine whether it is an Object type, if not, is to convert
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // If the length equals 0, the assignment is an empty array
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

1. ArrayList(): A parametric constructor that creates an empty array with an automatic initialization capacity of 10
2. ArrayList (int initial capacity): A parameter constructor that specifies the initialization capacity
3. ArrayList (Collection <? Extends E > c): The method of constructing Collection as a parameter is mainly to realize the replication function.

(5) Add Method (Expansion Operation)

	/**
     * Add the element at the end of the ArrayList
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     * Add an element to the specified location
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    /**
    * Adding another Collection object to the current ArrayList
    */
     public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * At the specified location, add another Collection object to the current ArrayList
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

• The Add () method mainly involves the expansion operation, which involves many member methods, but the basic operation is roughly the same. It is easy to understand one method and the other three methods. Here we use the add(int index, E element) method to give an example.

1. Let's first look at the source code of add(int index, E element), the main function of which is to insert elements at specified locations.

	public void add(int index, E element) {
		//Check that the location to insert is legitimate
        rangeCheckForAdd(index);
		//Ensure that the array has enough capacity, and if not, expand it
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //Move all the elements from index+1 to the end one bit back
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //Insert elements at index position
        elementData[index] = element;
        //The actual capacity of ArrayList is increased by 1
        size++;
    }

1. We enter the range CheckForAdd (index) method. The implementation of the method is very simple. We can judge whether index is legal or not and throw an exception if it is not.

	/**
     * Check whether the insertion location is legal
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
        	//Throw an exception if the location is not valid
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

1. Then we go back to the add() method and go to the ensureCapacityInternal (size+1) method, because it inserts an element, so the minimum required capacity = the actual capacity size+1. After entering the method, the first step is to determine whether it is an empty array or not. If it is an empty array, the initialization capacity should be set to 10. Then call ensure ExplicitCapacity (minCapacity);

	/**
     * Determine whether it is an empty array, and if it is an empty array, set the initialization capacity to 10
     */
	private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        	//Determine whether it is an empty array, and if it is an empty array, set the initialization capacity to 10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
		//Call methods.
        ensureExplicitCapacity(minCapacity);
    }

1. Then we go into the ensureExplicitCapacity(int minCapacity) method. modCount needs to add 1 first. This property is in AbstractList. It is mainly used to record modification operations and identify fast-fail mechanism. It is interesting to know about it. Then it determines whether the minimum capacity is larger than the length of the current array, and if it is larger, calls the grow() method for expansion.

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

        // Determine whether the minimum capacity is larger than the length of the current array, and if it is larger, call the grow() method to expand it.
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

1. In the grow() method, the capacity of the original array is first assigned to oldCapacity. The old Capacity capacity is then expanded to 1.5 times the value assigned to the new Capacity. If the new Capacity is still less than the minimum capacity, the minimum capacity is assigned to the new Capacity. If newCapacity exceeds the maximum capacity of the array, the hugeCapacity() method is called for expansion. Finally, we use Arrays.copyOf(elementData, newCapacity) to create a new array and assign it to elementData to complete the expansion.

	private void grow(int minCapacity) {
        // Assign the capacity of the original array to oldCapacity
        int oldCapacity = elementData.length;
        //By shifting, the old Capacity capacity is expanded to 1.5 times and assigned to new Capacity.
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //If the new Capacity is still less than the minimum capacity, the minimum capacity is assigned to the new Capacity.
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //If newCapacity exceeds the maximum capacity of the array, the hugeCapacity() method is called to expand it.
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // Using Arrays.copyOf(elementData, newCapacity) to create a new array and assign it to elementData to complete the expansion
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

1. In the previous step, the hugeCapacity(minCapacity) method is called, which uses a ternary expression. If the minimum capacity is greater than the maximum array length, the maximum value of the integer is returned, otherwise the maximum length of the array is returned.

	private static int hugeCapacity(int minCapacity) {
		//Illegal scope
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //Using ternary expressions, if the minimum capacity is greater than the maximum array length, the maximum value of the integer is returned, otherwise the maximum length of the array is returned.    
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

(6) Remove method (delete element)

	/**
     * Delete elements at specified locations
     */
	public E remove(int index) {
		//First of all, judge whether the scope is legitimate.
        rangeCheck(index);
		//Number of modifications + 1, as mentioned earlier
        modCount++;
        //Get the old value at the index position
        E oldValue = elementData(index);
		//Calculate the number of elements that need to be moved to delete the location
        int numMoved = size - index - 1;
        if (numMoved > 0)
        	//Move all the elements behind index+1 forward by one bit
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //Set the value of size-1 to null to facilitate garbage collection
        elementData[--size] = null; // clear to let GC do its work
		//Returns deleted elements
        return oldValue;
    }
    /**
     * Delete the element of the specified object
     */
    public boolean remove(Object o) {
    	//If the object is a null object
        if (o == null) {
        	//foreach
            for (int index = 0; index < size; index++)
            	//If a value of null is found, the fastRemove() method is called to delete the element.
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
        	//foreach
            for (int index = 0; index < size; index++)
            	//If a value of o is found, the fastRemove() method is called to delete the element.
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        //Without this element, return false
        return false;
    }

• remove(int index) method: Delete elements at a specified location, as follows:

1. First of all, judge whether the scope is legitimate.
2. Number of modifications + 1, as mentioned earlier
3. Get the old value at the index position
4. Calculate the number of elements that need to be moved to delete the location
5. Move all the elements behind index+1 forward by one bit
6. Set the value of size-1 to null to facilitate garbage collection
7. Returns deleted elements

• remove(Object o) method: Delete elements at a specified location, as follows:

1. Judging whether an object is a null object
2. If null, traverse the array and delete it
3. If not null, traverse the array and delete it

	private void fastRemove(int index) {
		//Number of modifications + 1
        modCount++;
        //Calculate the number of moving elements
        int numMoved = size - index - 1;
        if (numMoved > 0)
        	//Move one bit forward
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //The last bit is null to facilitate garbage collection
        elementData[--size] = null; // clear to let GC do its work
    }

The fastRemove(int index) method is called in the deletion process. In fact, this method is to move all the elements after the index position forward by one bit to achieve element deletion.

(7) Serialization

There are two main serialization-related methods in ArrayList, readObject() and writeObject().

	private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

1. WritteObject () mainly completes the serialization operation.
2. The first step is to determine whether the expected ModCount is equal to the actual ModCount. If not, fast-fail occurs.
3. Write elements one by one into the output stream using the for loop

	private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

1. readObject() basically does deserialization
2. First of all, we should judge whether the actual capacity is greater than 0. If it is greater than 0, we should adjust the capacity and allocate space according to the actual size, not according to the capacity.
3. Write data from streams using for loops

(8) trimToSize() method

	/**
     * Reduce the capacity of ArrayList to its actual size
     */
    public void trimToSize() {
    	//Number of modifications + 1
        modCount++;
        //If the actual size is less than capacity
        if (size < elementData.length) {
        	//Condensation of ternary expressions
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

Because the number of elements in an ArrayList may not be equal to the capacity of an array, sometimes to save space, an ArrayList is scaled up, with the actual size = the capacity of the array.

(9) indexOf() method

	/**
	* Get the location of an element
	*/
	public int indexOf(Object o) {
		//If null
        if (o == null) {
        	//for loop traversal, return to that location if it exists
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
        	//Not null, for loop traversal, return to that location if it exists
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        //There is no Return-1
        return -1;
    }

    /**
     * Get the position of the specified element in reverse order
     */
    public int lastIndexOf(Object o) {
    	//If null
        if (o == null) {
        //for loop traversal, return to that location if it exists
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
        	//Not null, for loop traversal, return to that location if it exists
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        //There is no Return-1
        return -1;
    }

• indexOf() and lastIndexOf() respectively return the position of the specified elements in the positive and reverse order in the list. The implementation is relatively simple, and the code has detailed annotations, which is easy to understand.

(10) toArray() method

	/**
     * Call Arrays.copyOf(elementData, size) directly to return a new array
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * This is a type conversion method that converts an array to a specified type
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Returns a new array of type T
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        //Duplicate elements
        System.arraycopy(elementData, 0, a, 0, size);
        //Marking function
        if (a.length > size)
            a[size] = null;
        return a;
    }

• The toArray() method is mainly used to convert lists, and it is easy to implement. Detailed comments are included in the code.
• There are some pits in toArray(T[] a). This article can be seen in detail: toArray() and toArray(T[] a) methods of set rotation arrays

(11), batchRemove() method (batch deletion)

	/**
	* For bulk deletion
	*/
	private boolean batchRemove(Collection<?> c, boolean complement) {
		//Get the elements in the original array
        final Object[] elementData = this.elementData;
        //Set two pointers with an initial value of 0
        int r = 0, w = 0;
        //Set the flag value modified and the initial value false
        boolean modified = false;
        try {
        	//Delete operation
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            //If the deletion is complete and there is still something left, it is added to the original array.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            //If the length of the new array is less than that of the original array after deletion, null the latter value for garbage collection
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

1. BachRemove (Collection <?> c, Boolean complement) is used for batch deletion. When the complement parameter is true, it does not delete elements in C. If it is false, it deletes elements in C.
2. If the deletion is complete and there is still something left, it is added to the original array.
3. If the length of the new array is less than that of the original array after deletion, null the latter value for garbage collection

(12) Some other simple methods

	/**
     * Returns the actual size
     */
    public int size() {
        return size;
    }

    /**
     * Judge whether it is empty
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Determine whether the element is included
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
     /**
     * Cloning Method of Rewriting Object
     */
    public Object clone() {
        try {
        	//Calling the Cloning Method of the Parent Class
            ArrayList<?> v = (ArrayList<?>) super.clone();
            //Duplicate elements
            v.elementData = Arrays.copyOf(elementData, size);
            //mouCount Reset
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
    /**
     * Gets the element at the specified location
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    /**
     * Set the element value for the specified location
     */
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    /**
     * Clear ArrayList()
     */
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

1. size(): Returns the actual size
2. isEmpty(): Determine whether it is empty
3. contains(Object o): Determine whether or not this element is included
4. clone(): Cloning method for rewriting Object
5. get(int index): Gets the element at the specified location
6. set(int index, E element): Sets the element value of the specified location
7. clear(): Clear ArrayList()

(13), System.arraycopy() and Array. copyOf ()

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

• First, let's look at the System.arraycopy() method, which is labeled native. We can't see the source code, which means it's not implemented in the java language. The main function is that System.arraycopy() copies only the contents of the array and does not create new arrays.

	public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

• Then there's the Arrays.copyOf() method. We can see that he first creates a new Object array based on newLength, then calls System.arraycopy() again, copies it into the new array, and returns the new array.

(14) The role of the ModCount field

• The ModCount field is designed to prevent multiple threads from modifying the collection and causing errors in the process of using iterators in a multithreaded environment.
• The pit created by specific iterators can be seen in this article: Basic Implementation Principle and Pit of Enhanced for Loop in Java