LinkedList VS ArrayList

List，根據名字我們知道是有序的元素集合。先貼一張集合的關系圖。這裡我們分析LinkedList與ArrayList。

Collection結構

LinkedList與ArrayList

它們都實作了List接口。但是内部實作上有些差別，我們具體看下。

LinkedList以連結清單的方式實作

ArrayList内部以數組方式實作

插入操作

預設順序插入

按照預設順序插入，兩者耗費的時間都是O(1)。

// LinkedList add操作
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    // 建立一個節點。然後讓最後一個節點指向新加入的節點
    // 如果最後一個為空，那麼這是第一個新插入的節點
    // 否則，節點按連結清單方式接在後面
     void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        
        // 增加大小，增加修改次數
        size++;
        modCount++;
    }

           

// ArrayList插入
    public boolean add(E e) {
        // 確定數組的容量足夠。這個方法感興趣可以看一下。
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
           

指定index插入元素

ArrayList的最壞情況下性能為O(n)，最好情況下為O（1）

LinkedList在任何情況下都是O(1)

// LinkedList
   public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    // LinkedList節點的查找方法
        Node<E> node(int index) {
        // 不斷的周遊索引的位置。
        // 如果index 為小于size的一半，從頭周遊
        // index 大于size的一半，從尾部索引
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    
    // 直接修改要插入
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    
           

//ArrayList 。
    //需要調用 System.arraycopy 擴充數組，數組中的元素都往後挪一個位置，在底層實作上應該是進行了(n-index)次的指派操作。
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

           

删除操作

删除元素，與插入本質上是類似的，有興趣可以閱讀JDK内部實作方式。

ArrayList的删除操作最差情況下性能為O(n)，最好為O(1),删除最後一個元素的時候性能為O(1)

LinkedList删除任何元素的性能都為O(1)

搜尋元素

ArrayList的搜尋性能為O(1)

LinkedList的搜尋性能差一些，最差為O(n/2)

//LinkedList的搜尋
public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {
        // assert isElementIndex(index);
        // 需要進行連結清單的周遊
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

           

// ArrayList搜尋
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
    
    //直接從數組的下标拿到元素即可。
    E elementData(int index) {
        return (E) elementData[index];
    }

           

注意事項

LinkedList與ArrayList的源碼非常容易閱讀，沒什麼難度。這裡我們說一下它們的使用事項。

• LinkedList因為要同時維護鄰居節點的兩個指針，記憶體消耗大于ArrayList。
• 在頻繁的插入和删除的時候，可以考慮使用LinkedList
• 在頻繁的搜尋的時候，考慮使用ArrayList
• 它們都不是非線程安全的。

想要擷取線程安全的List

List list = Collections.synchronizedList(new ArrayList());
...
synchronized(list) {
      Iterator i = list.iterator(); // 必須在 synchronized 塊中
      while (i.hasNext())
          foo(i.next());
  }
           

最後

文中可能有描述不正确的地方，如果有的話歡迎指出。不過LinkedList與ArrayList是資料結構中很基礎的結構，JDK源碼讀起來也很簡單，可以試着讀一下。