ArrayList和LinkedList都实现了List接口，它们的方法和结果几乎相同。然而，它们之间几乎没有差异，这取决于要求，使一个优于另一个。

　　ArrayList与LinkedList

　　1)搜索：与LinkedList搜索操作相比，ArrayList搜索操作非常快。ArrayList中的get(int index)给出O(1)的性能，而LinkedList性能为O(n)。

　　原因：ArrayList维护其元素的基于索引的系统，因为它隐式使用数组数据结构，这使得搜索列表中的元素更快。另一方面，LinkedList实现了双向链表，它需要遍历所有元素来搜索元素。

　　2)删除：LinkedList删除操作给出O(1)性能，而ArrayList提供可变性能：在最坏的情况下O(n)(删除第一个元素)和在最好的情况下O(1)(删除最后一个元素)。

　　结论：与ArrayList相比，LinkedList元素删除更快。

　　原因：LinkedList的每个元素都维护着两个指针(地址)，这些指针指向列表中的两个邻居元素。因此，移除仅需要改变将要移除的节点的两个相邻节点(元素)中的指针位置。在ArrayList中，需要移动所有元素以填充由要移除的元素创建的空间。

　　3)插入性能：LinkedList add方法给出O(1)性能，而ArrayList在最坏情况下给出O(n)。原因与删除说明相同。

　　4)内存开销：ArrayList维护索引和元素数据，而LinkedList维护元素数据和相邻节点的两个指针，因此LinkedList中的内存消耗比较高。

　　这些类之间的相似性很少，如下所示：

　　1. ArrayList和LinkedList都是List接口的实现。

　　2. 它们都维护元素的插入顺序，这意味着在显示ArrayList和LinkedList元素时，结果集将具有将元素插入List的相同顺序。

　　3. 这两个类都是非同步的，可以使用Collections.synchronizedList方法显式同步。

　　4. 这些类返回的迭代器和listIterator是快速失败的(如果在创建迭代器之后的任何时候对列表进行结构修改，除非通过迭代器自己的remove或add方法，迭代器将抛出 ConcurrentModificationException)。

　　何时使用LinkedList以及何时使用ArrayList?

　　1)如上所述，与 ArrayList(O(n))相比，insertList和remove操作在LinkedList中提供了良好的性能(O(1))。因此，如果在应用中需要频繁添加和删除，则LinkedList是最佳选择。

　　2)搜索(get方法)操作在Arraylist(O(1))中很快但在LinkedList(O(n)中)没有，因此如果添加和删除操作较少且搜索操作要求较多，则ArrayList将是您最好的选择。

上一篇

Java GC都用了哪些算法？分别应用在什么地方？

下一篇

equals和== 的区别是什么