java - 如何选择正确的 List 实现？

Question

来自 this CodeReview answer ,

You seem to use ArrayList for all purposes. There are other List-types in Java that suit certain situations better than an ArrayList. You should have a look at those and try to get a feeling when to use which list. In this particular case i.E. a LinkedList is better.

我也倾向于大量使用 ArrayList，看不到选择其他列表类型背后的逻辑。

List docs显示五个主要的 List 子类:ArrayList , CopyOnWriteArrayList , LinkedList , Stack , 和 Vector .

来自 ArrayList 文档，

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

这表明 ArrayList 通常会优于 LinkedList(this heavily upvoted question 支持的断言)，尽管 LinkedList 文档没有给出性能的好主意:

All of the operations perform as could be expected for a doubly-linked list.

CopyOnWriteArrayList 似乎只对不变的列表有用，因为每次修改的完整快照对于正常使用来说似乎贵得离谱。

即使是 Stack 文档也不推荐使用它:

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

由于 Vector 是同步的而其余的 List 子类不是，所以在我看来 Vector 将是最好的选择一个线程安全的环境。

然而，即使通读了文档，我仍然不明白 TwoThe 的答案从何而来。 CopyOnWriteArrayList 和 Vector 似乎都有一个专门的用例，Stack 似乎不值得使用，而 ArrayList似乎优于 LinkedList。

我在这里缺少什么，在什么情况下另一个 List 实现会优于 ArrayList？

Answer 1

我同意 ArrayList 是许多用途的正确选择。 LinkedList 为指针使用每个元素 8 或 16 字节的内存，正如您所说，索引是 O(length)。

LinkedLists 的优点是什么？

• 在迭代期间用remove() 删除是常量时间。对于 ArrayList，它是 O(length)。
• 添加一个新的列表节点总是需要相同的时间。当 ArrayList 空间不足时，会在后台分配更大的内存块，并复制所有内容。虽然每个元素的许多操作的摊销时间是恒定的，但单个 add() 的成本是 O(length)。如果不能接受这种周期性延迟，则不能使用 ArrayList。

至于其他，Vector 可以追溯到 Java 的早期。它是线程安全的。因为这会增加每个操作的成本，所以它的使用或多或少被弃用了，取而代之的是 ArrayList。当您需要线程安全时，您可以使用 SynchronizedList 包装 ArrayList。类似地，Stack 或多或少被弃用，取而代之的是更现代且非线程安全的 Deque。

CopyOnWriteArrayList 是一个线程安全的数据列表，它通过在任何元素发生变化时复制完整数组这一有点不寻常的措施来确保其安全性。虽然这听起来很疯狂，但如果有许多线程在同一个数组上迭代是有意义的，因为更改不必等待所有迭代完成，而其他并发列表通常是这种情况。