list - 在恒定时间内插入/删除双向链表 O(1)

Question

a）我在stackoverflow中看到了很多这个问题的例子，但我仍然无法理解它在调用insertAfter（Node n，Object o）等函数时如何知道它指的是哪个节点。如果我们说在节点 2 之后插入，linkedlist 怎么知道哪个节点是节点 2？

b）在stackoverflow的前几篇文章中，据说有一个指向要在之后或之前插入的节点的指针，这就是我们得到恒定时间操作的原因。这是否意味着，就像我们必须在链表中头尾一样，我们也有一个指向每个节点的指针？

非常感谢帮助理解这一点。

Answer 1

如果使用 key 完成删除，那么您的观点是有效的，因为我们不知道要删除的元素的位置，因此在列表中找到 key 使其时间与队列长度成线性关系。但是在写成恒定时间的地方是按地址删除。因此，人们可能总是移动到该地址并在恒定时间内删除该节点。

注意：这对于单链表是不可能的。