单链表的时间复杂度 [英] Time Complexity in singly link list

问题描述

我正在研究数据结构:单链表.

网站说单向链表的插入和删除时间复杂度为O(1).我错过了什么吗?

我用 C++ 做这件事，而且我只有一个 root 指针.如果我想在最后插入，那么我必须一路走到后面，这意味着O(n).

解决方案

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

如果您点击了 Singly-LinkedList 实现的维基百科文章的链接变得更加清晰:

<块引用>

function insertAfter(Node node, Node newNode)函数removeAfter(节点节点)

上述函数签名已经将前驱节点作为参数(其他变体也隐含地相同).

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

I am studying data-structure: singly link list.

The website says singly linked list has a insertion and deletion time complexity of O(1). Am I missing something?

website link

I do this in C++, and I only have a root pointer. If I want to insert at the end, then I have to travel all the way to the back, which means O(n).

解决方案

The explanation for this is, that the big O notation in the linked table refers to the function implementation itself, not including the list traversal to find the previous reference node in the list.

If you follow the link to the wikipedia article of the Singly-LinkedList implementation it becomes more clear:

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

The above function signatures already take the predecessor node as argument (same for the other variants implicitly).

Finding the predecessor is a different operation and may be O(n) or other time complexity.

这篇关于单链表的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！