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