在过去的几天里，我一直在为软件开发工作的第一次电话面试做准备。在研究问题时，我想出了这篇文章。
一切都很棒，直到我到达这段时间，
“你什么时候会使用链表与向量？”
现在根据经验和研究，这是两种非常不同的数据结构，链表是动态数组，向量是空间中的二维点。我可以看到两者之间的唯一相关性是，如果您将向量用作链表，例如myVector(my value, pointer to neighbor)
想法？
问问题
68663 次
5 回答
57
Vector 是动态数组的另一个名称。它是C++ 中用于动态数组数据结构的名称。如果您有 Java 方面的经验，您可能会知道他们的名字ArrayList。（Java 还有一个名为 Vector 的旧集合类，由于其设计方式存在问题，现在已不再使用。）
向量适用于随机读取访问以及后面的插入和删除（需要摊销的常数时间），但不适合前面或任何其他位置的插入和删除（线性时间，因为必须移动项目）。向量通常在内存中连续布局，因此遍历一个是有效的，因为 CPU 内存缓存得到有效使用。
另一方面，链表适用于在前面或后面插入和删除项目（恒定时间），但对其他很多事情不是特别好：例如，删除列表中间任意索引处的项目需要线性时间，因为您必须首先找到节点。另一方面，一旦你找到了一个特定的节点，你可以在恒定时间内删除它或在它之后插入一个新项目，这是矢量无法做到的。链表也很容易实现，这使得它们成为一种流行的数据结构。
于 2013-09-26T23:09:10.680 回答
10
我知道这个提问者有点晚了，但这是一个非常有见地的视频，来自 Bjarne Stroustrup（C++ 的发明者）关于为什么你应该避免使用现代硬件的链表。 https://www.youtube.com/watch?v=YQs6IC-vgmo 随着当今计算机上的快速内存分配，创建带有更新项目的矢量副本要快得多。
于 2015-10-30T14:17:51.723 回答
4
我不喜欢这里的第一答案，所以我想我会分享一些由微软的 Herb Sutter 进行的实际研究。测试的结果是在一个容器中最多包含 100k 个项目，但它还声称它会继续在 50 万个实体上执行链表。除非您计划让容器拥有数百万个实体，否则动态容器的默认容器应该是向量。 我或多或少地总结了他所说的内容，但也会在底部链接参考：
“[即使]你预先分配链表中的节点，这会给你一半的性能，但它仍然[比向量]更差。为什么？首先它有更多的空间——每个元素的开销（是原因）——链表中涉及的前向和后向指针——还有（更重要的是）访问顺序。链表必须遍历才能找到插入点，完成所有指针追逐，这是一样的向量正在做的事情，但实际发生的是预取器是如此之快。使用在内存中有效映射的数据执行线性遍历（分配和使用例如定义和布局的指针向量），它将胜过几乎所有场景中的链表。”
于 2017-05-09T05:35:08.660 回答
1
除非“数据量很大”或“必须有强大的安全保证”，否则使用向量。
数据量大 ：- 在中间插入向量需要线性时间（因为需要随机播放），但其他是恒定时间操作（如遍历到第 n 个节点）。因此，如果数据量小，则没有太多开销。
根据“Andrei Alexandrescu 和 Herb Sutter 的 C++ 编码标准书”
“对小列表使用向量几乎总是优于使用列表。即使在序列中间插入是向量的线性时间操作和列表的恒定时间操作，但当容器相对较小时，向量通常优于列表因为它有更好的常数因子，而且 list 的 Big-Oh 优势在数据量变大之前不会发挥作用。”
强大的安全保障 List提供强大的安全保障。 http://www.cplusplus.com/reference/list/list/insert/
于 2015-11-26T07:53:06.490 回答
1
作为对链表中插入和删除的大 O 时间的更正，如果您有一个保存当前元素位置的指针，以及用于在列表中移动它的方法（如.moveToStart()、.moveToEnd()等.next()），您可以在恒定时间内取出和插入。
于 2016-03-29T18:19:24.907 回答