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

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

总结

以上是内存溢出为你收集整理的c – 单链接列表插入和删除的时间复杂度全部内容，希望文章能够帮你解决c – 单链接列表插入和删除的时间复杂度所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。