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

哈希表+链接列表

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

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

还可以看看红黑树

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

见原始答案下方作者的2021更新。

原答案（2011年）

作为一个在非常大规模的SOA web服务上做了大约十年操作性能工程的人，我更喜欢LinkedList而不是ArrayList的行为。虽然LinkedList的稳态吞吐量更差，因此可能会导致购买更多硬件，但ArrayList在压力下的行为可能会导致集群中的应用程序以近乎同步的方式扩展其阵列，而对于较大的阵列大小，可能会导致应用程序缺乏响应能力，在压力下停机，这是灾难性的行为。

类似地，您可以从默认的吞吐量固定垃圾收集器中获得更好的应用吞吐量，但一旦您获得了具有10GB堆的java应用程序，您就可以在完全GC期间锁定应用程序25秒，这会导致SOA应用程序超时和失败，如果太频繁，还会破坏SLA。尽管CMS收集器占用了更多的资源，并且没有实现相同的原始吞吐量，但它是一个更好的选择，因为它具有更可预测性和更小的延迟。

如果您所指的性能是吞吐量，并且可以忽略延迟，那么ArrayList只是性能的更好选择。根据我的工作经验，我不能忽视最坏情况下的延迟。

更新（2021 8月27日——10年后）

这个答案（也是我在SO问题上最受欢迎的答案）很可能是错误的（原因在下面的评论中概述）。我想补充一点，ArrayList将优化内存的顺序读取，并最小化缓存线和TLB未命中等。相比之下，当阵列增长超过边界时的复制开销可能无关紧要（可以通过高效的CPU操作完成）。考虑到硬件趋势，随着时间的推移，这个答案可能会变得更糟。LinkedList可能有意义的唯一情况是，如果您有数千个列表，其中任何一个都可能增长到GB大小，但在分配列表时无法做出正确的猜测，并且将它们全部设置为GB大小，则会炸毁堆。如果你发现了这样的问题，那么无论你的解决方案是什么，都需要重新设计（我不想轻率地建议重新设计旧代码，因为我自己维护了一堆又一堆的旧代码，但这是一个很好的例子，因为原始设计已经过时，确实需要扔掉）。尽管如此，我还是会把我几十年来的糟糕观点留在那里，让你读一读。简单、合乎逻辑，而且非常错误。

ArrayList中的get（i）操作比LinkedList更快，因为：ArrayList：List接口的可调整大小的数组实现LinkedList：list和Deque接口的双重链接列表实现

索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引的为准。

首先使用Vector而不是ArrayList，因为您可以覆盖insuranceCapasity方法，在ArrayList中是私有的，并添加1.5大小的当前数组https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html#ensureCapacity-整数-

在很多情况下，linkedList会更好，las有一个很大的优势：你可以高频插入数据，所以列表的大小变化很快，你不能为数字元素分配大小。从理论上讲，你可能会遇到“内存不足”之类的错误，但在现代计算机中，你有16G和交换磁盘，所以如果你列出的是billoins元素，与15-20年前相比，你可能失败。

对于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。

ArrayList是您想要的。LinkedList几乎总是一个（性能）bug。

为什么LinkedList很糟糕：

它使用了大量小内存对象，因此影响了整个过程的性能。许多小对象不利于缓存位置。任何索引操作都需要遍历，即具有O（n）性能。这在源代码中并不明显，导致算法O（n）比使用ArrayList时慢。获得好的表现是很棘手的。即使big-O性能与ArrayList相同，它也可能会明显变慢。在源代码中看到LinkedList很刺耳，因为它可能是错误的选择。