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

Question

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

Answer 1

是否假设前向和下一个指针是已知的？

在单链表中，对于插入和删除，都需要一个指向插入/删除点之前的元素的指针。然后一切都会好起来的。

例如：

# 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前任者的指针。