轉(zhuǎn)自：阿里中間件團(tuán)隊博客

java.util.LinkedList是雙向鏈表，這個大家都知道，比如Java的基礎(chǔ)面試題喜歡問ArrayList和LinkedList的區(qū)別，在什么場景下用。大家都會說LinkedList隨機(jī)增刪多的場景比較合適，而ArrayList的隨機(jī)訪問多的場景比較合適。更進(jìn)一步，我有時候會問，LinkedList.remove(Object)方法的時間復(fù)雜度是什么？有的人回答對了，有的人回答錯了。回答錯的應(yīng)該是沒有讀過源碼。

理論上說，雙向鏈表的刪除的時間復(fù)雜度是O(1)，你只需要將要刪除的節(jié)點的前節(jié)點和后節(jié)點相連，然后將要刪除的節(jié)點的前節(jié)點和后節(jié)點置為null即可，

//偽代碼
node.prev.next=node.next;
node.next.prev=node.prev;
node.prev=node.next=null;

這個操作的時間復(fù)雜度可以認(rèn)為是O(1)級別的。但是LinkedList的實現(xiàn)是一個通用的數(shù)據(jù)結(jié)構(gòu)，因此沒有暴露內(nèi)部的節(jié)點Entry對象，remove(Object)傳入的Object其實是節(jié)點存儲的value，這里還需要一個查找過程：

    /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            //查找節(jié)點Entry
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    //刪除節(jié)點
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

刪除節(jié)點的操作就是剛才偽代碼描述的：

    /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

因此，顯然，LinkedList.remove(Object)方法的時間復(fù)雜度是O(n)+O(1)，結(jié)果仍然是O(n)的時間復(fù)雜度,而非推測的O(1)復(fù)雜度。最壞情況下要刪除的元素是最后一個，你都要比較N-1次才能找到要刪除的元素。

既然如此，說LinkedList適合隨機(jī)刪減有個前提，鏈表的大小不能太大，如果鏈表元素非常多，調(diào)用remove(Object)去刪除一個元素的效率肯定有影響，一個簡單測試，插入100萬數(shù)據(jù)，隨機(jī)刪除1000個元素：

        final List<Integer> list = new LinkedList<>();
        final int count = 1000000;
        for (int i = 0; i < count; i++) {
            list.add(i);
        }
        final Random rand = new Random();
        long start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
        //這里要強(qiáng)制轉(zhuǎn)型為Integer，否則調(diào)用的是remove(int)
            list.remove((Integer) rand.nextInt(count));
        }
        System.out.println((System.nanoTime() - start) / Math.pow(10, 9));

在我的機(jī)器上耗時2s左右，注意到上面的注釋，產(chǎn)生的隨機(jī)數(shù)強(qiáng)制轉(zhuǎn)為Integer對象，否則調(diào)用的是 remove(int)方法，而非remove(Object)。如果我們調(diào)用remove(int)根據(jù)索引來刪除:

for(int i=0;i<1000;i++){
    list.remove(rand.nextInt(list.size()-1));
}

隨機(jī)數(shù)范圍要遞減，防止數(shù)組越界，換成remove(int)效率提高不少，但是仍然需要1秒左右（包括了隨機(jī)數(shù)產(chǎn)生開銷）。這是因為 remove(int)的實現(xiàn)很有技巧，它首先判斷索引位置在鏈表的前半部分還是后半部分，如果是前半部分則從head往前查找，如果在后半部分，則從 head往后查找（LinkedList的實現(xiàn)是一個環(huán)）：

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    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;
        }
    }

最壞情況下要刪除的節(jié)點在中點左右，查找的次數(shù)仍然達(dá)到n/2次，但是注意到這里沒有比較的開銷，并且比remove(Object)最壞情況下n次查找還是好很多。

總結(jié)下，LinkedList的兩個remove方法，remove(Object)和remove(int)的時間復(fù)雜度都是O(n)，在鏈表元素很多并且沒有索引可用的情況下，LinkedList也并不適合做隨機(jī)增刪元素。在對性能特別敏感的場景下，還是需要自己實現(xiàn)專用的雙向鏈表結(jié)構(gòu)，真正實現(xiàn) O(1)級別的隨機(jī)增刪。更進(jìn)一步，jdk5引入的ConcurrentLinkedQueue是一個非阻塞的線程安全的雙向隊列實現(xiàn)，同樣有本文提到的問題，有興趣可以測試一下在大量元素情況下的并發(fā)隨機(jī)增刪，效率跟自己實現(xiàn)的特定類型的線程安全的鏈表差距是驚人的。

題外，ArrayList比LinkedList更不適合隨機(jī)增刪的原因是多了一個數(shù)組移動的動作，假設(shè)你刪除的元素在m，那么除了要查找m次之外，還需要往前移動n-m-1個元素。