单链表中的时间复杂度

Question

我正在学习数据结构：单向链表。

该网站称，单向链表的插入和删除时间复杂度为O(1)。我有什么遗漏吗？

网站链接

我使用C++进行操作，只有一个root指针。如果我想在末尾插入，则必须一直前往末尾，这意味着O(n)的时间复杂度。

- Anni_housie

---

看起来是一个重复的问题，与https://dev59.com/nmYq5IYBdhLWcg3w-FXQ相同。 - Jay Rajput

如果您跟随实现示例的链接，您会更好地理解，因为接口与您描述的情况不同。 - πάντα ῥεῖ

Answer 1

这是因为链接表中的大O符号表示函数实现本身，不包括在列表中遍历以查找先前引用节点的时间。

如果您跟随单向链表实现的维基百科文章链接，会更加清楚。

function insertAfter(Node node, Node newNode)
function removeAfter(Node node)     

上面的函数签名已经将前驱节点作为参数（其他变体隐含相同）。

查找前驱节点是一种不同的操作，可能是O(n)或其他时间复杂度。

- πάντα ῥεῖ

Answer 2

您在两个地方都忘了接口：

1. std::list::insert()/std:list::erase() 需要一个迭代器指向要插入或删除的元素。这意味着您不需要搜索，只需更改列表中元素的两个指针，这是恒定的复杂度。

2. 在列表末端插入可以通过 push_back 完成。标准要求这也是 O(1) 的。这意味着，如果您有一个 std::list，它将存储第一个和最后一个元素。

编辑：对不起，您使用的是 std::forward_list。即使名称为 insert_after 和 erase_after，点 1 仍然适用于此。但点 2 不适用，您需要遍历到列表的末尾。

- user6556709

Answer 3

我使用C++，只有一个根指针。如果我想要在末尾插入，则必须一直遍历到最后，这意味着O(n)。
这是两个操作，您首先需要搜索给定位置的列表，然后将元素插入列表中，时间复杂度为O(n)和O(1)。
在单链表中，插入操作包括：
1. 改变前一个元素的指针
2. 将对象打包到数据结构中并将其指针设置为下一个元素
两者都与列表大小无关。
另一方面，以“堆”结构为例。每个元素的插入需要O(log(n))的操作才能保持其结构。 树结构具有类似的机制，将根据当前树大小执行插入操作。

- thorhunter

Answer 4

在这里，假设您已经拥有了节点，并且需要添加一个新元素。

在这种情况下，对于单向链表，插入的时间复杂度为O(1)。

- luffy

Answer 5

事实是，与数组不同，我们在进行插入时不需要移动单向链表的元素。因此，单向链表的插入时间复杂度为O(1)。

想象一下，您有一个填充了整数数字的Python列表...

my_list = [9, 8, 4, 5, 6]

...并且您想在元素8之后插入数字3。

my_list.insert(2, 3)

打印出的结果将是：

[9, 8, 3, 4, 5, 6]

当您向my_list插入元素时，元素3后面的其他元素都向右移动，因此它们的索引会改变。因此，在给定索引处插入元素的时间复杂度为O(n)。

然而，在单链表中，没有数组元素，而是链接节点和节点值。

如上图所示，prev节点持有next节点的引用。正如@πάντα ῥεῖ所述，“函数签名已经将前驱节点作为参数”。您可以在O(n)时间内找到前一个节点，但是在插入新节点时，您只需要更改连接节点的地址即可，这是O(1)时间复杂度。

- Utku

---

但是到达那个节点不会花费O(n)的时间吗？假设我想在值为5的节点之后插入，我需要遍历四次然后再插入。 - Naser Mohd Baig