一、ArrayList

ArrayList 實現 List、RandomAccess

ArrayList相當於動態數據，其中最重要的兩個屬性分別是: elementData 數組，以及 size 大小。 在調用

add() 方法的時候：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
 }

• 首先進行擴容校驗。
• 將插入的值放到尾部，並將 size + 1 。

如果是調用 add(index,e) 在指定位置添加的話：

public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  
        //複製，向後移動
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    }

• 也是首先擴容校驗。
• 接著對數據進行復制，目的是把 index 位置空出來放本次插入的數據，並將後面的數據向後移動一個位置。

其實擴容最終調用的代碼:

     private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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 的主要消耗是數組擴容以及在指定位置添加數據，在日常使用時最好是指定大小，儘量減少擴容。更要減少在指定位置插入數據的操作。

二、Vector

Vector 也是實現List 接口，底層數據結構和 ArrayList 類似,也是一個動態數組存放數據。不過是在 add() 方法的時候使用 synchronize

以下是 add() 方法：

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

以及指定位置插入數據:

    public void add(int index, E element) {
        insertElementAt(element, index);
    }
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }

三、LinkedList

如圖所示 LinkedList 底層是基於雙向鏈表實現的，也是實現了 List 接口，所以也擁有 List 的一些特點。

add新增方法

public boolean add(E e) {
        linkLast(e);
        return true;
    }
     /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

可見每次插入都是移動指針，和 ArrayList 的拷貝數組來說效率要高上不少。

get查詢方法

 public E get(int index) { 

        checkElementIndex(index);
        return node(index).item;
    }
    
    Node node(int index) {
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

由此可以看出是使用二分查找來看 index 離 size 中間距離來判斷，是從頭結點正序查還是從尾節點倒序查。

這樣的效率是非常低的，特別是當 index 距離 size 的中間位置越遠時。

總結：

• LinkedList 插入，刪除都是移動指針效率很高。
• 查找需要進行遍歷查詢，效率較低。

閱讀更多 nicky猿 的文章

關鍵字: 底層 數據結構 框架