我对链表的时间复杂度有点困惑。本文中here它指出链表中的插入和删除是 O(1)。我想知道这怎么可能?是否假设前向和下一个指针是已知的?那不是双链表吗?如果有人能澄清这一点,我将不胜感激。以及单链表插入/删除的时间复杂度如何为O(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
指针。
关于c++ - 单链表插入和删除的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22600304/