我的经验法则是，如果我需要一个集合（即不需要是一个列表），那么如果你事先知道大小，或者可以自信地知道大小，或知道它不会有太大变化，那么就使用ArrayList。如果您需要随机访问（即使用get（index）），请避免LinkedList。基本上，只有当您不需要索引访问并且不知道正在分配的集合的（近似）大小时，才使用LinkedList。此外，如果您要进行大量添加和删除（再次通过Collection接口），则LinkedList可能更可取。

1） 基础数据结构

ArrayList和LinkedList之间的第一个区别在于，ArrayList由Array支持，而LinkedList由LinkedList支持。这将导致性能的进一步差异。

2） LinkedList实现Deque

ArrayList和LinkedList之间的另一个区别是，除了List接口之外，LinkedList还实现了Deque接口，该接口为add（）和poll（）以及其他几个Deque函数提供先进先出操作。3） 在ArrayList中添加元素如果不触发Array的重新调整大小，则在ArrayList中添加元素是O（1）操作，在这种情况下，它变为O（log（n））。另一方面，在LinkedList中添加一个元素则是O（2）操作，因为它不需要任何导航。

4） 从位置移除元素

为了从特定索引中删除元素，例如通过调用remove（index），ArrayList执行复制操作，使其接近O（n），而LinkedList需要遍历到该点，这也使其成为O（n/2），因为它可以根据接近度从任意方向遍历。

5） 遍历ArrayList或LinkedList

迭代是LinkedList和ArrayList的O（n）操作，其中n是元素的数量。

6） 从位置检索元素

get（index）操作在ArrayList中为O（1），而在LinkedList中为其O（n/2），因为它需要遍历该条目。虽然，在大O符号中，O（n/2）只是O（n），因为我们忽略了那里的常数。

7） 内存

LinkedList使用一个包装对象Entry，这是一个静态嵌套类，用于存储数据和下一个和上一个节点，而ArrayList只在Array中存储数据。

因此，除了Array在将内容从一个Array复制到另一个Array时执行重新调整大小操作的情况外，ArrayList的内存需求似乎比LinkedList少。

如果Array足够大，那么此时可能会占用大量内存并触发垃圾收集，这会降低响应时间。

从ArrayList与LinkedList之间的所有差异来看，ArrayList在几乎所有情况下都是比LinkedList更好的选择，除非您经常执行add（）操作而不是remove（）或get（）操作。

修改链接列表比修改ArrayList更容易，尤其是当您从开始或结束处添加或删除元素时，因为链接列表内部保留了这些位置的引用，并且可以在O（1）时间内访问。

换句话说，您不需要遍历链接列表就可以到达要添加元素的位置，在这种情况下，添加就变成了O（n）操作。例如，在链接列表中间插入或删除元素。

在我看来，在Java中，使用ArrayList而不是LinkedList来实现大多数实际用途。

我应该何时使用LinkedList？大多数情况下使用堆栈时，或使用缓冲区时。我应该何时使用ArrayList？只有在使用索引时，否则您可以将HashTable与链接列表一起使用，那么您将得到：

哈希表+链接列表

通过密钥O（1）访问，通过键O（1）插入，通过键O（1）拆除在使用版本控制时，使用O（1）实现RemoveAll/SetAll有一个技巧

这似乎是一个很好的解决方案，在大多数情况下，你应该知道：HashTable占用了大量磁盘空间，所以当您需要管理1000000个元素列表时，它可能会变得很重要。这可能发生在服务器实现中，但在客户端中很少发生。

还可以看看红黑树

随机访问日志（n），插入日志（n），删除日志（n）

到目前为止，除了人们普遍认为LinkedList比ArrayList“多得多”之外，似乎没有人解决这些列表中每一个的内存占用问题，所以我做了一些数字处理，以证明这两个列表对于N个空引用所占的空间。

由于引用在其相对系统上是32位或64位（即使为空），因此我为32位和64位LinkedList和ArrayList包含了4组数据。

注意：ArrayList行显示的大小是用于修剪列表的-实际上，ArrayList中的后备数组的容量通常大于其当前元素计数。

注2：（感谢BeeOnRope）由于压缩Oops现在是默认值，从JDK6中期开始，以下64位机器的值将基本上与32位机器的对应值相匹配，当然，除非您特意关闭它。

结果清楚地表明，LinkedList比ArrayList多得多，尤其是元素数非常高的情况。如果内存是一个因素，请避开LinkedList。

我使用的公式如下，如果我做错了什么，请告诉我，我会改正的对于32位或64位系统，b’是4或8，而n’是元素的数量。注意mods的原因是因为java中的所有对象都将占用8字节的倍数空间，而不管是否全部使用。

阵列列表：

ArrayList对象头+大小整数+modCount整数+数组引用+（数组项目头+b*n）+MOD

链接列表：

LinkedList对象标头+大小整数+modCount整数+对标头的引用+对页脚的引用+（节点对象开销+对上一元素的引用+下一元素的参考+对元素的引用）*n）+MOD（节点对象，8）*n+MOD， 8)

对于ArrayList和LinkedList，remove（）和insert（）的运行时效率都为O（n）。然而，线性处理时间背后的原因来自两个非常不同的原因：

在ArrayList中，您可以找到O（1）中的元素，但实际上删除或插入某些元素会使其成为O（n），因为以下所有元素都需要更改。

在LinkedList中，实际到达所需元素需要O（n），因为我们必须从一开始就开始，直到达到所需的索引。实际上，移除或插入是常量，因为我们只需要为remove（）更改1个引用，为insert（）更改2个引用。

插入和删除这两项中的哪一项更快取决于发生的位置。如果我们更接近开始，LinkedList将更快，因为我们必须经过相对较少的元素。如果我们接近末尾，ArrayList将更快，因为我们在恒定的时间内到达那里，只需更改紧随其后的几个剩余元素。如果正好在中间完成，LinkedList将更快速，因为遍历n个元素比移动n个值更快。

好处：虽然无法为ArrayList创建这两个方法O（1），但实际上在LinkedList中有一种方法可以做到这一点。假设我们想在整个列表中删除和插入元素。通常，您可以使用LinkedList从头开始每个元素，我们也可以使用迭代器“保存”当前正在处理的元素。在迭代器的帮助下，当在LinkedList中工作时，remove（）和insert（）的效率为O（1）。使其成为我所知的唯一性能优势，LinkedList总是优于ArrayList。

这是一个效率问题。LinkedList添加和删除元素很快，但访问特定元素很慢。ArrayList访问特定元素的速度很快，但添加到两端的速度可能很慢，尤其是删除在中间的速度慢。

Array vs ArrayList vs LinkedList vs Vector更深入，同样如此链接列表。