为什么有人想要使用链表而不是数组?
毫无疑问，编码一个链表比使用数组要多一些工作，人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中这是一个主要的任务。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复，因为另一个问题是专门问一个特定的Java类，而这个问题是关于一般数据结构的。
当前回答
我也认为链表比数组更好。 因为我们在链表中做遍历，而不是在数组中
其他回答
我将添加另一个-列表可以充当纯函数式数据结构。
例如，您可以让完全不同的列表共享相同的结束部分
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中。
这就是为什么它们在函数式语言中如此受欢迎的原因，函数式语言使用不可变变量——前置和尾部操作可以自由发生，而无需复制原始数据——当您将数据视为不可变时，这是非常重要的特性。
另一个很好的原因是链表非常适合高效的多线程实现。这样做的原因是，更改往往是局部的——只影响数据结构局部部分的插入和删除的一两个指针。所以，你可以让多个线程在同一个链表上工作。更重要的是，可以使用cas类型的操作创建无锁版本，并完全避免沉重的锁。
使用链表，迭代器还可以在进行修改时遍历列表。在修改没有冲突的乐观情况下，迭代器可以在没有争用的情况下继续。
对于数组，任何修改数组大小的更改都可能需要锁定数组的很大一部分，事实上，这是在整个数组上没有全局锁的情况下完成的，因此修改会停止全局事务。
我也认为链表比数组更好。 因为我们在链表中做遍历，而不是在数组中
It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size. As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow. Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory. As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.
两件事:
毫无疑问，编写链表比使用数组要多一些工作，他想知道如何才能证明这些额外的工作是合理的。
使用c++时不要编写链表。使用STL即可。实现的难度不应该成为选择一种数据结构而不是另一种数据结构的理由，因为大多数数据结构都已经实现了。
至于数组和链表之间的实际区别，对我来说最重要的是你计划如何使用这种结构。我将使用术语向量，因为这是c++中可调整大小的数组的术语。
对链表进行索引很慢，因为必须遍历链表才能找到给定的索引，而向量在内存中是连续的，可以使用指针数学方法到达那里。
添加到链表的末尾或开头是很容易的，因为你只需要更新一个链接，而在向量中，你可能需要调整大小并复制内容。
从列表中删除一个项目很容易，因为您只需要断开一对链接，然后将它们重新连接在一起。从向量中移除一个项目可以更快也可以更慢，这取决于您是否关心顺序。在你想要删除的项目上面交换最后一项更快，而移动它之后的所有内容较慢，但保持顺序。
