在双向链表中插入/删除的时间复杂度是 O(n) 吗？
要在 DLL（双向链表）中插入/删除具有特定值的节点，需要遍历整个链表来查找位置，因此这些操作应该是 O(n)。
如果是这样的话，那么STL列表（很可能使用DLL实现）为何能够在恒定时间内提供这些操作呢？
谢谢大家给我讲清楚了。
To insert/delete a node with a particular value in DLL (doubly linked list) entire list need to be traversed to find the location hence these operations should be O(n).
If that's the case then how come STL list (most likely implemented using DLL) is able to provide these operations in constant time?
Thanks everyone for making it clear to me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
在已知位置插入和删除的时间复杂度为 O(1)。然而，找到该位置的时间复杂度为 O(n)，除非它是列表的头或尾。
当我们谈论插入和删除的复杂性时，我们通常假设我们已经知道这将发生在哪里。
Insertion and deletion at a known position is O(1). However, finding that position is O(n), unless it is the head or tail of the list.
When we talk about insertion and deletion complexity, we generally assume we already know where that's going to occur.
它不是。 STL 方法将迭代器带到要发生插入的位置，因此严格来说，它们是
O(1)，因为您给了它们位置。然而，您仍然需要自己在O(n)中找到位置。It's not. The STL methods take an iterator to the position where insertion is to happen, so strictly speaking, they ARE
O(1), because you're giving them the position. You still have to find the position yourself inO(n)however.删除任意值（而不是节点）确实是 O(n)，因为它需要找到该值。删除一个节点（即当您开始了解该节点时）的复杂度为 O(1)。
基于值插入 - 例如插入排序列表 - 将为 O(n)。如果在现有已知节点之后或之前插入，则时间复杂度为 O(1)。
插入到列表的头部或尾部总是 O(1) - 因为这些只是上述情况的特殊情况。
Deleting an arbitrary value (rather than a node) will indeed be O(n) as it will need to find the value. Deleting a node (i.e. when you start off knowing the node) is O(1).
Inserting based on the value - e.g. inserting in a sorted list - will be O(n). If you're inserting after or before an existing known node is O(1).
Inserting to the head or tail of the list will always be O(1) - because those are just special cases of the above.