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

Question

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

如果我是正确的，链表将这样操作；它将在O(n)时间内找到需要添加/删除的节点的位置，然后在O(1)中添加/删除节点，总时间为O(n)。

在一个数组中，由于随机存取存储器，它会在O(1)时间内找到需要添加/删除的节点的位置，然后在O(n)时间内添加/删除该节点，因为可能需要移动该数组中的所有数据(假设删除意味着将它后面的所有节点移回1)。从而给出了O(n)的总运算时间

从这一点来看，这两种方法似乎都没有明显的优势。如果我看一下平均情况，链表平均需要n/2次操作，因为节点平均在列表的中间。

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

Answer 1

欢迎来到SO！这个问题很有趣。

我认为你是对的，这两个操作都是O(n)，只要数组可以扩展，而不分配新的内存。

但如果必须分配新的内存，问题是会发生什么。

在您的问题中，您假设必须为新的全尺寸数组分配内存。但这可能不是真的。

我不是操作系统专家，但我可以想象以下情况：

内存被划分为多个页面。如果在插入之后，当前nr页(n)不足以存储新数组，则需要n+1页来存储新数组。

在这种情况下-如果我是一名操作系统程序员-我不会分配新的n+1页面并将整个O(n)数组复制到新内存，但我会再分配一个页面，并设置虚拟内存，以便旧页面和新页面在虚拟内存中是连续的，即使它们在物理内存中是不连续的。在这种情况下，情况就像不需要分配新的内存一样(考虑到O符号)。

简而言之，我认为这两种实现都是O(n)。