ArrayList

ArrayList is a dynamic Array, which is a complex version of Array. It provides dynamic methods for adding and deleting elements. It also implements the Collection and List interfaces, and can set the size of an Array flexibly.

Through source code analysis, we can see that an ArrayList can be constructed in three ways

The empty constructor creates an array of specified length based on the value passed in, which is generated by passing in the list of Collection elements

Private static final int DEFAULT_CAPACITY = 10; Private static Final Object[] EMPTY_ELEMENTDATA = {}; [] elementData transient Object[] elementData; Private int size; private int size; /** * empty constructor */ publicArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; Public ArrayList(int initialCapacity) {// if the initialCapacity is greater than 0, an exception will be thrownif(initialCapacity > 0) {// Create an array of size initialCapacity this.elementData = new Object[initialCapacity]; }else if(initialCapacity == 0) {// Create an empty array this.elementData = EMPTY_ELEMENTDATA; }else{// If the value is negative, throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} /** * Constructs a list of specified collection elements that return sequentially using the iterators of the collection. Throws NullPointerException if the specified collection is NULL. */ 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

ArrayList related questions

ArrayList pros and cons

The advantages of ArrayList are that the underlying implementation of ArrayList is an array, a random-access mode, and that it implements the RandomAccess interface, making it fast to execute get methods.

An ArrayList is very verbose when adding elements sequentially, just adding one element to the array, traversing the elements by index, which is very efficient. You can automatically expand capacity by 1.5 times by default

disadvantages

Inserting and removing elements from an array (except at the end) is inefficient because a large number of elements need to be moved

When the ArrayList is smaller than the capacity to be expanded, the efficiency of adding is very high. When the capacity to be expanded is involved, the efficiency of adding is really low, and the copy to be deleted needs to be shifted.

At the same time, adding (expanding) or deleting elements in the ArrayList requires the inefficient method of system.arrayCopy (). Therefore, the efficiency is relatively low when the amount of data is slightly large or the operation of frequent insertion and deletion is required. You need to use LinkedList instead because the beauty of an ArrayList is that once you’ve constructed an array, it’s very efficient to access the elements frequently.

Difference between an ArrayList and a Vector

First, the List interface has three implementation classes: ArrayList, Vector, and LinkedList

Vector, like ArrayList, is implemented using arrays. The difference is that Vector supports thread synchronization. That is, only one thread can write a Vector at a time. But implementing synchronization requires a high level of Synchronized, so Vector is slower than ArrayList

At the same time, the capacity expansion mechanism of Vector is different from that of ArrayList. The capacity expansion mechanism of Vector is twice the length of array, while that of ArrayList is 1.5 times the length of the original array.

Expansion mechanism

The add method

Let’s start by looking at how the add method in an ArrayList adds elements. Okay

Public Boolean add(E E) {// Call ensureCapacityInternal(size + 1) before adding an element; // Increments modCount!! ElementData [size++] = e; elementData[size++] = e;return true;
}
Copy the code

EnsureCapacityInternal method

When an element is added, minCapacity is 1, and the maximum value of both elements is taken

Private void ensureCapacityInternal(int minCapacity) {// When the initial list is empty by defaultif(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// Get the default capacity and the maximum value of the passed parameter // DEFAULT_CAPACITY: 10, minCapacity: 1 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }Copy the code

EnsureExplicitCapacity method

As you can see, the ensureExplicitCapacity method is called after the above operation, which is mainly used to determine whether the capacity expansion is triggered

Private void ensureExplicitCapacity(int minCapacity) {modCount++; // overflow-conscious codeif(minCapacity -elementdata. length > 0) }Copy the code

Turns method

When an element is added that is larger than the current array, the grow operation is triggered, which expands the array

int newCapacity = oldCapacity + (oldCapacity >> 1)
Copy the code

The core code is the above sentence, expand the original array length to 1.5 times, and then execute the copy command, copy the contents of the old array to the new array, to achieve the expansion operation.

elementData = Arrays.copyOf(elementData, newCapacity);
Copy the code

The complete code is as follows

Private static final int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; private static final int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; Private void grow(int minCapacity) {oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); newCapacity = oldCapacity + (oldCapacity >> 1); // If the new capacity is smaller than the capacity of the added collection, the capacity is replacedif(newCapacity - minCapacity < 0) newCapacity = minCapacity; /** If the new capacity is greater than MAX_ARRAY_SIZE, enter the 'hugeCapacity()' method to compare minCapacity with * MAX_ARRAY_SIZE. If minCapacity is greater than the maximum capacity, The new capacity is' integer.max_value '; otherwise, * the new capacity is MAX_ARRAY_SIZE, which is' integer.max_value - 8 '. * /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); } /** If the new capacity is greater than MAX_ARRAY_SIZE, enter the 'hugeCapacity()' method to compare minCapacity with * MAX_ARRAY_SIZE. If minCapacity is greater than the maximum capacity, The new capacity is' integer.max_value '; otherwise, * the new capacity is MAX_ARRAY_SIZE, which is' integer.max_value - 8 '. */ private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
Copy the code

conclusion

By combing the above methods, we can conclude the following points

When we add the first element to the ArrayList, elementData.length is 0. MinCapacity = 10; minCapacity = elementData.length = 0; minCapacity = elementData.length = 0; minCapacity = elementData.length = 0; minCapacity = elementData.length = 0; So it goes into the grow(minCapacity) method

Elementdata.length () : minCapacity = 2; elementdata.length () : elementdata.length () : elementData.length = 0; So the grow(minCapacity) method is not entered.

Meanwhile we continue to add elements 3,4…. 11. By element 11, minCapacity(11) is larger than 10, which triggers the grow operation