ArrayList set is one of the most commonly used sets in daily development. It is a linear structure. Its bottom layer is implemented by array, which is equivalent to a dynamic array. Let's take a look at how some common methods of ArrayList are implemented.

ArrayList inheritance relationship

Interfaces and classes implemented by inheritance

• ArrayList inherits from AbstractList and implements List, RandomAccess, Cloneable and Java io. Serializable these interfaces.
• ArrayList inherits AbstractList and implements List. It is an array queue, which provides related functions such as adding, deleting, modifying and traversing.
• ArrayList implements RandmoAccess interface, which provides random access function. RandmoAccess is implemented by List in java to provide fast access for List. In ArrayList, we can quickly obtain the element object through the element serial number; This is fast random access.
• ArrayList implements the Cloneable interface and can call object The clone method returns a shallow copy of the object
• ArrayList implements Java io. Serializable interface, which means that ArrayList supports serialization and can be transmitted through serialization.

ArrayList class source code

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

Class diagram

Source code analysis

ArrayList property

The bottom layer of ArrayList is actually implemented by an array. It is an array with a default length of 10. When the storage elements reach the length of the array, ArrayList will expand the capacity of the array, that is, expand the capacity of the array. The capacity of the expanded array is 1.5 times that of the original array.

However, the array capacity will not be automatically reduced after the element is deleted. If it needs to be reduced, you can manually call the trimToSize() method

Note: ArrayList thread is unsafe. If it is multi-threaded, you can select Vector.

//serial number
private static final long serialVersionUID = 8683452581122892189L;

//Defines the length of the initialization set (array)
private static final int DEFAULT_CAPACITY = 10;

//Define an empty array and return it when the ArrayList element is empty
private static final Object[] EMPTY_ELEMENTDATA = {};

//Define an empty array, and ArrayList returns by default
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//The array containing elements cannot be serialized, and the content modified by transient cannot be serialized
transient Object[] elementData; // non-private to simplify nested class access

//The number of data stored in the array
private int size;

Construction method

There are three construction methods in the ArrayList source code, namely, the construction method with int type parameters, the construction method without parameters, and the collection <? Extensions E > type parameter constructor.

int type parameter construction method

The passed in parameter initialCapacity is the capacity of the initialization array.

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

If the parameter initialCapacity passed in is greater than 0, an empty array with an initial capacity of initialCapacity is created.

If the parameter passed in is equal to 0, the empty defined above will be_ An empty array of elementData is assigned to elementData.

When the passed in parameter is illegal (less than 0), an exception is thrown.

Nonparametric construction method

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

The parameterless construction method uses the above defined default attribute_ EMPTY_ An empty array of elementData is assigned to elementData.

The parameterless construction method initializes the array length to 0. After calling the add method for the first time, expand the array length to 10.

Collection<? Extensions E > type parameter construction method

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // Judge whether the array returned by c.toArray() is an Object type array
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // Empty array EMPTY_ELEMENTDATA is assigned to elementData
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

From the above inheritance diagram, you can know that a Collection is a Collection.

• Convert the parameter into an array and assign it to elementData
• Judge whether the length of the array is 0
• If it is not equal to 0, if the array returned by c.toArray() is not an array of Object type, use arrays The copyof() function is converted to an array of Object type and re assigned to elementData.
• If equal to 0, empty defined above_ An empty array of elementData is assigned to elementData.

trimToSize() method

As mentioned above, deleting elements in the ArrayList collection will not automatically reduce the capacity of the array, but we can reduce the capacity of the array by calling the trimToSize() method.

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

The trimToSize method first compares the length of the current array with the number of elements stored in the current array.

If the number of elements is less than the length of the current array, use arrays The copyof() function adjusts the capacity of the array elementData to reduce the capacity of the array.

size() method

When defining attributes, a size attribute is defined to store the number of data, so the size method returns the number of elements in the collection.

public int size() {
	return size;
}

isEmpty() method

isEmpty() method is used to judge whether the number of elements in the collection is equal to 0, that is, whether the collection is empty. If it is empty, return true; otherwise, return false.

public boolean isEmpty() {
  	return size == 0;
}

indexOf(Object o) method

The indexOf() method finds the location index of the element o in the collection and returns the location index found for the first time. If not found, - 1 is returned.

public int indexOf(Object o) {
	// Judge whether the parameter o is empty
   	if (o == null) {
   		//If it is empty, traverse the array to determine whether any element in the array is empty. If yes, return the subscript of the element
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
    	//If it is not empty, traverse the array, use equals to judge whether it is equal to o, and return the subscript of the equal element if it is equal
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    // If not found, - 1 is returned
    return -1;
}

First judge whether the searched element o is empty. If it is empty, traverse the array to judge whether there are empty elements in the array. If there are, return the subscript of the first empty element in the array.

If the lookup element o is not empty, traverse the array, use the equals keyword to compare whether the elements in the array are equal to element o, and return the subscript of the first equal element.

If not found, - 1 is returned.

lastIndexOf(Object o) method

The lastIndexOf() method, like the indexOf() method, looks for whether the element o exists in the collection.

The difference is that the lastIndexOf() method returns the last found location index. The indexOf() method returns the location index found for the first time.

public int lastIndexOf(Object o) {
	if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

As can be seen from the above code, the lastIndexOf() method starts from the last element of the array, and returns the subscript of the element after finding it. Therefore, the returned index is the location index of the last occurrence of the element in the array.

On the contrary, the indexOf() method starts from the first element of the array, so it returns the location index of the element for the first time in the array.

The time complexity of the lastIndexOf() and indexOf() methods is O(n).

get(int index) method

The get() method returns the element at the specified position in the collection.

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

    return elementData(index);
}

For the get() method, first use the rangeCheck() method to determine whether the passed index is out of bounds. If the passed index value is greater than the length of the array, an exception will be thrown.

The source code of rangeCheck() method is as follows:

private void rangeCheck(int index) {
  	if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

If there is no problem with the passed index value, the element corresponding to the index value in the array is returned.

set(int index, E element) method

The set() method modifies the element with index as the index position to element, and returns the element value before modification.

public E set(int index, E element) {
	//Judge whether the index is out of bounds
   	rangeCheck(index);
	
	//Save the value of index location
    E oldValue = elementData(index);
    //Modify the value of index position
    elementData[index] = element;
    //Returns the value before modification 	
    return oldValue;
}

Like the get method, the set() method calls the rangeCheck() method to determine whether the passed index is out of bounds.

Save the value of the index position first, then change the value of the index position to element, and finally return the element value before modifying the index position.

Add (E) method

The add() method adds an element to the end of the collection.

public boolean add(E e) {
	//Judge whether the array needs to be expanded
   	ensureCapacityInternal(size + 1);
   	//Adds the element e to the end of the array  
    elementData[size++] = e;
    //true is returned after adding successfully
    return true;
}

First call the ensureCapacityInternal() method to determine whether the array needs to be expanded. Because an element needs to be added, the parameter here is size+1. Then add the element at the end of the array, size the number of array contents + +.

Add elements. At the end of the array, the elements do not need to be moved, so the time complexity is O(n).

The source code of ensureCapacityInternal() method is as follows:

private void ensureCapacityInternal(int minCapacity) {
	//Determine whether the array is empty
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    	//Take the maximum value
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
	//Determine whether the array needs to be expanded
    ensureExplicitCapacity(minCapacity);
}

If the collection is empty, the array capacity takes the maximum value between the initial capacity and minCapacity.

The ensureExplicitCapacity() method determines whether the array needs to be expanded

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

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

If the length of the passed parameter minus the array is greater than 0, it needs to be expanded. The growth () method expands the array. The length of the expanded array is 1.5 times that of the original array.

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //1.5 times of the original capacity expansion
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //Assign the contents of the expanded array to the original array.
    elementData = Arrays.copyOf(elementData, newCapacity);
}

add(int index, E element) method

add(int index, E element) method to add an element to the index position.

public void add(int index, E element) {
  	rangeCheckForAdd(index);

	//Do you need to expand the array
    ensureCapacityInternal(size + 1);
    //The elements after the insertion position move back one position in turn
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //Insert element
    elementData[index] = element;
    size++;
}

After determining whether the array needs to be expanded, the system The arraycopy () method moves the elements after the insertion position back one position in turn, and then inserts the elements at the index position.

System. The arraycopy () method copies an array from the specified source array, starting at the specified location and ending at the specified location of the target array.

remove(int index) method

The remove(int index) method deletes the element at the specified index position and returns the deleted element value.

public E remove(int index) {
	//Judge whether the index is legal
  	rangeCheck(index);

    modCount++;
    //Save deleted element values
    E oldValue = elementData(index);

	//Number of array elements - 1
    int numMoved = size - index - 1;
    //If the number of elements in the collection after deletion > 0
    if (numMoved > 0)
    	//Move the elements after the index position forward one position in turn
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //Set the last element of the array to null, and the number of elements is - 1
    elementData[--size] = null; // clear to let GC do its work

	//Returns the value of the deleted element
    return oldValue;
}

Call the rangeCheck() method to judge whether the location index is legal.

If the number of elements in the collection after deletion is greater than 0, move the elements after the index position forward one position in turn.

Set the last element of the array to be empty, reduce the number of elements by one, and return the deleted element value.

remove(Object o) method

The remove(Object o) method deletes the specified element. If the specified element appears multiple times, only the first element will be deleted. true is returned if the deletion is successful.

public boolean remove(Object o) {
	//Judge whether the deleted element is empty
  	if (o == null) {
  		//If empty, find the subscript where the first element in the array is empty
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
            	//Delete the element with index
                fastRemove(index);
                return true;
            }
    } else {
    	//If it is not empty, find the index of the first element in the array equal to element o
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

The remove(Object o) method logic is similar to the indexof() method. fastRemove(index) method to delete the element with index as the subscript. The source code is as follows.

private void fastRemove(int index) {
  	modCount++;
    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
}

clear() method

clear() method to clear all elements in the collection.

public void clear() {
   	modCount++;

    // Traversal, set all elements in the collection to null
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

summary

• The bottom layer of ArrayList is implemented by array, which will be dynamically expanded. It is a linear structure.

• It is efficient to find and access elements based on subscripts.

• The add() method adds elements at the end of the array, so it is also very efficient.

• When inserting and deleting elements in the middle, the elements need to be moved, so the efficiency is relatively low.

• Thread unsafe.