为什么插入链表O(1)的中间？

Question

根据关于链表的维基百科文章,在链表中间插入被认为是O(1).我认为这将是O(n).您是否需要找到可能接近列表末尾的节点？

此分析是否不考虑节点操作的发现(虽然它是必需的)并且只是插入本身？

编辑:

链接列表与数组相比有几个优点.在列表的特定点处插入元素是恒定时间操作,而在数组中插入可能需要移动一半或更多元素.

上述陈述对我来说有点误导.如果我错了,请纠正我,但我认为结论应该是:

阵列:

• 找到插入/删除点O(1)
• 执行插入/删除O(n)

链接列表:

• 找到插入/删除点O(n)
• 执行插入/删除O(1)

我认为你唯一一次不必找到位置就是你保留了某种指针(如某些情况下的头部和尾部).因此,我们不能断然说链接列表总是超过插入/删除选项的数组.

Answer 1

你是对的,文章认为"索引"是一个单独的操作.因此插入本身就是O(1),但是到达那个中间节点是O(n).

Answer 2

插入本身是O(1).节点发现是O(n).

Answer 3

不,当您决定要插入时,假设您已经在迭代列表中间.

链接列表上的操作通常以这样的方式完成,即它们实际上不被视为通用"列表",而是作为节点的集合 - 将节点本身视为主循环的迭代器.因此,当您浏览列表时,您会注意到作为业务逻辑的一部分,需要添加新节点(或删除旧节点),然后执行此操作.您可以在一次迭代中添加50个节点.

编辑:伙计,你输入第二段而不是第一个响应者,你是第5个和第4个说同样的东西!

Answer 4

为了与数组进行比较,这是图表所示,它是O(1),因为您不必在新节点之后移动所有项目.

所以是的,他们假设你已经拥有指向该节点的指针,或者获得指针是微不足道的.换句话说,问题是:" 在X处给定节点,在此节点之后插入的代码是什么？" 你可以从插入点开始.

Answer 5

一旦你知道要把它放在哪里，插入的复杂度就是 O(1)。

Answer 6

此分析是否没有考虑节点操作的查找（尽管这是必需的）以及插入本身？

你说对了。在给定点插入假定您已经持有指向要在其后插入的项目的指针：

InsertItem(item * newItem, item * afterItem)

Answer 7

不，它不考虑搜索。但是，如果您已经拥有指向列表中间某个项目的指针，则在该点插入的时间复杂度为 O(1)。

如果你必须要搜索它，你就必须加上搜索的时间，应该是O(n)。

Answer 8

插入链表不同于迭代链表.您没有找到该项目,您正在重置指针以将项目放在那里.如果要将其插入前端附近或靠近末端,插入仍然需要重新分配指针.当然,这取决于它是如何实现的,但这是列表的优势 - 您可以轻松插入.通过索引访问是数组发光的地方.但是,对于列表,找到第n个项目通常是O(n).至少那是我从学校里记得的.