C++中的动态数组与链表比较

Question

为什么我们需要链表而不是动态数组列表？

我学过静态列表和链表，并且了解动态数组列表。但我无法找到它们之间的确切区别。请有人帮我回答这个问题。

- Aadnan Farooq A

Answer 1

动态数组是一种根据内容数量自行调整大小的数组。

优点：

- 通过索引访问和赋值非常快，O(1)的过程，因为内部索引访问只是"[第一个成员的地址] + [偏移量]"。 - 添加对象（插入到数组末尾）相对较快，平摊O(1)。与从数组末尾删除对象具有相同的性能特征。注意：在数组末尾附近添加和删除对象也称为推送和弹出。 - 在动态数组中随机位置插入或删除对象非常慢，O(n/2)，因为每次必须移动（平均）一半的数组。特别是在数组开始附近插入和删除时，它必须复制整个数组。 - 插入或删除需要调整大小时，性能不可预测。 - 有一些未使用的空间，因为动态数组实现通常分配比必要多的内存（因为调整大小是一项非常缓慢的操作）。

链表是一个具有一般结构"[头，[尾]]"的对象，其中"头"是数据，"尾"是另一个链表。有许多版本的链表：单链表、双链表、循环链表等。

优点：

- 在列表中任何位置快速插入和删除，O(1)，因为在链表中插入只是打破列表、插入和修复它（不需要复制尾部）。 - 链表是一种持久的数据结构，很难用简短的句子解释，参见：wiki-link。这个优点允许两个链接列表之间进行"尾共享"。尾部共享使得使用链表作为写时复制数据结构变得容易。

缺点：

- 随机访问速度慢，O(n)，因为通过索引访问链表意味着必须递归地遍历整个列表。 - 空间利用率较低，链表使用的内存散布在混乱的位置。相比之下，数组使用连续的内存地址。数组（稍微）受益于处理器缓存，因为它们都靠近彼此。 其他：

- 由于链表的性质，您必须递归地思考。不习惯递归函数的程序员可能在编写链表算法时遇到一些困难（或者更糟糕的是，他们可能会尝试使用索引）。

简而言之，当您想要使用需要随机访问的算法时，请忘记链表。当您想要使用需要大量插入和删除的算法时，请忘记数组。

这是从问题的最佳答案中摘取的。

我被这个答案所说服。

- Shafi

---

我不同意作者的观点。他误用了大O符号（不存在O（n/2）），将O（n）称为“非常慢”（我只会将“非常”用于超线性复杂度），声称数组的局部性优势“轻微”（它们是如此巨大，以至于即使在插入几百个廉价复制元素时，在数组中开始插入也更快），并对链表进行了一般性的断言，认为它们是持久的（单向链表可以是持久的，但标准的forward_list不是，而双向链表永远不可能是持久的）。他还声称，你必须用递归思考链表。 - Sebastian Redl

从 $O$ 的定义来看，$O(n/2)$ 没有问题。只是 $O(n) = O(n/2)$，通常我们更喜欢说 $O(n)$。 - Manuel Lafond

只是补充一下，如果你的数据都能够放在内存中，那么数组对于大量插入操作非常好用——插入的平均时间复杂度为O(1)。 - Ravi R

Answer 2

向量（Vector）又称动态数组：与普通数组类似，连续的内存位置用于存储向量。每当需要分配更多内存时，并且当前位置没有可用的内存，整个数组将被复制到另一个位置，并分配额外的内存。

列表（List）：在每个元素中维护一个指针，该指针指向下一个元素。

标准容器的复杂度保证是什么？请查看此链接以获取更多信息。

- aaroh