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

高楼逃生装置

单链表和双链表的删除和插⼊的时间复杂度分析

单向链表要删除某⼀节点时，必须要先通过遍历的⽅式到前驱节点（开发中⼤致分为两种删除⽅式:1.通过待删除节点序号2.按值查）。若仅仅知道待删除节点，是不能知道前驱节点的，故单链表的增删操作复杂度为O(n)。

隔音房制作双链表（双向链表）知道要删除某⼀节点p时，获取其前驱节点q的⽅式为 q = p->prior，不必再进⾏遍历。故时间复杂度为O(1)。⽽若只知道待删除节点的序号，则依然要按序查，时间复杂度仍为O(n)。

单、双链表的插⼊操作，若给定前驱节点，则时间复杂度均为O(1)。否则只能按序或按值查前驱节点，时间复杂度为O(n)。

led显示屏单元板⾄于查，⼆者的时间复杂度均为O(n)。对于最基本的CRUD操作，双链表优势在于删除给定节点。但其劣势在于浪费存储空间（若从⼯程⾓度考量，则其维护性和可读性都更低）。

喷绘相纸砭石祛斑泥双链表本⾝的结构优势在于，可以O(1)地到前驱节点，若算法需要对待操作节点的前驱节点做处理，则双链表相⽐单链表有更加便捷的优势。祛痘灵

本文发布于:2024-09-23 02:20:58，感谢您对本站的认可！

标签：节点双链前驱删除

留言与评论（共有 0 条评论）