In this chapter, we’ll take a quick look at ArrayList. If you have any questions, please contact me at [email protected]. Ask for directions of various gods, thank you

Introduction to ArrayList

An ArrayList is based on an array. It is a dynamic array that grows automatically. Since ArrayList is not thread-safe, it can only be used under a single thread;

Two: Application scenario of ArrayList

Because an ArrayList is implemented based on an array, it has the properties of an array: it automatically numbers the stored elements (subscripts). So we can easily get each element by its number

Three: Ask questions

The length of an array is immutable, so if an ArrayList is implemented based on an array, why can an ArrayList add and remove elements?

Four: into the source code

4.1: Inheritance of ArrayList

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

ArrayList implements the Serializable interface, so it supports serialization; Implementation of RandomAccess interface, support for fast RandomAccess, is actually through the subscript serial number for fast access; Cloneable interface, can be cloned.

4.2: Some constants in an ArrayList

/** * serial version */ private static Final Long serialVersionUID = 8683452581122892189UID; /** * Default array size */ private static final int DEFAULT_CAPACITY = 10; */ private static Final Object[] EMPTY_ELEMENTDATA = {}; / / EMPTY_ELEMENTDATA = {}; /** * init is used when the size is not set. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * transient Object[] elementData; /** * Private int size;Copy the code

4.3: Three constructors of ArrayList

/** * When we use the no-argument constructor, we create an array of length 0 */ publicArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * ArrayList with capacity size constructor. Public ArrayList(int initialCapacity) {EMPTY_ELEMENTDATA */ 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(Collection<? extends E> c) { elementData = c.toArray();if((size = elementData.length) ! Arrays.copyof () {arrays.copyof () {arrays.copyof ();if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else{ this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

4.4: Common methods

The method is to reduce the size of elementData, remove the excess array space. Applications use this operation to reduce the amount of storage that an ArrayList instance takes up because some operations, such as empty, only change the parameters but do not free space. Public voidtrimToSize() {
	modCount++;
	if(size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }} The function returns the position of the first occurrence of a given element in the set. If not, it returns -1. If not null, equals is used to check for equality. This is because calling equals directly on null throws a null-pointer exception. It is also impossible to loop over the elements of an array and call equals to check for equality, since null elements are allowed in the ArrayList collection. public int indexOf(Object o) {if (o == null) {
		for (int i = 0; i < size; i++)
			if (elementData[i]==null)
				return i;
	} else {
		for (int i = 0; i < size; i++)
			if (o.equals(elementData[i]))
				return i;
	}
	return- 1; Public Boolean contains(Object o) {public Boolean contains(Object o) {returnindexOf(o) >= 0; } returns the last position of a given element, or -1 if not: same principle as indexOf, except that set elements are traversed in reverse order. 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; } private void rangeCheck(int index) {if (index >= size)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}


@SuppressWarnings("unchecked")
E elementData(int index) {
	return(E) elementData[index]; } For the get method, first call rangeCheck to check the subscript and then call elementData to return the element: public E get(int index) {rangeCheck(index);returnelementData(index); } sets the element at the given position to the given element, and then returns the original element. public Eset(int index, E element) {
	rangeCheck(index);

	E oldValue = elementData(index);
	elementData[index] = element;
	returnoldValue; } the key!!!!! Public Boolean add(E E) {ensureCapacityInternal(size + 1); elementData[size++] = e;return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) {// If the default capacity is not set at initializationif(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// Returns the default capacity (10) and the maximum value of the specified capacityreturnMath.max(DEFAULT_CAPACITY, minCapacity); } otherwise return the current length +1returnminCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; AbstractList, the parent of ArrayList, is used to store structure changesif(minCapacity - elementData.length > 0) grow(minCapacity); } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; Private void grow(int minCapacity) {// oldCapacity = elementData.length; // The new capacity is increased to 1.5 times the original capacity, where >> is the 'bit operator'. int newCapacity = oldCapacity + (oldCapacity >> 1); // If the calculated capacity is too small, the specified capacity is assigned to itif (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); elementData = array.copy (elementData, newCapacity); } // The length is set to integer. max_value-8 to avoid running out of memory. Integer.MAX_VALUE private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
		throw new OutOfMemoryError();
	return(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } public E remove(int index) {rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1;if(numMoved > 0) arrayCopy (elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear tolet GC do its work

	returnoldValue; } C/C++ code with native flag for Java call system, the function actually finally called the MEMmove () function of C language, so it can ensure the correct copy and move of elements in the same array, much higher than the implementation efficiency of the general copy method, very suitable for batch array processing. Java strongly recommends using this method when copying a large number of array elements for greater efficiency. public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);Copy the code

Five:

ArrayList is realized by array. It can directly find the element in the specified position through the subscript index, so the search efficiency is high. The principle of adding elements is that objects are recreated each time they are added, and the original data is copied. Frequent adding and deleting operations consume a lot of memory, so ArrayList is suitable for finding elements