游客nqewexvef7oyc
游客nqewexvef7oyc_个人页
游客nqewexvef7oyc
文章
0
问答
1
视频
0
个人介绍
暂无个人介绍
擅长的技术
暂无更多信息
2019年08月
-
08.26 18:14:38
回答了问题
2019-08-26 18:14:38
双向链表为什么时间复杂度是O(1)
赞0 踩0 评论0
暂无更多信息
-
回答了问题
2019-08-26
双向链表为什么时间复杂度是O(1)
虽然是很久以前的问题了，但是也许以后会帮助到其他的同学。 双向链表相比于单向链表，所谓的O(1)是指删除、插入操作。 单向链表要删除某一节点时，必须要先通过遍历的方式找到前驱节点（通过待删除节点序号或按值查找）。若仅仅知道待删除节点，是不能知道前驱节点的，故单链表的增删操作复杂度为O(n)。 双链表（双向链表）知道要删除某一节点p时，获取其前驱节点q的方式为 q = p->prior，不必再进行遍历。故时间复杂度为O(1)。而若只知道待删除节点的序号，则依然要按序查找，时间复杂度仍为O(n)。 单、双链表的插入操作，若给定前驱节点，则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点，时间复杂度为O(n)。至于查找，二者的时间复杂度均为O(n)。 对于最基本的CRUD操作，双链表优势在于删除给定节点。但其劣势在于浪费存储空间（若从工程角度考量，则其维护性和可读性都更低）。双链表本身的结构优势在于，可以O(1)地找到前驱节点，若算法需要对待操作节点的前驱节点做处理，则双链表相比单链表有更加便捷的优势。
赞0 踩0 评论0
滑动查看更多
暂无更多信息