java.util.LinkedList是雙向鏈表，這個大家都知道，比如Java的基礎(chǔ)面試題喜歡問ArrayList和LinkedList的區(qū)別，在什么場景下用。大家都會說LinkedList隨機增刪多的場景比較合適，而ArrayList的隨機訪問多的場景比較合適。更進一步，我有時候會問，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，這里還需要一個查找過程：
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 {
//查找節(jié)點Entry
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
//刪除節(jié)點
remove(e);
return true;
}
}
}
return false;
}
刪除節(jié)點的操作就是剛才偽代碼描述的：
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)方法的時間復(fù)雜度是O(n)+O(1)，結(jié)果仍然是O(n)的時間復(fù)雜度,而非推測的O(1)復(fù)雜度。最壞情況下要刪除的元素是最后一個，你都要比較N-1次才能找到要刪除的元素。
既然如此，說LinkedList適合隨機刪減有個前提，鏈表的大小不能太大，如果鏈表元素非常多，調(diào)用remove(Object)去刪除一個元素的效率肯定有影響，一個簡單測試，插入100萬數(shù)據(jù)，隨機刪除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++){
//這里要強制轉(zhuǎn)型為Integer，否則調(diào)用的是remove(int)
list.remove((Integer)rand.nextInt(count));
}
System.out.println((System.nanoTime()-start)/Math.pow(10, 9));
在我的機器上耗時近9.5秒，刪除1000個元素耗時9.5秒，是不是很恐怖？注意到上面的注釋，產(chǎn)生的隨機數(shù)強制轉(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));
}
隨機數(shù)范圍要遞減，防止數(shù)組越界，換成remove(int)效率提高不少，但是仍然需要2.2秒左右（包括了隨機數(shù)產(chǎn)生開銷）。這是因為remove(int)的實現(xiàn)很有技巧，它首先判斷索引位置在鏈表的前半部分還是后半部分，如果是前半部分則從head往前查找，如果在后半部分，則從head往后查找（LinkedList的實現(xiàn)是一個環(huán)）：
Entry<E> e = header;
if (index < (size >> 1)) {
//前一半，往前找
for (int i = 0; i <= index; i++)
e = e.next;
} else {
//后一半，往后找
for (int i = size; i > index; i--)
e = e.previous;
}
最壞情況下要刪除的節(jié)點在中點左右，查找的次數(shù)仍然達(dá)到n/2次，但是注意到這里沒有比較的開銷，并且比remove(Object)最壞情況下n次查找還是好很多。
總結(jié)下，LinkedList的兩個remove方法，remove(Object)和remove(int)的時間復(fù)雜度都是O(n)，在鏈表元素很多并且沒有索引可用的情況下，LinkedList也并不適合做隨機增刪元素。在對性能特別敏感的場景下，還是需要自己實現(xiàn)專用的雙向鏈表結(jié)構(gòu)，真正實現(xiàn)O(1)級別的隨機增刪。更進一步，jdk5引入的ConcurrentLinkedQueue是一個非阻塞的線程安全的雙向隊列實現(xiàn)，同樣有本文提到的問題，有興趣可以測試一下在大量元素情況下的并發(fā)隨機增刪，效率跟自己實現(xiàn)的特定類型的線程安全的鏈表差距是驚人的。
題外，ArrayList比LinkedList更不適合隨機增刪的原因是多了一個數(shù)組移動的動作，假設(shè)你刪除的元素在m，那么除了要查找m次之外，還需要往前移動n-m-1個元素。