为什么有人想要使用链表而不是数组?
毫无疑问，编码一个链表比使用数组要多一些工作，人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中这是一个主要的任务。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复，因为另一个问题是专门问一个特定的Java类，而这个问题是关于一般数据结构的。
当前回答
数组和链表之间的区别在于，数组是基于索引的数据结构，每个元素都与一个索引相关联，而链表是使用引用的数据结构，每个节点都被引用到另一个节点。在数组大小是固定的，而在链表大小是不固定的。
其他回答
当集合不断增加和减少时，链表尤其有用。例如，很难想象尝试使用数组实现一个Queue(添加到末尾，从前面删除)—您将花费所有时间向下移动内容。另一方面，对于链表来说，这是微不足道的。
链表比数组的维护开销更大，它还需要额外的内存存储，所有这些都是一致的。但是有一些事情是数组做不到的。在很多情况下，假设你想要一个长度为10^9的数组你无法得到它，因为必须有一个连续的内存位置。链表可能是这里的救世主。
假设你想用数据存储多个东西，那么它们可以很容易地扩展到链表中。
STL容器通常在后台有链表实现。
除了插入和删除方便之外，链表的内存表示方式也不同于数组。对于链表中的元素数量没有限制，而在数组中，您必须指定元素的总数。 看看这篇文章。
使用链表的唯一原因是插入元素很容易(删除也很容易)。
缺点可能是指针占用大量空间。
关于编码就更难了: 通常你不需要代码链表(或只需要一次)他们包括在内 STL 如果你还是要做的话，它就不那么复杂了。
另一个很好的原因是链表非常适合高效的多线程实现。这样做的原因是，更改往往是局部的——只影响数据结构局部部分的插入和删除的一两个指针。所以，你可以让多个线程在同一个链表上工作。更重要的是，可以使用cas类型的操作创建无锁版本，并完全避免沉重的锁。
使用链表，迭代器还可以在进行修改时遍历列表。在修改没有冲突的乐观情况下，迭代器可以在没有争用的情况下继续。
对于数组，任何修改数组大小的更改都可能需要锁定数组的很大一部分，事实上，这是在整个数组上没有全局锁的情况下完成的，因此修改会停止全局事务。
