Detailed source code explanation of common methods of ArrayList

I believe that almost all students will be asked about the similarities and differences between ArrayList and LinkedList during written tests and interviews. Those who are slightly prepared are already familiar with these problems. The former is based on array implementation, and the latter is based on linked list implementation; the former's random method is fast, while deleting and inserting at specified positions is slow, while the latter's random access is slow, and deleting and inserting at specified positions is fast; Both are thread-unsafe; differences between lists vs arrays and more.

One of the big differences between lists and arrays is that arrays need to be sized during initialization and cannot be dynamically expanded, while lists can be dynamically expanded. ArrayList is implemented based on arrays, so how does it achieve dynamic expansion?
There are three ways to initialize ArrayList:
For the first default construction method, ArrayList does not initialize the capacity, but points the element data reference of the list to an empty array.

private transient Object[] elementData;private static final Object[] EMPTY_ELEMENTDATA = {};

//1.ArrayList默认构造方法public ArrayList() {    super();this.elementData = EMPTY_ELEMENTDATA;
}

Different from JDK1.6, JDK1.6 will initialize the capacity even when calling the default constructor. JDK1.7 Of course, it will bring certain benefits. If it is initialized and not used, the storage space will be wasted. Just wait until it is added and then initialize the capacity.

//JDK1.6 ArrayListpublic ArrayList() {this(10);
}

For the second construction method, directly create an array of the specified size and point the element array reference of the list to it.

//2.ArrayList带有初始化大小的构造方法public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+   initialCapacity);this.elementData = new Object[initialCapacity];
}

The third construction method can pass a collection as a parameter, but the elements in the collection must inherit from the elements in the ArrayList.

//3.可将一个集合作为ArrayList的参数构造成ArrayListpublic ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();    //将集合转换为数组size = elementData.length;    //集合中的元素大小// c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug，参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

A bug was mentioned above, which means that when converting a collection into an array, Object[] may not be returned by mistake. Here is an example.

 1 package com.algorithm.sort; 2  3 import java.util.ArrayList; 4 import java.util.Arrays; 5 import java.util.List; 6  7 /** 8  * bug编号:6260652。toArray有可能不会返回Object[] 9  * Created by yulinfeng on 2017/6/26.10  */11 public class Test {12     public static void main(String[] args) {13         correctly();14         incorrectly();15     }16     17     /**18      * 返回Object[]19      */20     private static void correctly() {21         List<String> list = new ArrayList<String>();22         list.add("test");23         System.out.println(list.getClass());24         Object[] objArray = list.toArray();25         System.out.println(objArray.getClass());26     }27     /**28      * 不返回Object[]29      */30     private static void incorrectly() {31         List<String> list = Arrays.asList("test");32         System.out.println(list.getClass());33         Object[] objArray = list.toArray();34         System.out.println(objArray.getClass());35     }36 }

Running result:

The above example illustrates that toArray does not always return Object[]. Object[], the Object element cannot be inserted, so the JDK fixed this bug in "6260652".

Next, let’s look at other methods such as element insertion and deletion.

//ArrayList#addpublic boolean add(E e) {
    ensureCapacityInternal(size + 1);  //确保容量是否充足elementData[size++] = e;    //将元素添加至数组return true;
}

//ArrayList#ensureCapacityInternalprivate void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);     //如果此时还没有初始化列表容量大小，则对其初始化，默认容量为10    }
    ensureExplicitCapacity(minCapacity); //检查容量是否充足}

//ArrayList#ensureEcplicitCapacityprivate void ensureExplicitCapacity(int minCapacity) {
    modCount++;    //注意此变量if (minCapacity - elementData.length > 0)
        grow(minCapacity);    //容量不够则进行扩容}

In the ensureEcplicitCapacity method, there is a modCount (modify count) variable that is incremented.

protected transient int modCount = 0;

This variable will not only increment in the add method, but will be recorded and incremented by 1 whenever there is a change to the ArrayList structure such as addition or deletion. The reason for this is the same as in multi-threading. Iterator is related to iterator traversal. There is also a variable corresponding to it in AbstractList$Itr.

//AbstractList$Itrint expectedModCount = modCount;

The checkForComodification method is called in AbstractList$Itr#next.

//AbstractList$Itr#checkForComodificationfinal void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

If the current running environment is single-threaded, no matter what operations are performed on the list, such as adding, modifying, deleting, etc., unexpectedModCount will always be equal to modCount, but if the current running environment is With multi-threading, it is very likely that one thread is iterating while another thread is adding or modifying it. JDK does not allow this. In this case, a ConcurrentModificationException will be thrown. This is where the modCount variable comes from. effect.
Return to the ArrayList#add method. When the list capacity is insufficient, the grow method will be called to expand the capacity.

//ArrayList#growprivate void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);    //扩容策略为，每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10，则第一次扩容大小为10 / 2 = 5，第二次扩容大小为15 / 2 = 7。if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;    //扩容策略扩得太小if (newCapacity - MAX_ARRAY_SIZE > 0)    //扩容策略扩得太大，大于最大数组大小时，最多等于Integer.MAX_VALUEnewCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList gets the element get method at the specified index position.

public E get(int index) {
    rangeCheck(index);    //检查索引是否越界return elementData(index);
}

Since ArrayList is implemented based on arrays, this method is relatively simple. Just judge whether it is out of bounds. If not, just index and return the elements according to the array subscript. The remove method deletes the element at the specified position.​

//ArrayList#removepublic E remove(int index) {
    rangeCheck(index);    //检查索引是否越界modCount++;    //记录modCount，上面已提及E oldValue = elementData(index);    //取出指定索引元素int numMoved = size - index - 1;    //移动的元素个数if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //将最后一个数组元素置为null，方便GCreturn oldValue;
}

The code is relatively simple, and it also reflects the efficiency problem of ArrayList based on array practice when deleting specified elements. For information about the Arrays.copyOf and System.arraycopy methods, please refer to "The Difference between System.arraycopy(src, srcPos, dest, destPos, length) and Arrays.copyOf(original, newLength)"

The above is the detailed content of Detailed source code explanation of common methods of ArrayList. For more information, please follow other related articles on the PHP Chinese website!