Java 8 ArrayList.add(int index, E element) 原始碼分析

本篇分析Java 8 java.util.ArrayList.add(int index, E element)的原始碼。

節錄原始碼如下。

java.util.ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    transient Object[] elementData; // non-private to simplify nested class access // 實際用來裝載元素的陣列空間
    
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity)); // 複製原elementData陣列並增加陣列長度
    }
    
    // (2)
    private Object[] grow() {
        return grow(size + 1); // 至少增加原長度加1
    }
    
    // (3)
    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; // 陣列原有長度
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 新長度 = 舊長度 + 舊長度/2 (shift bit operation)
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 若未新增過元素，則取新增長度或預設長度(10)的最大
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0) // 新的陣列長度不能超過最大陣列長度
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
    
    // (1)
    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }
    
    // (2)
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

ArrayList.add(int index, E element)插入元素到指定索引位置(1)，先呼叫rangeCheckForAdd()檢查指定的索引位置index是否超出範圍，若超出範圍丟出IndexOutOfBoundsException。

然後呼叫grow()(2)視陣列空間是否足夠來增加儲存元素的elementData陣列長度，若陣列長度不足預設新增%50的長度空間(3)。

接著把利用System.arraycopy()把elementData從index開始及之後的每個元素往後1個位置複製。這也是為什麼ArrayList插入或刪除時效能比LinkedList差的原因。

以一個元素長度為10且elementData滿載的情況來看，插入一個元素的陣列變化圖示如下。

  0   1   2   3   4   5   6   7   8   9
+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | f | g | h | i | j |  elementData = {a,b,c,d,e,f,g,h,i,j}
+---+---+---+---+---+---+---+---+---+---+


  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | f | g | h | i | j |   |   |   |   |   |  grow()
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+


  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e |   | f | g | h | i | j |   |   |   |   |  System.arraycopy(elementData, index,
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+                           elementData, index + 1,
                                                                                        s - index)

  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | X | f | g | h | i | j |   |   |   |   |  elementData[index] = element
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

• Java 8 ArrayList.add(E e) 原始碼分析
• Java 位元位移運算子