aja*_*jay 5 c++ complexity-theory linked-list
要在DLL(双向链表)中插入/删除具有特定值的节点,需要遍历整个列表以找到位置,因此这些操作应该是O(n).
如果是这种情况,那么为什么STL列表(最有可能使用DLL实现)能够在恒定时间内提供这些操作？
谢谢大家向我说清楚.
GMa*_*ckG 15
在已知位置的插入和删除是O(1).但是,找到该位置是O(n),除非它是列表的头部或尾部.
当我们谈论插入和删除复杂性时,我们通常假设我们已经知道将要发生的位置.