为什么有人想要使用链表而不是数组?
毫无疑问，编码一个链表比使用数组要多一些工作，人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中这是一个主要的任务。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复，因为另一个问题是专门问一个特定的Java类，而这个问题是关于一般数据结构的。
当前回答
Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。
其他回答
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.
两件事:
毫无疑问，编写链表比使用数组要多一些工作，他想知道如何才能证明这些额外的工作是合理的。
使用c++时不要编写链表。使用STL即可。实现的难度不应该成为选择一种数据结构而不是另一种数据结构的理由，因为大多数数据结构都已经实现了。
至于数组和链表之间的实际区别，对我来说最重要的是你计划如何使用这种结构。我将使用术语向量，因为这是c++中可调整大小的数组的术语。
对链表进行索引很慢，因为必须遍历链表才能找到给定的索引，而向量在内存中是连续的，可以使用指针数学方法到达那里。
添加到链表的末尾或开头是很容易的，因为你只需要更新一个链接，而在向量中，你可能需要调整大小并复制内容。
从列表中删除一个项目很容易，因为您只需要断开一对链接，然后将它们重新连接在一起。从向量中移除一个项目可以更快也可以更慢，这取决于您是否关心顺序。在你想要删除的项目上面交换最后一项更快，而移动它之后的所有内容较慢，但保持顺序。
对我来说是这样的，
Access Linked Lists allow only sequential access to elements. Thus the algorithmic complexities is order of O(n) Arrays allow random access to its elements and thus the complexity is order of O(1) Storage Linked lists require an extra storage for references. This makes them impractical for lists of small data items such as characters or boolean values. Arrays do not need an extra storage to point to next data item. Each element can be accessed via indexes. Size The size of Linked lists are dynamic by nature. The size of array is restricted to declaration. Insertion/Deletion Elements can be inserted and deleted in linked lists indefinitely. Insertion/Deletion of values in arrays are very expensive. It requires memory reallocation.
我将添加另一个-列表可以充当纯函数式数据结构。
例如，您可以让完全不同的列表共享相同的结束部分
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中。
这就是为什么它们在函数式语言中如此受欢迎的原因，函数式语言使用不可变变量——前置和尾部操作可以自由发生，而无需复制原始数据——当您将数据视为不可变时，这是非常重要的特性。
我也认为链表比数组更好。 因为我们在链表中做遍历，而不是在数组中
