LinkedList特性

LinkedList沒什么好說的，在存放大量數(shù)據(jù)時尤其有用，其插入花費的操作次數(shù)僅僅為1，而對比arraylist的插入，花費的操作次數(shù)通過aggregate method算出為2，快兩倍。

Java中的LinkedList

雙向鏈表，因為內(nèi)部維護的Node就是雙向，而開頭寫的tail加head更是直接提醒

缺陷在哪

雙向鏈表的一個重要性質(zhì)就是如果傳入的是鏈表中element的指針，那么刪除的復(fù)雜度則為O(1)，但可惜的是java的remove(object)是通過遍歷，然后判斷equals進行刪除，所以復(fù)雜度為O(n)，翻看完oracle文檔里的說明，并沒發(fā)現(xiàn)合適的方法可以達到O(1)，全部都是遍歷，并沒有Node指針的接口。最典型的remove:

 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 {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

其實現(xiàn)過程也是相當(dāng)簡單，當(dāng)然，這里的unlink符合O(1)的要求，但也僅僅只是用來刪除節(jié)點而已。而外部暴露的接口并沒有O(1)復(fù)雜度的接口

需不需要自己實現(xiàn)一個O(1)

不需要，linkedhashmap就是彌補這個的