【Java基礎】ArrayList工作原理

1. ArrayList

   以數組實現。節約空間，但數組有容量限制。超出限制時會增加50%容量，用System.arraycopy（）復制到新的數組。因此最好能給出數組大小的預估值。默認第一次插入元素時創建大小為10的數組。按數組下標訪問元素－get（i）、set（i,e）的性能很高，這是數組的基本優勢。如果按下標插入元素、刪除元素－add（i,e）、remove（i）、remove（e），則要用System.arraycopy（）來復制移動部分受影響的元素，性能就變差了。越是前面的元素，修改時要移動的元素越多。直接在數組末尾加入元素－常用的add（e），刪除最後一個元素則無影響。

   ArrayList是一個相對來說比較簡單的數據結構，最重要的一點就是它的自動擴容。

2. 構造方法

   ArrayList提供了三個構造方法：

   1. ArrayList(int initialCapacity)：指定容量
   2. ArrayList()：構造一個默認容量為10的ArrayList
   3. ArrayList(Collection<? extends E> c)：構造一個指定Collection的ArrayList

3. add

    // 添加指定元素到list末尾
    public boolean add(E e) {
        // 檢查是否需要擴容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 賦值
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 比較默認的容量10和傳入的容量，返回大點的數
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //擴容
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        // 記錄修改次數
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        // 記錄當前list的容量
        int oldCapacity = elementData.length;
        // 擴展為原來的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果擴展1.5倍還不能滿足，直接擴展為需求值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

也就是說，當增加數據的時候，如果ArrayList的大小已經不滿足需求時，那麼數組大小就會變為原來的1.5倍，之後就是把老的數據拷貝新的數組裡面。例如我創建的list的容量時10，當我們已經添加了10個元素的之後，再添加就會進行自動擴容到15。

1. get，set

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
    
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

get()和set()就比較簡單了，進行范圍檢查後就可以進行對應的操作了。由於ArrayList是動態數組，所以我們完全可以根據下標來獲取ArrayList中的元素，而且速度還比較快，故ArrayList長於隨機訪問。

1. remove

   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; // clear to let GC do its work
   
       return oldValue;
   }

   remove()首先進行范圍檢查，然後計算移動的開始位置，如果大於0的話就進行移動並返回舊值

參考文章：

1. http://yikun.github.io/2015/04/04/Java-ArrayList%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/