Detailed analysis of Java collection framework ArrayList source code (picture)

Overall introduction

ArrayList implements the List interface, which is a sequential container where elements are stored The data is in the same order as it is put in. null elements are allowed to be put in. The bottom layer implements through the array. Except that this class does not implement synchronization, the rest is roughly the same as Vector. Each ArrayList has a capacity (capacity), which represents the actual size of the underlying array. The number of elements stored in the container cannot exceed the current capacity. When elements are added to the container, the container automatically increases the size of the underlying array if there is insufficient capacity. As mentioned before, Java generics are just syntax sugar provided by the compiler, so the array here is an Object array to be able to accommodate any type of object.

size(), isEmpty(), get(), and set() methods can all be completed in constant time. The time cost of the add() method is related to the insertion position. , the time cost of the addAll() method is proportional to the number of elements added. Most of the other methods are linear time.

In order to pursue efficiency, ArrayList is not synchronized. If concurrent access by multiple threads is required, users can synchronize manually or use Vector instead.

Method analysis

set()

Since the bottom layer is an arrayArrayListset()method also becomes It's very simple, just assign a value directly to the specified position in the array.

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
    return oldValue;
}

get()

get()The method is also very simple. The only thing to note is that since the underlying array is Object[], you need to ## after getting the elements. #Type conversion.

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

add()

is different from C++’s

vector, ArrayList does not have a bush_back() method, the corresponding method It is add(E e), ArrayList does not have the insert() method, the corresponding method is add(int index, E e). Both methods add new elements to the container, which may result in insufficient capacity. Therefore, before adding elements, the remaining space needs to be checked and automatically expanded if necessary. The expansion operation is finally completed through the grow() method.

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的3倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}

Since Java GC automatically manages memory, there is no need to consider the issue of source array release here.

After the space problem is solved, the insertion process becomes very simple.

add(int index, E e)You need to move the element first, and then complete the insertion operation, which means that this method has a linear time complexity.

addAll()

addAll()The method can add multiple elements at one time. There are two handles depending on the position, one is added at the end addAll(Collection extends<a href="http://www.php.cn/wiki/166.html" target="_blank"> E> c)</a> method, one is the addAll(int index, Collection extends E> c) method that inserts from the specified position. Similar to the add() method, space check is also required before inserting, and the capacity will be automatically expanded if necessary; if inserted from a specified position, elements may also be moved. The time complexity of
addAll() is not only related to the number of inserted elements, but also to the insertion position.

remove()

remove()The method also has two versions, one is remove(int index)Deletes the element at the specified position, and the other One is remove(Object o)Remove the first element that satisfies o.equals(elementData[index]). The deletion operation is the reverse process of the add() operation, which requires moving the element after the deletion point forward one position. It should be noted that in order for GC to work, the last position must be explicitly assigned a null value.

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //清除该位置的引用，让GC起作用
    return oldValue;
}

The above is the detailed content of Detailed analysis of Java collection framework ArrayList source code (picture). For more information, please follow other related articles on the PHP Chinese website!