data-structures - 链表与向量

Question

在过去的几天里，我一直在为软件开发工作的第一次电话面试做准备。在研究问题时，我提出了 this article.

一切都很棒，直到我到达这个段落，

"When would you use a linked list vs. a vector? "

现在根据经验和研究，这是两种截然不同的数据结构，链表是动态数组，向量是空间中的二维点。我能看到两者之间唯一的相关性是，如果您将向量用作链表，例如 myVector(my value, pointer to neighbor)
想法？

Answer 1

矢量是 dynamic arrays 的别称.它是用于 dynamic array data structure in C++ 的名称.如果您有 Java 方面的经验，您可能知道他们的名字 ArrayList . (Java 还有一个名为 Vector 的旧集合类，由于其设计方式存在问题，现在已不再使用。)

向量适用于后面的随机读取访问和插入和删除(需要摊销常数时间)，但不适用于前面或任何其他位置的插入和删除(线性时间，因为项目必须移动)。矢量通常在内存中连续排列，因此遍历一个是有效的，因为 CPU 内存缓存得到了有效利用。

Linked lists另一方面，对于在前面或后面(恒定时间)插入和删除项目有好处，但对于其他方面不是特别好:例如，删除列表中间任意索引处的项目需要线性时间，因为您必须首先找到节点。另一方面，一旦你找到了一个特定的节点，你就可以在恒定时间内删除它或在它后面插入一个新项目，这是向量无法做到的。链表也很容易实现，这使得它们成为一种流行的数据结构。