【数据结构】链表变体：双向链表与循环链表

考点频率★★★★☆选择题常考重点考查双向链表与单链表的区别以及循环链表的判断条件难度⭐⭐⭐建议重点掌握双向链表的节点结构及其在插入/删除时的指针修改特点理解循环链表的遍历终止条件1️⃣ 为什么需要链表变体上一篇我们讲了单链表。单链表的结构简单但有一个明显的缺点只能单向移动。你只能从前往后走不能从后往前走。如果我想删除某个节点必须知道它的前驱节点是谁——这在单链表中需要从头遍历才能找到。就像一条单行道你只能往前开不能掉头。想回去得绕一大圈从头再来。于是人们发明了两种变体来解决这个问题双向链表给每个节点增加一个指向前驱的指针实现双向移动循环链表把尾节点的指针指向头节点实现循环遍历2️⃣ 双向链表Doubly Linked List2.1 节点结构双向链表的每个节点包含三个部分组成部分含义前驱指针prev指向前一个节点的地址数据域data存储数据后继指针next指向后一个节点的地址// 双向链表节点的结构定义typedefstructDNode{intdata;// 数据域structDNode*prev;// 前驱指针structDNode*next;// 后继指针}DNode;与单链表的区别单链表只有next指针双向链表多了prev指针可以向前和向后双向遍历。2.2 双向链表的核心特点特点说明双向遍历可以从头到尾也可以从尾到头删除更灵活删除节点时如果已知该节点的指针无需遍历找前驱直接通过prev就能找到插入更灵活可以在节点之前插入也可以在节点之后插入空间开销更大每个节点多存储一个指针占用更多内存2.3 双向链表的插入操作以在节点p之后插入新节点s为例// 在节点 p 之后插入新节点 ss-nextp-next;// 新节点的 next 指向 p 的后继s-prevp;// 新节点的 prev 指向 pif(p-next!NULL){p-next-prevs;// p 的后继的 prev 指向 s}p-nexts;// p 的 next 指向 s时间复杂度O(1)O(1)O(1)前提是已知插入位置的前驱节点2.4 双向链表的删除操作以删除节点q为例// 删除节点 q假设 q 不为 NULLq-prev-nextq-next;// q 的前驱的 next 指向 q 的后继if(q-next!NULL){q-next-prevq-prev;// q 的后继的 prev 指向 q 的前驱}free(q);// 释放 q 的内存时间复杂度O(1)O(1)O(1)前提是已知待删除节点的指针单链表 vs 双向链表的删除在单链表中如果只知道要删除的节点本身无法直接删除它因为找不到它的前驱必须从头遍历。双向链表通过prev指针直接找到前驱无需遍历。3️⃣ 循环链表Circular Linked List3.1 什么是循环链表循环链表是一种首尾相连的链表。在单链表或双向链表的基础上将最后一个节点的next指针指向头节点或头指针形成一个环。打个比方单链表像一条有终点的单向公路走到头就是NULL死路。循环链表像一条环形跑道——你从起点出发绕了一圈还能回到起点永远不会遇到死路。3.2 循环链表的两种形式类型结构特点遍历终止条件单循环链表尾节点的next指向头节点回到头节点时停止双循环链表头节点的prev指向尾节点尾节点的next指向头节点回到头节点时停止3.3 循环链表的遍历遍历终止条件的判断方式是唯一的考点。非循环链表p NULL时停止循环链表p head时停止已经绕完一圈回到起点// 循环单链表的遍历Node*phead-next;// 从第一个数据节点开始带头节点while(p!head){// 回到头节点就停止printf(%d ,p-data);pp-next;}3.4 循环链表的适用场景应用场景原因约瑟夫环问题循环删除节点利用环形结构自然实现操作系统进程调度时间片轮转循环遍历就绪队列每个进程轮流获得CPU时间环形缓冲区数据循环读写不需要移动数据4️⃣ 三种链表完整对比表重点对比项单链表双向链表循环链表以单循环为例节点结构data nextdata prev nextdata next遍历方向只能向前可前可后只能向前但可循环遍历终止条件p NULLp NULLp head空间开销小1个指针/节点大2个指针/节点小1个指针/节点查找前驱需从头遍历O(n)O(n)O(n)直接通过prevO(1)O(1)O(1)需从头遍历O(n)O(n)O(n)删除已知节点O(n)O(n)O(n)需找前驱O(1)O(1)O(1)直接通过prevO(n)O(n)O(n)需找前驱典型应用简单线性结构需要反向遍历的场景环形队列、约瑟夫环5️⃣ 经典例题例题1在双向链表中删除一个已知节点非头节点、非尾节点需要修改的指针数量是 。A. 2 个B. 3 个C. 4 个D. 5 个解析删除已知节点q需要修改q-prev-next1个、q-next-prev1个共修改2 个指针。但如果把q本身的prev和next置空也算的话就是4个。软考中通常问的是“修改链表中的指针”答案是2 个。选A。例题2在带头节点的单向循环链表中判断链表为空的条件是 。A.head NULLB.head-next NULLC.head-next headD.head head-next解析带头节点的单向循环链表中空链表的头节点的next指向它自己。选C。例题3概念判断双向链表比单链表占用更多的存储空间但删除操作更灵活。 解析正确。双向链表每个节点多存储一个prev指针空间开销更大但删除已知节点时无需遍历找前驱更加灵活。6️⃣ 记忆口诀双向链表两个针前后遍历都可行。删除不用找前驱直接通过 prev 拎。循环链表首尾连遍历到头不算完。判断空表看头尾head-next head是关键。7️⃣ 小测验评论区对答案在带头节点的双向循环链表中若head-next head则表示 。A. 链表中有 1 个数据节点B. 链表为空C. 链表已满D. 链表出现错误本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #双向链表 #循环链表 #数据结构 #软考备考