c++ - 搜索链表和数组时有什么区别？

Question

我知道数组的值可以通过它们的位置直接访问，而链表必须一个一个地遍历它们，但不知道在搜索发生时如何解释它们的开销和存储方面的差异。

（我认为前一个节点是否需要在某个地方临时存储，同时尝试访问下一个节点时通过它们时系统部分的任何额外存储或开销？并且在搜索数组时也是如此）

谁能给我详细说明在每个结构中搜索时会发生什么？或者只是指向正确的方向

Answer 1

随机访问列表元素允许您实现搜索算法，例如二分搜索，使用链表是不切实际的。

Answer 2

数组是一个固定大小的向量变量。

链接列表没有指定的大小：列表的每个元素都包含一个指向下一个元素的指针。这就是为什么您需要按顺序迭代它的原因。这里的优点是结构不应分配在连续的内存块中，并且如果在其中添加更多元素则不需要调整大小。

同样在数组中，如果删除一个元素，则需要移动所有先前的元素。如果在数组中间插入一个元素，则需要移动元素以为新元素腾出空间。在列表中，您只需更新指针：

另一方面，数组可以随机访问，不需要顺序访问：因此它们可以更快地搜索对象、排序等。