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

问题描述

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

I am studying data-structure: singly link list.

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

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

网站链接

我用C ++做到这一点，而我只有一个root pointer.如果要在末尾插入，则必须一直向后移动，这表示O(n).

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).

推荐答案

对此的解释是，链接表中的大O表示法引用的是函数实现本身，不包括遍历列表以查找先前的引用节点.在列表中.

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).

查找前任是另一种操作，可能是O(n)或其他时间复杂度.

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

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