为什么在链表中间插入元素的时间复杂度是O(1)？

Question

168

根据维基百科关于链表的文章，在链表中间插入被认为是O(1)。但我认为它应该是O(n)，因为你需要找到可能在列表末尾附近的节点。这个分析是否没有考虑到查找节点操作（虽然必须执行）只是插入本身？ 编辑： 引用块：

相对于数组，链表有几个优点。在列表特定位置插入元素是一个恒定时间的操作，而在数组中插入可能需要移动一半或更多的元素。

以上陈述对我来说有点误导性。请纠正我如果我错了，但我认为结论应该是： 数组：

链表：

我认为唯一不需要查找位置的时候是如果您保留某种指向它的指针（如某些情况下的头和尾）。因此我们不能断言链表总是优于数组的插入/删除选项。

- Rob Sobers

14个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- anon · Answer 1

本文是关于比较数组和列表的文章。对于数组和列表的插入位置查找，时间复杂度均为O(N)，因此本文不予考虑。

- Glenn · Answer 2

O(1) 是基于您有一个要插入新项的项目的事实（之前或之后）。如果没有，它就是 O(n)，因为您必须找到该项目。

- workmad3 · Answer 3

我认为这只是选择您要计算O()符号的情况。在插入正常操作的情况下，计数操作是复制操作。对于一个数组，在中间插入涉及将位置上方的所有内容复制到内存中。对于链表，这变成了设置两个指针。无论如何，您都需要找到要插入的位置。

- Sani Huttunen · Answer 4

如果您有要插入的节点的引用，则在链表中进行此操作的时间复杂度为O(1)。
对于数组而言，由于您必须移动所有连续的节点，因此仍然是O(n)。