单链表中的时间复杂度

Question

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

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

website link

我做这在C++，我只有一个root pointer。如果我想在最后插入，那么我必须一路走到后面，这意味着O(n)。

Answer 1

对此的解释是，链接表中的大O符号指的是函数实现本身，不包括列表遍历以在列表中找到前一个参考节点。

如果按照链接到Singly-LinkedList implementation的维基百科文章变得更加清晰：

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

上述函数签名已经采取了前代节点作为参数（同为其他变体隐）。

查找前驱是一个不同的操作，可能是O（n）或其他时间复杂度。

Answer 2

你错过了接口在两个地方：

1. 的std ::目录::插入（）/ STD：列表::擦除（）需要一个迭代器在哪里插入或删除元素。这意味着你没有搜索，只能在列表中的元素中改变两个指针，这是不变的复杂性。

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

编辑：对不起，你遇到std :: forward_list。即使名称是insert_after和erase_after，点1也适用于此。点2不是，你必须迭代到列表的末尾。

Answer 3

我在C++中这样做，我只有一个根指针。如果我想在最后插入，那么我必须一路走到后面，这意味着O（n）。

这两个操作，首先搜索O（n）的的列表中指定位置，然后插入O（1）元素到列表中。

在单链表，插入的操作包括：

• 交替前一个元素的指针

• 包装对象到数据结构和它的指针设置为下一个元素

两者都不变列表大小。

另一方面，以堆结构为例。插入每个元素需要O（log（n））操作才能保留其结构。树结构具有类似的机制，将在插入时运行并取决于当前的树大小。