双向链表的插入/删除操作的时间复杂度是O(n)吗？

Question

6

在双向链表(DLL)中插入/删除具有特定值的节点需要遍历整个列表以查找位置，因此这些操作应该是O(n)。

如果是这样，那么STL列表（最可能使用DLL实现）如何能够在常数时间内提供这些操作呢？

感谢大家为我澄清了这一点。

- ajay

3个回答

3

不是的。STL方法接受一个迭代器来指定插入位置，所以严格来说，它们是O(1)的，因为你已经给出了位置。但是你仍然需要在O(n)中自己找到这个位置。

- IVlad

1

删除任意值（而不是节点）的时间复杂度确实为O(n)，因为需要查找该值。删除节点（即当您开始知道节点时）的时间复杂度为O(1)。

基于值插入 - 例如在排序列表中插入 - 时间复杂度为O(n)。如果您在已知现有节点之后或之前插入，则时间复杂度为O(1)。

向列表头或尾插入始终是O(1) - 因为这些只是上述情况的特例。

- Jon Skeet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- GManNickG · Accepted Answer

在已知位置进行插入和删除的时间复杂度为O(1)。但是，除非它是列表的头或尾，否则查找该位置的时间复杂度为O(n)。

当我们谈论插入和删除的复杂度时，通常假设我们已经知道将要发生的位置。