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

Question

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

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

任何人都可以详细说明在每个结构中搜索时会发生什么吗？或者简单地指向正确的方向

Answer 1

数组是固定大小的 vector 变量。

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

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

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