数组与链表
为什么有人想要在数组上使用链表呢？
毫无疑问，编写链表比使用数组要多一点的工作，人们可能想知道什么可以证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中却是一件很重要的事情。与将数据存储在数组中相比，使用链表存储一组数据是否还有其他优势？
这个问题不是this question的重复，因为另一个问题是问一个特定的Java类，而这个问题是关于一般数据结构的。
回答 22
Stack Overflow用户
发布于 2008-10-03 13:59:08
另一个很好的原因是链表非常适合高效的多线程实现。这样做的原因是更改往往是局部的-只影响数据结构的本地化部分的插入和删除的一两个指针。因此，您可以让多个线程在同一链表上工作。更重要的是，可以使用CAS类型的操作创建无锁版本，并完全避免重量级锁。
使用链表，迭代器还可以在修改发生时遍历列表。在乐观的情况下，修改不会发生冲突，迭代器可以继续执行，而不会发生争用。
对于数组，任何修改数组大小的更改都可能需要锁定数组的很大一部分，事实上，这很少在整个数组中没有全局锁的情况下完成，因此修改成为停止世界事务。
Stack Overflow用户
发布于 2008-10-03 15:33:48
我将添加另一个-列表可以作为purely functional数据结构。
例如，您可以让完全不同的列表共享相同的结束部分
a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)即：
b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next 而不必将a指向的数据复制到b和c中。
这就是为什么它们在使用不可变变量的函数式语言中如此流行- prepend和tail操作可以自由发生，而不必复制原始数据-当您将数据视为不可变时，这是非常重要的特性。
Stack Overflow用户
发布于 2008-10-03 13:39:11
除了插入到列表的中间更容易-从链表的中间删除也比从数组中删除容易得多。
但坦率地说，我从来没有使用过链表。每当我需要快速插入和删除时，我也需要快速查找，所以我去找HashSet或字典。
https://stackoverflow.com/questions/166884
复制相似问题