c++ - 单链表插入和删除的时间复杂度

Question

我对链表的时间复杂度有点困惑。本文中here它指出链表中的插入和删除是 O(1)。我想知道这怎么可能？是否假设前向和下一个指针是已知的？那不是双链表吗？如果有人能澄清这一点，我将不胜感激。以及单链表插入/删除的时间复杂度如何为O(1)？

Answer 1

Is it assumed that the forward and next pointers are known ?

在单链表中，对于插入和删除，您需要一个指向插入/删除点之前的元素的指针。然后一切顺利。

例如:

# insert y after x in O(1)
def insert_after(x, y): 
    y.next = x.next
    x.next = y

# delete the element after x in O(1)
def delete_after(x):
    x.next = x.next.next

对于许多应用程序，可以很容易地通过算法携带您当前正在查看的项目的前身，以允许在恒定时间内动态插入和删除。当然，您始终可以在 O(1) 的列表前面插入和删除，这允许类似堆栈 (LIFO) 的使用模式。

当您只知道指向项目的指针时删除项目通常不可能在 O(1) 中。 编辑: 正如 codebeard 所演示的，我们可以通过知道指向插入/删除点的指针来插入和删除。它涉及从后继者复制数据，从而避免修复前任者的 next 指针。