LinkedList的局限

  java.util.linkedlist是雙向連結清單，這個大家都知道，比如java的基礎面試題喜歡問arraylist和linkedlist的差別，在什麼場景下用。大家都會說linkedlist随機增删多的場景比較合适，而arraylist的随機通路多的場景比較合适。更進一步，我有時候會問，linkedlist.remove(object)方法的時間複雜度是什麼？有的人回答對了，有的人回答錯了。回答錯的應該是沒有讀過源碼。

    理論上說，雙向連結清單的删除的時間複雜度是o(1)，你隻需要将要删除的節點的前節點和後節點相連，然後将要删除的節點的前節點和後節點置為null即可，

//僞代碼

node.prev.next=node.next;

node.next.prev=node.prev;

node.prev=node.next=null;

這個操作的時間複雜度可以認為是o(1)級别的。但是linkedlist的實作是一個通用的資料結構，是以沒有暴露内部的節點entry對象，remove(object)傳入的object其實是節點存儲的value，這裡還需要一個查找過程：

  public boolean remove(object o) {

        if (o==null) {

            for (entry<e> e = header.next; e != header; e = e.next) {

                if (e.element==null) {

                    remove(e);

                    return true;

                }

            }

        } else {

            //查找節點entry

                if (o.equals(e.element)) {

                    //删除節點

        }

        return false;

    }

    删除節點的操作就是剛才僞代碼描述的：

   private e remove(entry<e> e) {

        e result = e.element;

    e.previous.next = e.next;

    e.next.previous = e.previous;

        e.next = e.previous = null;

        e.element = null;

    size--;

    modcount++;

        return result;

    是以，顯然，linkedlist.remove(object)方法的時間複雜度是o(n)+o(1)，結果仍然是o(n)的時間複雜度,而非推測的o(1)複雜度。最壞情況下要删除的元素是最後一個，你都要比較n-1次才能找到要删除的元素。

    既然如此，說linkedlist适合随機删減有個前提，連結清單的大小不能太大，如果連結清單元素非常多，調用remove(object)去删除一個元素的效率肯定有影響，一個簡單測試，插入100萬資料，随機删除1000個元素：

        final list<integer> list = new linkedlist<integer>();

        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++){

            //這裡要強制轉型為integer，否則調用的是remove(int)

            list.remove((integer)rand.nextint(count));

        system.out.println((system.nanotime()-start)/math.pow(10, 9));

    在我的機器上耗時近9.5秒，删除1000個元素耗時9.5秒，是不是很恐怖？注意到上面的注釋，産生的随機數強制轉為integer對象，否則調用的是remove(int)方法，而非remove(object)。如果我們調用remove(int)根據索引來删除:

            list.remove(rand.nextint(list.size()-1));

    随機數範圍要遞減，防止數組越界，換成remove(int)效率提高不少，但是仍然需要2.2秒左右（包括了随機數産生開銷）。這是因為remove(int)的實作很有技巧，它首先判斷索引位置在連結清單的前半部分還是後半部分，如果是前半部分則從head往前查找，如果在後半部分，則從head往後查找（linkedlist的實作是一個環）：

        entry<e> e = header;

        if (index < (size >> 1)) {

            //前一半，往前找

            for (int i = 0; i <= index; i++)

                e = e.next;

            //後一半，往後找

            for (int i = size; i > index; i--)

                e = e.previous;

     最壞情況下要删除的節點在中點左右，查找的次數仍然達到n/2次，但是注意到這裡沒有比較的開銷，并且比remove(object)最壞情況下n次查找還是好很多。

    總結下，linkedlist的兩個remove方法，remove(object)和remove(int)的時間複雜度都是o(n)，在連結清單元素很多并且沒有索引可用的情況下，linkedlist也并不适合做随機增删元素。在對性能特别敏感的場景下，還是需要自己實作專用的雙向連結清單結構，真正實作o(1)級别的随機增删。更進一步，jdk5引入的concurrentlinkedqueue是一個非阻塞的線程安全的雙向隊列實作，同樣有本文提到的問題，有興趣可以測試一下在大量元素情況下的并發随機增删，效率跟自己實作的特定類型的線程安全的連結清單差距是驚人的。

    題外，arraylist比linkedlist更不适合随機增删的原因是多了一個數組移動的動作，假設你删除的元素在m，那麼除了要查找m次之外，還需要往前移動n-m-1個元素。

文章轉自莊周夢蝶  ，原文釋出時間 2010-09-16