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