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
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
//刪除節點
remove(e);
return true;
}
}
}
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)根據索引來刪除:
for(int i=0;i<1000;i++){
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;
} else {
//后一半，往后找
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個元素。