arrays - 数组与链表

Question

为什么有人想要使用链表而不是数组？

毫无疑问，对链表进行编码比使用数组要多一些工作，人们可能想知道什么可以证明额外的工作是合理的。

我认为在链表中插入新元素是微不足道的，但在数组中却是一项主要工作。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗？

此问题与 this question 不重复因为另一个问题是专门询问特定的 Java 类，而这个问题涉及一般数据结构。

Answer 1

另一个很好的理由是链表非常适合高效的多线程实现。其原因是更改往往是本地的 - 仅影响在数据结构的本地部分插入和删除的一两个指针。因此，您可以让许多线程在同一个链表上工作。更重要的是，可以使用 CAS 类型的操作创建无锁版本，并完全避免重量级锁。

使用链表，迭代器还可以在发生修改时遍历列表。在修改不发生冲突的乐观情况下，迭代器可以继续而不会发生争用。

对于数组，任何修改数组大小的更改都可能需要锁定数组的大部分，事实上，在没有跨整个数组的全局锁的情况下很少会这样做，因此修改会停止世界事务。