为什么有人想要使用链表而不是数组?
毫无疑问，编码一个链表比使用数组要多一些工作，人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中这是一个主要的任务。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复，因为另一个问题是专门问一个特定的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中。
这就是为什么它们在函数式语言中如此受欢迎的原因，函数式语言使用不可变变量——前置和尾部操作可以自由发生，而无需复制原始数据——当您将数据视为不可变时，这是非常重要的特性。
其他回答
数组和链表之间的区别在于，数组是基于索引的数据结构，每个元素都与一个索引相关联，而链表是使用引用的数据结构，每个节点都被引用到另一个节点。在数组大小是固定的，而在链表大小是不固定的。
数组Vs链表:
由于内存碎片，阵列内存分配有时会失败。 在数组中缓存更好，因为所有元素都分配了连续的内存空间。 编码比数组更复杂。 与数组不同，在链表上没有大小限制 在链表中插入/删除更快，在数组中访问更快。 从多线程的角度来看，链表更好。
Arrays make sense where the exact number of items will be known, and where searching by index makes sense. For example, if I wanted to store the exact state of my video output at a given moment without compression I would probably use an array of size [1024][768]. This will provide me with exactly what I need, and a list would be much, much slower to get the value of a given pixel. In places where an array does not make sense there are generally better data types than a list to deal with data effectively.
Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。
首先，在c++中，使用链表应该不会比使用数组更麻烦。对于链表，可以使用std::list或boost指针列表。链表与数组的关键问题是指针需要额外的空间和糟糕的随机访问。你应该使用链表，如果你
你不需要随机访问数据 您将添加/删除元素，特别是列表中间的元素
