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

根据 关于链表的维基百科文章，在链表中间插入被认为是 O (1)。我想应该是 O (n)。您不需要找到可能位于列表末尾的节点吗？

难道这种分析没有考虑到节点操作的发现(尽管它是必需的)和插入本身吗？

编辑:

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

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

数组:

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

相关名单:

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

我认为你唯一不需要找到位置的时候就是你保留一些指向它的指针(就像某些情况下的头和尾)。因此，我们不能直截了当地说，对于插入/删除选项，链表总是优先于数组。

79739 次浏览
小开

因为它不涉及任何循环。

插入就像:

  • 插入元素
  • 链接到上一页
  • 链接到下一个
  • 搞定

这在任何情况下都是常量时间。

因此，一个接一个地插入 n 个元素是 O (n)。

小开
最佳答案

您是正确的，本文将“索引”视为一个单独的操作。所以插入本身是 O (1) ，但到达中间节点是 O (n)。

小开

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

小开

不，当您决定要插入时，它假定您已经在对列表进行迭代。

LinkedList 上的操作通常是这样完成的，它们并不真正被视为一个通用的“列表”，而是作为一个节点集合——把节点本身想象成主循环的迭代器。因此，当您浏览这个列表时，您会注意到，作为业务逻辑的一部分，需要添加一个新节点(或者删除一个旧节点) ，并且这样做了。您可以在一次迭代中添加50个节点，并且每个节点的时间只有取消两个相邻节点的链接并插入新节点的时间 O (1)。

小开

难道这种分析没有考虑到节点操作的发现(尽管它是必需的)和插入本身吗？

没问题。给定点上的插入假设您已经持有一个指向要插入的项的指针:

InsertItem(item * newItem, item * afterItem)
小开

插入本身是 O (1)。节点查找是 O (n)。

小开

这篇文章是关于数组和列表的比较。查找数组和列表的插入位置是 O (N) ，因此本文将忽略它。

小开

O (1)取决于这样一个事实，即您有一个要插入新项的项。(之前或之后)。如果你没有，它是 O (n) ，因为你必须找到那个项目。

小开

不，这不能解释搜索。但是如果您已经拥有一个指向列表中间项的指针，那么在该点插入就是 O (1)。

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

小开

我认为这只是一个选择 O ()符号的例子。在插入普通的计数操作的情况下是复制操作。对于数组，在中间插入涉及到将位置之上的所有内容复制到内存中。对于链表，这变成了设置两个指针。不管插入什么，都要找到位置。

小开

为了与数组进行比较，图表显示的是 O (1) ，因为您不必移动新节点后面的所有项。

因此，是的，它们假设您已经拥有指向该节点的指针，或者获取指针是微不足道的。换句话说，问题是这样陈述的: “ 给定 X 点的节点，在这个节点之后插入什么代码?”你可以从插入点开始。

小开

如果有要插入的节点的引用，则对于链表的操作是 O (1)。
对于数组，它仍然是 O (n) ，因为必须移动所有结果节点。

小开

最常见的情况可能是在列表的开头或结尾处插入(并且列表的结尾可能不需要花费时间就能找到)。

与此相反，在数组的开始或结束处插入项(如果数组在结束处，则需要调整数组的大小，如果数组在开始处，则需要调整并移动所有元素)。

小开

插入到链表中与在链表中迭代是不同的。您没有定位该项，而是重置指针以将该项放入其中。不管插入是在前端附近还是在末端附近，插入仍然需要重新分配指针。当然，这取决于它是如何实现的，但这就是列表的优势所在——您可以轻松地插入。通过索引访问是数组的亮点。然而，对于一个列表，通常是 O (n)来查找第 n 项。至少我在学校是这么记得的。


提交答案