购买网站域名银川市网站建设
张小明 2026/3/2 19:57:40
购买网站域名,银川市网站建设,一级a做爰片免费网站 新闻,个体户做网站有用吗引入#xff1a;在单链表中#xff0c;查找其直接后继的时间复杂度为O#xff08;1#xff09;#xff0c;而查找其直接前驱的时间复杂度为O#xff08;n#xff09;。好比如下单链表#xff1a;若查找2的直接后继#xff0c;记指针p指向值为2的节点#xff08;p-在单链表中查找其直接后继的时间复杂度为O1而查找其直接前驱的时间复杂度为On。好比如下单链表若查找2的直接后继记指针p指向值为2的节点p-data2则2的直接后继是p-next但若查找2的直接前驱时无法通过p直接获取单链表无前驱指针需从头指针head开始遍历直到找到节点q满足q-next pq即为p的前驱遍历最坏需走n步因此时间复杂度为O(n)故面对这种情况为降低时间复杂度我们引入双向链表。双向链表简介第一个格子为prev指向前一个结点第二个格子为data存放数据第三个格子为next指向后一个结点与单向链表不同的是双向链表多了一个可以指向前一个结点的指针即prev假设图中头结点head后一个结点为q则有q-prev headhead-next q这样链表就能通过next和prev两个指针向前或向后遍历不再是单方向的流动。双向链表的核心优势查找直接前驱 / 后继的时间复杂度均为 O (1)通过prev/next指针直接获取解决了单链表查找前驱 O (n) 的问题插入 / 删除操作时无需像单链表那样从头遍历找前驱节点仅需通过prev指针直接定位操作效率提升注意双向链表的代价是每个节点多占用一个指针的内存空间空间换时间。在双向链表中头插法的使用流程图在已知双向链表的基础上使用头插法按如上图的步骤更改箭头的指向核心代码及理解在双向链表中尾插法的使用流程图第一步将存放新数据的结点记为pp-prev tail尾结点第二步tail-next p将原来的尾结点的next指向新的尾结点new第三步第三步p-next NULL新节点作为新尾节点后继指向NULL若为「双向循环链表」第三步需改为p-next L头结点同时L-prev p头结点的前驱指向新尾节点维持循环结构。核心代码及理解在双向链表中指定位置插入节点的使用第一步在双向链表中指定位置插入pos从1开始计数优先找“前驱节点”更符合操作习惯遍历的终止条件是“找到第pos-1个节点”且必须判断遍历过程中指针是否为空避免pos超出链表长度下面的代码图展示的是前驱结点第二步将数据e存放在新的结点q中第三步改变prev和next的指向让数据e被插入链表中流程图核心代码通过遍历找到指定位置的前一个结点更改指针的指向让新结点插入链表中来p8和p9的代码图源于b站逊哥