c – 单链接列表插入和删除的时间复杂度

发布时间：2020-12-16 09:51:17 所属栏目：百科来源：网络整理

导读：我对链接列表的时间复杂性感到有点困惑.在这篇文章 here中,它指出链表中的插入和删除是O(1).我想知道这是怎么回事？假设前向和下一个指针是已知的吗？那不就是Double Linked List吗？如果有人能澄清这一点,我将不胜感激.以及单个链表的插入/删除的时间复杂度

我对链接列表的时间复杂性感到有点困惑.在这篇文章 here中,它指出链表中的插入和删除是O(1).我想知道这是怎么回事？假设前向和下一个指针是已知的吗？那不就是Double Linked List吗？如果有人能澄清这一点,我将不胜感激.以及单个链表的插入/删除的时间复杂度如何是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所示,我们可以通过知道指向插入/删除点的指针来插入和删除.它涉及从后继者复制数据,从而避免修复前一个指针的下一个指针.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!