Java 集合 ArrayList和LinkedList的区别

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将是您最好的选择。