顺序为 O(n) 的双向链表中插入/删除的时间复杂度是否为 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) 的双向链表中插入/删除的时间复杂度是否为 O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！