logo标签列表

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

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

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

以上陈述对我来说有点误导性。请纠正我如果我错了，但我认为结论应该是： 数组：
  • 查找插入/删除点 O(1)
  • 执行插入/删除 O(n)
链表：
  • 查找插入/删除点 O(n)
  • 执行插入/删除 O(1)
我认为唯一不需要查找位置的时候是如果您保留某种指向它的指针（如某些情况下的头和尾）。因此我们不能断言链表总是优于数组的插入/删除选项。
14个回答
162

您是正确的，这篇文章将“索引”视为单独的操作。因此，插入本身是O(1)，但到达中间节点的时间复杂度是O(n)。

7
当在同一位置插入多个对象时，哪种情况会产生更大的差异... - Has QUIT--Anony-Mousse
@Anony-Mousse，你能再解释一下吗？也就是说，当插入多个对象时，我们只需要找到插入位置一次？ - WelcomeTo
3
这里的复杂度是基于现有列表的大小O(n)，而不是你计划在其中进行插入的次数。 - Has QUIT--Anony-Mousse
39

插入操作本身的时间复杂度为O(1)。查找节点的时间复杂度为O(n)。

33

不，当你决定要插入时，假设你已经在遍历列表的中间。

对链表的操作通常不是作为一个通用的“列表”来处理，而是作为节点的集合——将节点本身视为主循环的迭代器。因此，在浏览列表时，您会注意到作为业务逻辑的一部分需要添加新节点（或删除旧节点），然后进行操作。您可能会在单次迭代中添加50个节点，每个节点只需要O(1)的时间来取消链接两个相邻的节点并插入新节点。

7

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

因此，是的，他们假设您已经拥有指向该节点的指针，或者获取指针很容易。换句话说，问题陈述为：" 给定节点X，插入此节点后面的代码是什么？"您可以从插入点开始。

6
插入链表与遍历链表不同。你不是在定位项目，而是重新设置指针以将项目放入其中。无论它将被插入到前端还是后端附近，插入仍涉及重新分配指针。当然，它取决于它的实现方式，但这就是列表的优势 - 你可以轻松地插入。通过索引访问是数组的优点。对于一个列表，通常需要O(n)的时间才能找到第n个项目。至少这是我从学校记住的。
5

这个分析没有考虑到节点操作的发现（尽管它是必需的），只考虑了插入本身吗？

没错。在给定位置进行插入操作，假设您已经持有指向要插入的项之后的指针：

InsertItem(item * newItem, item * afterItem)
5

一旦你知道要放置的位置，插入操作的时间复杂度为O(1)。

5

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

如果您必须搜索它，则必须添加搜索时间，这应该是O(n)。

4

因为它不涉及任何循环。

插入操作如下：

  • 插入元素
  • 链接到前一个元素
  • 链接到后一个元素
  • 完成

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

因此，一个接一个地插入n个元素的时间复杂度为O(n)。

1

最常见的情况可能是在列表的开头或结尾插入项目（而且找到列表的末尾可能不需要时间）。

与此相比，在数组的开头或结尾插入项目则需要调整数组大小（如果在结尾，则需要调整数组大小；如果在开头，则需要调整并移动所有元素）。

如果在数组末尾保留一些空元素的缓冲区，那么将项目插入到数组末尾是O(1)的，尽管有时插入仍然是O(1)的。大多数集合都这样做。通过将索引运算符更改为返回元素编号(n+x)%len，其中x是您已将项目插入列表开头的次数，可以使将项目插入数组开头成为O(1)。双端队列有时会像这样实现（但有时也会使用双向链表）。 - Brian
如果你必须调整数组的缓冲区大小，那就不是O(1)，因为你还必须将n个元素从旧缓冲区复制到新缓冲区。如果你将元素留在旧缓冲区中，有一个非连续的链接缓冲区链，那就是一个列表！ - ChrisW
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接