链表 vs 向量

Question

在过去的几天里，我一直在为我的第一次软件开发工作电话面试做准备。在研究问题时，我找到了这篇文章。

一切都很顺利，直到我看到了这段话:

“何时使用链表而不是向量？”

从经验和研究来看，这两种数据结构非常不同，链表是动态数组，而向量是空间中的二维点。我唯一能看出两者之间的关系是，如果将向量用作链表，例如myVector（我的值，指向邻居的指针） 你有什么想法？

- Ryan

---

错误的向量类型，请查看http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html。 - RussS

https://www.youtube.com/watch?v=YQs6IC-vgmo&t=99s - Sudip Bhandari

Answer 1

Vector是动态数组的另一个名称。在C++中，它是用于动态数组数据结构的名称。如果您有Java经验，您可能会用ArrayList来称呼它们。(Java还有一个旧的集合类叫做Vector，由于设计问题现在不再使用。)

向量适用于随机读取访问和后部插入和删除(摊销常数时间)，但前部或其他位置的插入和删除效率较低(线性时间，因为需要移动项目)。向量通常在内存中连续布局，因此遍历向量效率高，CPU内存缓存得到有效利用。

链表另一方面适用于在前面或后面插入和删除项（常数时间），但不特别适用于其他操作：例如，在列表中间的任意索引处删除项需要线性时间，因为您必须先找到节点。另一方面，一旦找到特定节点，您可以在常数时间内删除它或在其后插入新项，这是使用向量无法完成的。链表也非常简单易于实现，因此成为一种流行的数据结构。

- Joni

---

向量允许在O(n)时间内在中间进行插入和删除，就像链表一样。算法移动插入/删除位置后面的元素，使其为O(n)。 - Joni

链表非常适合在中间进行插入和删除操作。在链表中插入元素的时间复杂度为O(1)。此外，链表保证了当其他数据被插入或移除时，数据地址不会发生改变。 - rabensky

在链表的中间插入或删除一个元素需要先迭代整个链表，以找到插入或删除的位置。正是这种迭代使算法的时间复杂度为O(n)；如果已经找到了要插入/删除的元素，则时间复杂度当然为O(1)。 - Joni

@joni，你错了。记住列表的迭代器并不意味着它是“不是列表的其他东西”。它仍然是一个列表，我只是有一个保存迭代器的变量。在链表中查找第n个元素需要O(n)的时间，但插入只需要O(1)的时间。插入之前不必进行“查找”，因为您可以通过其他方法（如记住要从哪里插入）选择要插入的位置。无论如何 - 无论您称其为什么，这是您可以使用链表而无法使用向量完成的操作。 - rabensky

@joni所说的是，你需要把这个内容放在“链表优于向量的优势”中，对吧？因为这是链表相对于向量的一个优势。 - rabensky

Answer 2

我知道这个提问者有些晚了，但这是一段非常有深度的视频，由C++发明人Bjarne Stroustrup讲述现代硬件中为什么应该避免使用链表。 https://www.youtube.com/watch?v=YQs6IC-vgmo 在如今计算机上快速内存分配的情况下，使用向量创建更新项目副本的速度要快得多。

- Jonathan Roberts

---

嗨，乔纳森，当在回答中引用链接时，请尝试包括一个用户可能通过跟随链接找到的摘要。请记住，链接可能会失效。为了未来的可持续性，请将你的回答做好准备。【回答】 - Dan Beaulieu

我真的不认为这个视频对比列表和向量类型是公平的。谬误在于比较了两者在随机生成的索引处删除单个元素时的效率。一个更有趣的比较是比较删除随机选择的成员的效率。我想知道需要从列表中删除多少成员才能使其优于向量。换句话说，用范围为[0，n）的m个随机整数填充列表和向量。然后删除所有0。对于哪些(m，n)值，列表更有效？ - Jeff G

Answer 3

我不喜欢这里的第一种答案，所以我想分享一些由微软的Herb Sutter进行的实际研究。测试结果是在容器中最多有100k个项目，但也声称即使有50万个实体，它仍将继续优于链表。除非您计划容器拥有数百万个实体，“动态容器的默认容器应该是vector”。我总结了他所说的内容，但底部还提供了参考链接：
“即使您预先分配链表中的节点，这也会使您恢复一半的性能，但仍然比向量差。为什么？首先，它需要更多的空间--每个元素的开销（是原因之一）--链表内的前向和后向指针--但更重要的是访问顺序。链表必须遍历以找到插入点，执行所有这些指针追踪操作，这与向量执行的相同，但实际上发生的事情是预取器速度非常快。使用在内存中高效映射数据（例如，分配和使用定义和布局的指针向量），它将在几乎所有情况下优于链表。”
https://youtu.be/TJHgp1ugKGM?t=2948

- simon

---

为什么向量在访问元素时必须进行线性搜索？它只需在常数时间内跳转到连续的内存中的元素即可。 - Vencat

Answer 4

除非“数据量很大”或“需要强大的安全保证”，否则请使用vector。

数据量很大 :- 在中间插入向量需要线性时间（因为需要重新排列），但其他操作是常数时间操作（如遍历到第n个节点）。因此，如果数据大小较小，则没有太多开销。

根据"Andrei Alexandrescu和Herb Sutter的C++编程规范书"

"对于小型列表，使用向量几乎总是优于使用列表。即使在序列中间插入是向量的线性时间操作，而列表是常数时间操作，但由于其更好的常数因子，向量通常在容器相对较小时表现更好，而列表的Big-Oh优势直到数据大小变大才会发挥作用。"

强大的安全保证 列表提供强大的安全保证。 http://www.cplusplus.com/reference/list/list/insert/

- Rahul_cs12

Answer 5

作为对链表插入和删除的Big O时间的更正，如果您有一个指针来保存当前元素的位置，并且使用方法在列表中移动它(比如.moveToStart()，.moveToEnd()，.next()等)，那么您可以在常数时间内删除和插入。

- blackbox66