我正在学习数据结构:单向链表。
该网站称,单向链表的插入和删除时间复杂度为O(1)
。我有什么遗漏吗?
我使用C++进行操作,只有一个root指针
。如果我想在末尾插入,则必须一直前往末尾,这意味着O(n)
的时间复杂度。
我正在学习数据结构:单向链表。
该网站称,单向链表的插入和删除时间复杂度为O(1)
。我有什么遗漏吗?
我使用C++进行操作,只有一个root指针
。如果我想在末尾插入,则必须一直前往末尾,这意味着O(n)
的时间复杂度。
function insertAfter(Node node, Node newNode)
function removeAfter(Node node)
上面的函数签名已经将前驱节点作为参数(其他变体隐含相同)。您在两个地方都忘了接口:
std::list::insert()/std:list::erase() 需要一个迭代器指向要插入或删除的元素。这意味着您不需要搜索,只需更改列表中元素的两个指针,这是恒定的复杂度。
在列表末端插入可以通过 push_back 完成。标准要求这也是 O(1) 的。这意味着,如果您有一个 std::list,它将存储第一个和最后一个元素。
编辑:对不起,您使用的是 std::forward_list。即使名称为 insert_after 和 erase_after,点 1 仍然适用于此。但点 2 不适用,您需要遍历到列表的末尾。
在这里,假设您已经拥有了节点,并且需要添加一个新元素。
在这种情况下,对于单向链表,插入的时间复杂度为O(1)。
数组
不同,我们在进行插入时不需要移动单向链表
的元素。因此,单向链表的插入时间复杂度为O(1)
。列表
...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)
时间复杂度。