LinkedList 底層分析

如圖所示 LinkedList 底層是基于雙向鏈表實(shí)現(xiàn)的，也是實(shí)現(xiàn)了 List 接口，所以也擁有 List 的一些特點(diǎn)(JDK1.7/8 之后取消了循環(huán)，修改為雙向鏈表)。

新增方法

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
     /**
     * Links e as last element.
     */
    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++;
    }

可見(jiàn)每次插入都是移動(dòng)指針，和 ArrayList 的拷貝數(shù)組來(lái)說(shuō)效率要高上不少。

查詢方法

    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;
        }
    }

上述代碼，利用了雙向鏈表的特性，如果index離鏈表頭比較近，就從節(jié)點(diǎn)頭部遍歷。否則就從節(jié)點(diǎn)尾部開(kāi)始遍歷。使用空間（雙向鏈表）來(lái)?yè)Q取時(shí)間。

• node()會(huì)以O(n/2)的性能去獲取一個(gè)結(jié)點(diǎn)
  • 如果索引值大于鏈表大小的一半，那么將從尾結(jié)點(diǎn)開(kāi)始遍歷

這樣的效率是非常低的，特別是當(dāng) index 越接近 size 的中間值時(shí)。

總結(jié)：

• LinkedList 插入，刪除都是移動(dòng)指針效率很高。

• 查找需要進(jìn)行遍歷查詢，效率較低。

  
  
  礦洞程序員.jpg