我花了很多时间反复讨论我应该使用向量还是链表。我读过很多关于这个话题的完全矛盾的观点，所以我想要一个基于真实世界中今天硬件的简单答案。
因此，我被告知，如果你在序列中间进行大量插入和删除，链表将是理想的，复杂度为O(1)（这本身我并不完全理解，因为无论如何你都必须遍历到所需的位置），而插入向量显然非常慢，复杂度是O(n)
另一方面，在观看了Bjarne Stroustrup的讲座后https://www.youtube.com/watch?v=YQs6IC-vgmo似乎链表没有真正的用途，而使用链表因为会有很多插入和删除操作，实际上只有天真的学生才能实现。我从中得到的是，本质上，根据链表遍历的性质，它在遍历内存中的不同位置时会执行多次随机访问，而向量会执行一次随机访问，将您直接发送到所需位置。这个解释准确吗？
在我的实现中，序列是为了保持秩序，在每帧中用每个元素的新值更新，因此需要大量的删除和插入。
我的问题是：链表真的还有什么用吗？即使是为了维持秩序，而不是简单地被挤过海峡？
背景信息：
- 该序列用于2D扫频和修剪宽相位碰撞检测
- 序列中元素数量的上限约为30000
我不会对您的具体情况发表评论，但是的，在"现实"世界中，在"当今"硬件上有很多实例，在这些实例中使用链表是有意义的。
一个例子：malloc和free（即动态内存分配器）的实现通常使用链表来跟踪可用内存块。在链接列表指针的每个内存块中都包含一些额外的字节。通过这种方式，空闲块本身可以链接在一起，而无需在其他地方分配任何额外的内存来跟踪它们（这是矢量所要求的）。
这意味着分配器只需要常量的内存量来进行内部记录保存。否则，您的动态分配器本身将需要使用动态分配器来增加其空闲列表（实际上是"空闲向量"）。
Linux内核（可能还有其他操作系统内核）在很多方面都使用链表。我想，如果它使用向量，当它必须增长向量时，可能会导致不希望的延迟峰值（如果在持有一些重要锁或屏蔽中断等时发生这种情况，那将非常糟糕）。