关于链表与 vector 的效率问题。
我知道链表的插入/删除是常数时间的，而 vector 的相同操作是线性的。但是，考虑到您必须在链表上执行线性搜索才能插入/删除，这最终不是一个线性操作。
插入/删除操作本身是不变的，但由于您无法在不遍历链表的情况下进行插入/删除操作，因此您最终只能进行线性操作。搜索 + 插入/删除 = 线性。
所以我不明白这与 vector 相比有何优势。对我来说，它是一样的。两者(最终)都需要线性操作才能插入/删除。
我在这里错过了什么？
最佳答案
插入:当我们在 vector 中插入时(假设不在末尾)，我们需要将插入位置之后的所有元素打乱 O(n) 而在链表中我们只需要将前一个节点指向新节点并将新节点指向旧的下一个节点 O(1)。
到达:在到达 vector 中的插入位置时，我们只需转到索引 O(1)，而在链表中，从开始到该位置需要 O(n)。
因此，两者各有利弊，具体取决于应用。
如果在随机位置有很多插入，一次又一次地打乱元素将是低效的，链表是一个更好的解决方案。这一点在处理 vector/链表中的复杂对象时得到巩固。
如果插入操作次数不多，而且位置也固定(尤其是序列末尾)，vector会是更好的选择。
关于c++ - 链接列表与 vector ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47213519/