为什么使用链接法解决冲突中删除元素的时间复杂度可以是O(1)？-灵析社区
UX_siri在算法导论《第3版》11.2节中表述如果采用的是双向链表结构，那么可以在O(1)的时间复杂度内删除指定元素。书中的解释和分析并没有一阵见血地指出是为啥。 因为在我看来只要是链表结构，无论是双向链表还是单向链表都需要有一个查找过程，所以删除的时间复杂度应该是O(n)才对，为什么书中说它是O(1)？应该怎么理解？
sssssjkl你主观上将"删除"和"查找"两个动作结合了。
这块的"删除"应该这样理解，当前已经拿到了具体的要删除的元素，现在要从线性表中将其移除。
* 链表只需修改指针即可，故O(1)；
* 数组在清除数据后，(当需要时)还需移动后续元素以保持连续，故O(N)。