单链表的时间复杂度

Question

我正在研究数据结构：单链表。

该网站称单链表的插入和删除时间复杂度为 O(1) 。我错过了什么吗？

网站链接

我在 C++ 中执行此操作，我只有一个 root pointer 。如果我想在最后插入，那么我必须一直走到后面，这意味着 O(n) 。

原文由 Anni_housie 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

对此的解释是，链表中的大 O 表示法是指函数实现本身，不包括在列表中查找上一个引用节点的列表遍历。

如果您点击 单链表实现 的维基百科文章的链接，它会变得更加清晰：

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

上述函数签名已经将前驱节点作为参数（对于其他变体隐式相同）。

寻找前任是一个不同的操作，可能是 O(n) 或其他时间复杂度。

原文由 πάντα ῥεῖ 发布，翻译遵循 CC BY-SA 3.0 许可协议