LinkedList陷阱

前几天看到一篇文章，里面特意提到了，读取频繁使用ArrayList，增删频繁使用Linkedlist；并且在一个范例中，特意将ArrayList转化为LinkedList以提高末尾插入的效率。而事实上，问题并非如此简单。

ArrayList与LinkedList的异同是我面试较常问的问题。大部分人可能都知道前者基于数组而后者基于链表（能答出双向链表自然更好），并且前者适合读取、后者适合插入删除；偶有候选人能曰“It depends”并给出具体情况之分析时，往往能获得不错的第一印象。

抛开具体语言的实现不说，先从数据结构上看一下，两者时间、空间负责度上的区别：



查找自不必说，插入删除与具体的位置有关，如果在首部、中部执行增删，考虑到ArrayList需要复制指定位置之后的所有元素，因此具有O(N)的时间复杂度；而LinkedList则只需O(1)。

如果是尾部增加、删除的情况，ArrayList不需要移动任何元素，因此两者的理论时间复杂度都为
O(1)。考虑得更细一点，如果是尾部增加的情况，LinkedList需要重新向JVM申请内存空间，而ArrayList不需要，因其一开始就会申请较多的空间，并且可以通过初始化capacity来避免动态膨胀的开销；如果是尾部减少的情况，LinkedList或许会带来GC释放内存的开销，而ArrayList仅需简单的将length减一；并且考虑到今后的扩展性，无论是哪种情况，使用ArrayList要划算得多。

另外，特别提一下删除操作，我前面特意强调“抛开具体语言不说”，是因为虽然理论上LinkedList的随机增删的时间复杂度是O(1)，但那是对于传入的是其内部某节点指针或者entry而言的，而事实上，在JAVA中由于不存在指针一说，并且对其数据结构的完美隐藏，大部分情况我们不会直接传入某个entry，而是基于以下两种情况的元素删除：

• 删除特定index的元素，对应LinkedList.remove(int)方法
• 删除特定值的元素，LinkedList.remove(Object)

事实上，对于上述情况，在删除前势必需要一个定位查找的工作，而众所周知，LinkedList在元素遍历上相当低效的，因此删除元素的时间复杂度应该是O(1) + O(N)，也就是O(N)。当然java进行了优化，譬如说采用折半查找索引的方式

Entry<E> e = header; 
if (index < (size >> 1)) { 
//looking forward
for (int i = 0; i <= index; i++) 
    e = e.next; 
} else { 
//looking backward
for (int i = size; i > index; i–) 
    e = e.previous; 
}

尽管如此，还是不敌ArrayList的O(1)。特别的，对于LinkedList.remove(int)方法来说，LinkedList定位慢而删除快，ArrayList定位快而删除慢，因此具体谁领风骚还真不好说，不仅与具体操作的位置有关，还与集合中元素的数量有关。

麻雀虽小五脏俱全，一个小小的LinkedList居然衍生出这么多的花样。以后对于LinkedList增删优于ArrayList一说，切不可一言以蔽之

评论

1 楼 NightBalance 2012-04-10  

领教了！谢谢分享