转自：阿里中间件团队博客
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，这里还需要一个查找过程：
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
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 {
//查找节点Entry
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
//删除节点
unlink(x);
return true;
}
}
}
return false;
}
删除节点的操作就是刚才伪代码描述的：
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
因此，显然，LinkedList.remove(Object)方法的时间复杂度是O(n)+O(1)，结果仍然是O(n)的时间复杂度,而非推测的O(1)复杂度。最坏情况下要删除的元素是最后一个，你都要比较N-1次才能找到要删除的元素。
既然如此，说LinkedList适合随机删减有个前提，链表的大小不能太大，如果链表元素非常多，调用remove(Object)去删除一个元素的效率肯定有影响，一个简单测试，插入100万数据，随机删除1000个元素：
final List<Integer> list = new LinkedList<>();
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));
在我的机器上耗时2s左右，注意到上面的注释，产生的随机数强制转为Integer对象，否则调用的是 remove(int)方法，而非remove(Object)。如果我们调用remove(int)根据索引来删除:
for(int i=0;i<1000;i++){
list.remove(rand.nextInt(list.size()-1));
}
随机数范围要递减，防止数组越界，换成remove(int)效率提高不少，但是仍然需要1秒左右（包括了随机数产生开销）。这是因为 remove(int)的实现很有技巧，它首先判断索引位置在链表的前半部分还是后半部分，如果是前半部分则从head往前查找，如果在后半部分，则从 head往后查找（LinkedList的实现是一个环）：
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
//前一半，往前找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//后一半，往后找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
最坏情况下要删除的节点在中点左右，查找的次数仍然达到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个元素。
网友评论