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

阵列列表与链接列表

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

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

2） 删除：LinkedList删除操作提供O（1）性能，而ArrayList提供可变性能：最坏情况下（删除第一个元素时）为O（n），最好情况下（移除最后一个元素时，为O（2）。

结论：LinkedList元素删除速度比阵列列表。

原因：LinkedList的每个元素都有两个指针（地址），指向列表中的两个相邻元素。因此，移除仅需要改变将要移除的节点的两个相邻节点（元素）中的指针位置。当在ArrayList中时，需要移动所有元素以填充移除的元素所创建的空间。

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

4） 内存开销：ArrayList维护索引和元素数据，而LinkedList维护相邻节点的元素数据和两个指针

因此LinkedList中的内存消耗相对较高。

这些类之间几乎没有相似之处，如下所示：

ArrayList和LinkedList都是List接口的实现。它们都保持元素插入顺序，这意味着在显示ArrayList和LinkedList元素时，结果集将具有元素插入列表的相同顺序。这两个类都是非同步的，可以使用Collections.synchronizedList方法显式同步。这些类返回的迭代器和listIterator是快速失败的（如果在创建迭代器之后的任何时候对列表进行结构修改，除了通过迭代器自己的remove或add方法之外，其他任何方式，迭代器都会抛出ConcurrentModificationException）。

何时使用LinkedList，何时使用ArrayList？

如上所述，与ArrayList（O（n））相比，插入和删除操作在LinkedList中提供了良好的性能（O（1））。因此，若应用程序中需要频繁添加和删除，则LinkedList是最佳选择。搜索（get方法）操作在Arraylist（O（1））中很快，但在LinkedList（O（n））中不快因此，如果添加和删除操作更少，搜索操作需求更多，ArrayList将是您的最佳选择。

ArrayList本质上是一个数组。LinkedList实现为双链接列表。

答案很清楚。O（1）表示ArrayList，因为ArrayList允许使用索引进行随机访问。O（n）表示LinkedList，因为它需要首先查找索引。注意：添加和删除有不同的版本。

LinkedList在添加和删除时速度更快，但在获取时速度较慢。简而言之，在以下情况下，应首选LinkedList：

元素没有大量的随机访问有大量的添加/删除操作

==阵列列表===

添加（E E）在ArrayList末尾添加需要内存大小调整成本。O（n）最差，O（1）摊销add（int索引，E元素）添加到特定索引位置需要移动和可能的内存调整成本O（n）删除（int索引）删除指定的元素需要移动和可能的内存调整成本O（n）删除（对象o）从此列表中删除第一个出现的指定元素需要先搜索元素，然后移动&可能的内存调整成本O（n）

==链接列表===

添加（E E）添加到列表末尾O（1）add（int索引，E元素）在指定位置插入需要先找到位置O（n）删除（）删除列表的第一个元素O（1）删除（int索引）删除具有指定索引的元素需要先找到元素O（n）删除（对象o）删除指定元素的第一个引用需要先找到元素O（n）

这是programcreek.com中的一个图（add和remove是第一种类型，即在列表末尾添加元素，然后在列表中的指定位置删除元素）：

Joshua Bloch，LinkedList的作者：

有人真的使用LinkedList吗？我写的，我从来没有用过。

链接：https://twitter.com/joshbloch/status/583813919019573248

很抱歉，我的答案没有其他答案那样信息丰富，但我认为这是最不言自明的答案。

是的，我知道，这是一个古老的问题，但我会投入我的两分钱：

LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList，但这些算法非常非常罕见，并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。

有一个常见的用例LinkedList优于ArrayList：队列。但是，如果您的目标是性能，那么您也应该考虑使用ArrayBlockingQueue（如果您可以提前确定队列大小的上限，并且能够提前分配所有内存），而不是LinkedList，或者使用CircularArray实现。（是的，它来自2001年，因此您需要对其进行一般化，但我得到的性能比与最近一篇JVM文章中引用的性能比相当）

您可以根据对该特定列表执行的操作的时间复杂性，使用一个而不是另一个。

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

算法：Big Oh符号（存档）

ArrayList适用于一次写入、多次读取或追加，但不适用于从前面或中间添加/删除。