为什么有人想要使用链表而不是数组?
毫无疑问，编码一个链表比使用数组要多一些工作，人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中这是一个主要的任务。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复，因为另一个问题是专门问一个特定的Java类，而这个问题是关于一般数据结构的。
当前回答
首先，在c++中，使用链表应该不会比使用数组更麻烦。对于链表，可以使用std::list或boost指针列表。链表与数组的关键问题是指针需要额外的空间和糟糕的随机访问。你应该使用链表，如果你
你不需要随机访问数据 您将添加/删除元素，特别是列表中间的元素
其他回答
两件事:
毫无疑问，编写链表比使用数组要多一些工作，他想知道如何才能证明这些额外的工作是合理的。
使用c++时不要编写链表。使用STL即可。实现的难度不应该成为选择一种数据结构而不是另一种数据结构的理由，因为大多数数据结构都已经实现了。
至于数组和链表之间的实际区别，对我来说最重要的是你计划如何使用这种结构。我将使用术语向量，因为这是c++中可调整大小的数组的术语。
对链表进行索引很慢，因为必须遍历链表才能找到给定的索引，而向量在内存中是连续的，可以使用指针数学方法到达那里。
添加到链表的末尾或开头是很容易的，因为你只需要更新一个链接，而在向量中，你可能需要调整大小并复制内容。
从列表中删除一个项目很容易，因为您只需要断开一对链接，然后将它们重新连接在一起。从向量中移除一个项目可以更快也可以更慢，这取决于您是否关心顺序。在你想要删除的项目上面交换最后一项更快，而移动它之后的所有内容较慢，但保持顺序。
没有人再编写自己的链表了。那太愚蠢了。使用链表需要更多代码的前提是错误的。
如今，构建链表只是学生们的一个练习，以便他们能够理解这个概念。相反，每个人都使用预先构建的列表。在c++中，根据我们问题中的描述，这可能意味着stl向量(#include <vector>)。
因此，选择链表还是数组完全是权衡每个结构相对于应用程序需求的不同特征。克服额外的编程负担应该对决策没有任何影响。
合并两个链表(特别是两个双链表)比合并两个数组快得多(假设合并是破坏性的)。前者取O(1)，后者取O(n)。
编辑:澄清一下，我在这里指的是无序意义上的“合并”，而不是归并排序。也许"串联"这个词更合适。
Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。
链表是一个动态的数据结构，因此它可以在运行时通过分配和释放内存来增长和收缩。所以不需要给出链表的初始大小。插入和删除节点非常容易。
2-链表的大小可以在运行时增加或减少，因此没有内存浪费。在数组的情况下，有很多内存浪费，比如如果我们声明一个大小为10的数组，只存储6个元素，那么4个元素的空间就浪费了。链表中不存在这样的问题，因为只有在需要时才分配内存。
3-数据结构，如堆栈和队列可以很容易地实现使用链表。
