是在顺序O（n）的双向链表中的插入/删除的时间复杂度？ [英] Is time complexity for insertion/deletion in a doubly linked list of order O(n)?

问题描述

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

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

如果是这样的话，STL列表（最有可能使用DLL实现）能够在常量时间提供这些操作吗？

If that's the case then how come STL list (most likely implemented using DLL) is able to provide these operations in constant time?

推荐答案

在已知位置插入和删除是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.

这篇关于是在顺序O（n）的双向链表中的插入/删除的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！