arrays - 在列表中的任何位置添加/删除元素时，链表是否比数组更好？

Question

有人告诉我，一般来说，从链表中添加和删除往往会更好，因为永远不必移动内存来容纳新元素。我不确定这是否真的适用于何时可以在列表中的任何位置添加/删除。

如果我是正确的，链表将像这样运行；它将在 O(n) 时间内找到需要添加/删除的节点的位置，然后在 O(1) 中添加/删除节点，从而给出整体时间 O(n)。

在数组中；由于随机存取存储器，它会在O(1)时间内找到需要添加/删除节点的位置，然后在O(n)时间内添加/删除节点，因为可能需要移动所有数据数组(假设删除意味着将其后的所有节点移回 1)。因此给出了 O(n) 的整体操作时间

由此看来，两者似乎都没有明显的优势。如果我看平均情况，链表平均需要 n/2 次操作，因为节点平均位于链表的中间。

对于数组，由于类似的原因，删除也平均需要 n/2 次操作，而如果需要移动所有数据以容纳额外的元素，则添加将需要 n 次操作，如果有足够的空间，则需要 n/2 次并且需要将数据向上移动 1 个空间。这会给出 2*n/3 的平均值吗，这可能是为什么链表更适合这个的原因吗？

Answer 1

欢迎来到SO!有趣的问题。
我认为你是对的，只要可以扩展数组而不分配新内存，这两个操作都是 O(n)。
但是如果必须分配新的内存，问题是那会发生什么。
在您的问题中，您假设必须为新的全尺寸数组分配内存。但这可能不是真的。
我不是操作系统专家，但我可以想象以下情况:
内存被分成页面。如果当前nr页(n)不足以存储插入后的新数组，则需要n+1页用于新数组。
在这种情况下——如果我是一名操作系统程序员——我不会分配新的 n+1 页并将 O(n) 的整个数组复制到新内存，但我会再分配一个页面，并设置虚拟内存，以便旧页面和新页面在虚拟内存中是连续的，即使它们在物理内存中是不连续的。在这种情况下，情况与无需分配新内存一样(考虑 O 表示法)。
简而言之，我相信这两种实现都是 O(n)。