为什么有人想要使用链表而不是数组?
毫无疑问，编码一个链表比使用数组要多一些工作，人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中这是一个主要的任务。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复，因为另一个问题是专门问一个特定的Java类，而这个问题是关于一般数据结构的。
当前回答
使用链接列表的人必须阅读。人们会再次爱上数组的。 它谈到了 无序执行，硬件预取，内存延迟等。
http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
其他回答
这实际上是一个效率问题，在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的，即操作本身是O(1)，而不是O(n)。如果您大量操作数据列表，这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型，并为所使用的算法选择最有效的数据类型。
除了插入到列表中间更容易之外——从链表中间删除也比从数组中删除容易得多。
但坦率地说，我从未使用过链表。每当我需要快速插入和删除时，我也需要快速查找，所以我使用HashSet或Dictionary。
两件事:
毫无疑问，编写链表比使用数组要多一些工作，他想知道如何才能证明这些额外的工作是合理的。
使用c++时不要编写链表。使用STL即可。实现的难度不应该成为选择一种数据结构而不是另一种数据结构的理由，因为大多数数据结构都已经实现了。
至于数组和链表之间的实际区别，对我来说最重要的是你计划如何使用这种结构。我将使用术语向量，因为这是c++中可调整大小的数组的术语。
对链表进行索引很慢，因为必须遍历链表才能找到给定的索引，而向量在内存中是连续的，可以使用指针数学方法到达那里。
添加到链表的末尾或开头是很容易的，因为你只需要更新一个链接，而在向量中，你可能需要调整大小并复制内容。
从列表中删除一个项目很容易，因为您只需要断开一对链接，然后将它们重新连接在一起。从向量中移除一个项目可以更快也可以更慢，这取决于您是否关心顺序。在你想要删除的项目上面交换最后一项更快，而移动它之后的所有内容较慢，但保持顺序。
链表是一个动态的数据结构，因此它可以在运行时通过分配和释放内存来增长和收缩。所以不需要给出链表的初始大小。插入和删除节点非常容易。
2-链表的大小可以在运行时增加或减少，因此没有内存浪费。在数组的情况下，有很多内存浪费，比如如果我们声明一个大小为10的数组，只存储6个元素，那么4个元素的空间就浪费了。链表中不存在这样的问题，因为只有在需要时才分配内存。
3-数据结构，如堆栈和队列可以很容易地实现使用链表。
这里有一个快速的方法:移除物品更快。
