传统上，当我们想要在随机位置执行插入/删除操作时，建议使用链接列表。这是因为在使用链接列表（单链表）时，我们只需更改next和previous指针的相邻节点。而在数组中，我们必须推出大量元素才能为新元素留出空间（在插入的情况下）。链接列表插入/删除效率
但是，与数组（随机访问）相比，特别是当我们有大量数据时，在链表中查找插入/删除位置的过程非常昂贵（顺序搜索）。
此因素是否显着降低链接列表中插入/删除数组的效率？或者，在数组的情况下推送元素所需的时间比顺序访问更大的问题？
在链表的情况下发现插入/缺失的位置的过程中是非常昂贵的（顺序的搜索）相比，阵列（随机接入）
的比较是错误的，因为您正在比较插入/删除操作的效率。相反，比较这两个因素：
在有时间复杂度O(n)
为了推复制数组元素链接列表顺序搜索。可能需要复制到n数组元素。
在阵：如果基础类型是POD它可以只realloc，但如果没有它，必须将它们与对象的operator=移动。
所以你可以看到，并非所有的人都赞成数组的使用。 链接列表避免了一次又一次复制相同数据的需要。
，特别是当我们有大数据。
这将意味着更多的数组元素在推移时被复制。
然而，在 情况链表发现插入/缺失的位置的过程是非常昂贵相比， 阵列（随机访问）（顺序搜索），特别是当我们有大量的数据。
随机存取没有什么帮助，如果你正在寻找一个元素，不知道它在哪里，如果你知道它在哪里，并有像一个指针或索引到它，不再有无论您是使用链接列表还是数组，都需要进行搜索来访问元素。在这种情况下，只有在随机访问有帮助的情况下，才能对数组进行排序，在这种情况下，随机访问将启用二进制搜索。
难道这个因素显著减少 插入/缺失的效率在数组a链表？或者是时间 所需的推动元素的情况下，一个阵列更大的问题 比顺序访问？
通常至少与无序序列不同，因为同样，数组和链表都需要线性时间搜索来查找元素。如果人们需要频繁地搜索非重要输入大小的关键路径，通常人们会使用哈希表或平衡二叉树或尝试或者类似的东西。
由于与算法复杂性无关的原因，在许多性能关键字段中，经常使用数组优先于链接列表。这是因为数组保证连续存储它们的元素。这为顺序处理提供了很好的参考地点。
还有一些方法可以在恒定时间从阵列中删除。举个例子，如果你想在常量时间内从数组中删除第n个元素，只需将它与数组中的最后一个元素交换并在常量时间内删除最后一个元素。如果允许重新排列元素，则不一定必须将所有元素全部洗掉才能缩小差距。
链接列表可能连续或不连续地存储它们的节点。如果他们这样做，他们往往会在性能关键的上下文中变得更有用，就像他们将节点存储在数组中一样（通过基于数组的容器或分配器）。否则遍历它们会导致缓存未命中，并且每个正在访问的节点都有可能发生缓存未命中。
比较性能的一些很好的图表（底线是矢量显示效率低，存储元素大小增加）https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque html的 – orhtej2