一单链表和双链表更多单链表详细讲解地址单链表的定义、实现、核心操作与逆置1.1 单链表的基本概念单链表Singly Linked List是最简单的链表结构由一系列结点组成每个结点包含两个部分数据域data存储数据元素指针域next存储下一个结点的地址1.1.1 单链表结点结构定义typedefintElemType;// 假设元素类型为整型typedefstructLNode{ElemType data;// 数据域structLNode*next;// 指针域指向下一个结点}LNode,*LinkList;// LNode是结点类型LinkList是指向头结点的指针1.1.2 单链表的优缺点优点动态分配内存不需要预先知道数据大小插入和删除操作时间复杂度为O(1)在已知位置不需要连续的内存空间缺点只能单向遍历无法反向访问查找特定结点需要从头开始遍历时间复杂度为O(n)每个结点需要额外空间存储指针1.2 单链表的基本操作1.2.1 初始化带头结点的单链表// 初始化一个带头结点的单链表boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));// 分配头结点if(LNULL)returnfalse;// 内存分配失败L-nextNULL;// 头结点的next指向NULL表示空表returntrue;}1.2.2 按位序插入带头结点// 在第i个位置插入元素e带头结点boolListInsert(LinkListL,inti,ElemType e){if(i1)returnfalse;// i值不合法LNode*pL;// p指向头结点intj0;// 当前p指向的是第几个结点// 寻找第i-1个结点while(p!NULLji-1){pp-next;j;}if(pNULL)returnfalse;// i值不合法// 创建新结点LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)returnfalse;// 内存分配失败s-datae;// 插入新结点s-nextp-next;p-nexts;returntrue;}1.2.3 按位序删除带头结点// 删除第i个位置的元素boolListDelete(LinkListL,inti,ElemTypee){if(i1)returnfalse;LNode*pL;// p指向头结点intj0;// 当前p指向的是第几个结点// 寻找第i-1个结点while(p!NULLji-1){pp-next;j;}if(pNULL||p-nextNULL)returnfalse;// i值不合法LNode*qp-next;// q指向要删除的结点eq-data;// 用e返回被删除元素的值// 删除结点p-nextq-next;free(q);returntrue;}1.2.4 按值查找// 按值查找返回结点指针LNode*LocateElem(LinkList L,ElemType e){LNode*pL-next;// 从第一个数据结点开始while(p!NULL){if(p-datae){returnp;// 找到返回结点指针}pp-next;}returnNULL;// 未找到}1.2.5 求表长// 求单链表的长度带头结点intLength(LinkList L){intlen0;LNode*pL-next;// 从第一个数据结点开始while(p!NULL){len;pp-next;}returnlen;}1.3 单链表的遍历// 遍历单链表并打印所有元素voidPrintList(LinkList L){LNode*pL-next;// 从第一个数据结点开始printf(链表元素: );while(p!NULL){printf(%d - ,p-data);pp-next;}printf(NULL\n);}1.4 单链表的局限性虽然单链表在很多场景下非常有用但它存在以下主要局限性单向遍历限制只能从头到尾遍历无法从尾到头前驱访问困难要访问某个结点的前驱结点必须从头开始遍历删除操作复杂删除指定结点需要知道其前驱结点尾插效率低在尾部插入需要遍历整个链表找到尾结点示例场景假设我们需要在链表中删除某个结点p在单链表中需要// 在单链表中删除结点p已知p// 需要先找到p的前驱结点LNode*preL;while(pre-next!ppre-next!NULL){prepre-next;}if(pre-nextp){pre-nextp-next;free(p);}这种局限性促使了双链表的出现它通过增加一个指向前驱的指针完美解决了上述问题。1.5双链表的定义与初始化1.5.1结构定义多了一个prior指针双链表结点与单链表结点的最大区别在于多了一个prior指针用于指向前驱结点。单链表结点结构data数据域next指向后继结点的指针只能往后走双链表结点结构data数据域prior指向前驱结点的指针next指向后继结点的指针typedefintElemType;typedefstructDNode{// 定义双链表结点类型ElemType data;// 数据域structDNode*prior,*next;// 前驱和后继指针}DNode,*DLinkList;// DNode 是结点DLinkList 是指向头结点的指针1.5.2 带头结点的双链表初始化// 初始化一个带头结点的双链表boolInitDLinkList(DLinkListL){L(DNode*)malloc(sizeof(DNode));// 1. 分配头结点空间if(LNULL)returnfalse;// 2. 内存分配失败检查L-priorNULL;// 3. 头结点的 prior 永远指向 NULL因为它前面没有结点L-nextNULL;// 4. 头结点的 next 指向 NULL当前为空表returntrue;} 重要注意事项双链表的初始化必须把prior和next都置为NULL。如果有任意一个没有置空就会变成野指针导致后续操作崩溃。1.6. 双链表的核心操作双链表拥有两个指针因此插入和删除比单链表多了一倍的操作需要同时修改两个方向。操作顺序的正确性至关重要1.6.1 指定结点的后插操作InsertNextDNode目标在已知结点 p 之后插入一个新结点 s。// 在 p 结点之后插入 s 结点boolInsertNextDNode(DNode*p,DNode*s){if(pNULL||sNULL)returnfalse;// 1. 防空指针// 核心指针修改顺序绝不能乱 s-nextp-next;// 2. 新结点 s 的 next先指向 p 原本的下一个结点 yif(p-next!NULL){// 3. 【极其重要】如果 p 不是最后一个结点p-next-priors;// 4. 让原本 y 结点的 prior反向指回到新结点 s}s-priorp;// 5. 新结点 s 的 prior 指向前驱 pp-nexts;// 6. p 的 next 重新指向新结点 s// returntrue;} 逐句精讲与避坑第3行和第4行为什么必须用if (p-next ! NULL)保护如果 p 是链表的最后一个结点即p-next NULL此时执行第4行p-next-prior s;相当于执行了NULL-prior s;这会导致程序发生严重的内存错误段错误而直接崩溃双链表安全法则在双链表中访问-next-prior之前必须先校验-next是否为空1.6.2 指定结点的前插操作InsertPriorDNode单链表前插的痛点由于没有前驱指针只能从头遍历找前驱。双链表的优势因为有了 prior 指针前插变得和后插一样简单// 在 p 结点之前插入新结点 s已知 pboolInsertPriorDNode(DNode*p,DNode*s){if(pNULL||sNULL||p-priorNULL)returnfalse;// 防止 p 是头结点s-priorp-prior;// 1. s 的 prior 指向 p 的原前驱p-prior-nexts;// 2. p 的原前驱的 next 指向 ss-nextp;// 3. s 的 next 指向 pp-priors;// 4. p 的 prior 指向 sreturntrue;}1.6.3 指定结点的删除操作DeleteNextDNode需求删除 p 的后继结点 q。// 删除 p 结点的后继结点 qboolDeleteNextDNode(DNode*p){if(pNULL)returnfalse;DNode*qp-next;// 1. 令 q 指向 p 的后继if(qNULL)returnfalse;// 2. 如果 p 后面没有结点直接返回失败p-nextq-next;// 3. 让 p 的 next 跳过 q指向 q 的 nextif(q-next!NULL){// 4. 【极其重要】同样需要判空q-next-priorp;// 5. 如果 q 不是尾结点让 q 原本的后继结点的 prior 反向指回 p}free(q);// 6. 释放被摘除的 q 结点内存returntrue;} 为什么不可以用if (q ! NULL)代替if (q-next ! NULL)我们访问的是q-next-prior这意味着我们在求 q 的下一跳。如果 q 本身是最后一个结点指向NULL那么q-next就是NULL。再次访问NULL-prior会导致崩溃。双链表删除铁律先判后继再改前驱是所有双链表删除操作的铁律。1.7 408考点补充1.7.1 补充考点按位序插入ListInsert思路和单链表完全一致先找到第 i-1 个结点然后调用写好的后插函数。boolListInsert(DLinkListL,inti,ElemType e){if(i1)returnfalse;// 1. 找到第 i-1 个结点DNode*pGetElem(L,i-1);// 假设我们已经实现了 GetElem和单链表完全一样if(pNULL)returnfalse;// 2. 创建新结点DNode*s(DNode*)malloc(sizeof(DNode));if(sNULL)returnfalse;s-datae;// 3. 直接复用后插操作returnInsertNextDNode(p,s);}1.7.2 补充考点销毁整条双链表DestroyList注意必须先释放所有真实的数据结点最后才能释放头结点。voidDestroyList(DLinkListL){// 1. 循环释放数据结点while(L-next!NULL){DeleteNextDNode(L);// 不断删除头结点后面的第一个结点}// 2. 释放头结点free(L);LNULL;// 防止悬空指针野指针}1.8 双链表的遍历双链表可以方便地正向遍历也可以反向遍历。1.8.1 后向遍历从头到尾DNode*pL-next;// 从第一个数据结点开始while(p!NULL){// 对结点 p 做相应处理如打印 p-dataprintf(%d ,p-data);pp-next;}1.8.2 前向遍历从尾到头// 假设 p 指向最后一个结点while(p!NULL){// 对结点 p 做相应处理printf(%d ,p-data);pp-prior;}1.8.3 前向遍历跳过头结点如果 p 指向的是最后一个结点我们可以利用 prior 一直往前走直到p-prior NULL撞到头结点停止。while(p-prior!NULL){// 对结点 p 做相应处理printf(%d ,p-data);pp-prior;}⚠️ 考研核心结论双链表虽然能双向移动但依然不具备随机存取特性。如果你要找第 i 个元素或者按值查找依然只能通过遍历的方式实现平均时间复杂度为 O(n二循环链表在掌握了双链表的基础上我们进一步探讨链表的另一种重要变体——循环链表。循环链表通过将链表的首尾相连形成闭环结构在某些场景下能提供更高效的操作2.1 循环单链表 (Circular Singly Linked List)2.1.1 核心特性与数据结构改变普通单链表最后一个数据结点的 next 指针指向 NULL。循环单链表最后一个数据结点的 next 指针不指向 NULL而是指向头结点Head Node从而形成一个闭合的环。结构体定义和普通单链表完全一样typedefintElemType;typedefstructLNode{ElemType data;structLNode*next;}LNode,*LinkList;2.1.2 循环单链表的初始化、判空与判尾由于尾巴不再指向 NULL判断链表为空和为尾的规则发生了彻底的改变。// 1. 初始化一个带头结点的循环单链表boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));// 分配头结点if(LNULL)returnfalse;L-nextL;// 【核心差异】头结点的 next 指向自身returntrue;}// 2. 判断循环单链表是否为空boolEmpty(LinkList L){if(L-nextL)// 如果头结点的 next 指向自己说明只有头结点空表returntrue;elsereturnfalse;}// 3. 判断结点 p 是否为循环单链表的表尾结点重点应用boolisTail(LinkList L,LNode*p){if(p-nextL)// 如果 p 的 next 指向了头结点说明 p 就是表尾returntrue;elsereturnfalse;}2.1.3 循环单链表的遍历防死循环因为链表是闭合的用普通的while(p ! NULL)会陷入死循环。正确的遍历逻辑必须使用从头结点的下一个开始直到回到头结点作为结束条件。voidPrintList(LinkList L){LNode*pL-next;// p 从第一个数据结点开始if(pL){// 空表直接返回printf(空表\n);return;}printf(链表: );while(p!L){// 【关键】只要 p 还没绕回 L头结点就继续打印printf(%d - ,p-data);pp-next;}printf(回到头结点 (L)\n);}2.1.4 补充考点从表中任意结点出发都能遍历全表普通单链表如果你只拿到结点 a₂ 的指针你永远找不到 a₁ 和头结点。但在循环单链表中无论你从哪个结点出发顺着 next 一直走最终都会绕回自己从而找到全表的任意一个结点。2.2 循环双链表 (Circular Doubly Linked List)2.2.1 核心特性与数据结构定义在普通双链表中头结点的 prior 指向 NULL尾结点的 next 指向 NULL。在循环双链表中这两个死胡同被彻底打通了头结点的 prior 指向表尾结点。表尾结点的 next 指向头结点。结构体定义和普通双链表一致typedefstructDNode{ElemType data;structDNode*prior,*next;}DNode,*DLinkList;2.2.2 循环双链表的初始化、判空与判尾双指针闭环// 1. 初始化带头结点的循环双链表boolInitDLinkList(DLinkListL){L(DNode*)malloc(sizeof(DNode));if(LNULL)returnfalse;L-priorL;// 【核心差异】头结点的 prior 指向自身L-nextL;// 【核心差异】头结点的 next 指向自身returntrue;}// 2. 判断循环双链表是否为空boolEmpty(DLinkList L){if(L-nextL)// 如果 L 的 next 指向自己说明只有头结点returntrue;elsereturnfalse;}// 3. 判断结点 p 是否为循环双链表的表尾结点boolisTail(DLinkList L,DNode*p){if(p-nextL)// 如果 p 的 next 指向了头结点returntrue;elsereturnfalse;}2.2.3 循环双链表的插入与删除彻底消灭 NULL 边界特判循环双链表最大的好处就是不需要写if (p-next ! NULL)这种复杂的防崩溃代码了循环双链表的后插操作// 在 p 结点之后插入 s 结点boolInsertNextDNode(DNode*p,DNode*s){if(pNULL||sNULL)returnfalse;s-nextp-next;// 1. s 的 next 先连上 p 的后继p-next-priors;// 2. 【无需判空】因为 p-next 永远不可能是 NULL要么是后继结点要么是头结点s-priorp;// 3. s 的 prior 指向 pp-nexts;// 4. p 的 next 指向 sreturntrue;}为什么不需要判空了在普通双链表中如果 p 是表尾那么 p-next 是 NULL访问 NULL-prior 会崩溃。但在循环双链表中就算 p 是表尾它的 next 指针也是指向头结点 L 的直接修改 L-prior 是绝对安全的。循环双链表的删除后继结点// 删除 p 结点的后继结点 qboolDeleteNextDNode(DNode*p){if(pNULL)returnfalse;DNode*qp-next;if(qL)returnfalse;// 如果要删的是头结点本身不行。注意这里换成 L因为 p-next 永远不会是 NULL。p-nextq-next;// 1. p 越过 q连向下下个q-next-priorp;// 2. 【无需判空】 q 的下下个的 prior 直接指回 pfree(q);returntrue;}2.2.4 循环链表的巧妙优化指向表尾传统做法L 指向头结点。想在尾部插入必须先从头遍历一圈才能找到尾巴时间复杂度 O(n)。✅优化做法让头指针 L 指向表尾结点而不是头结点。此时找表头因为链表是循环的表尾结点的 next 指向就是头结点因此找头结点的时间复杂度变成了 O(1)。找表尾指针 L 自己就指着表尾所以找表尾的时间复杂度变成了 O(1)考题应用如果题目要求你频繁地在表尾插入元素你可以定义一个 tail 尾指针或者直接把 L 指向表尾这样尾插法就能从普通链表的 O(n) 直接优化到 O(1)。2.3 对比总结为了方便记忆这里总结了普通链表与循环链表判空、判尾的核心规则链表类型结构体特点如何判断空表如何判断表尾结点 p普通单链表尾结点 next NULLL-next NULLp-next NULL循环单链表尾结点 next 头结点L-next Lp-next L普通双链表头 prior NULL尾 next NULLL-next NULLp-next NULL循环双链表头 prior 尾尾 next 头L-next Lp-next L2.4 循环链表操作的时间复杂度总结在考试中遇到循环链表的复杂度选择题请直接对号入座循环单链表头指针 L 指向头结点查找/按值查找O(n)按位插入/删除找到前驱结点后操作O(n)在表头插入/删除已知头结点O(1)在表尾插入需要找尾O(n) →优化若 L 指向尾结点则为 O(1)循环双链表头指针 L 指向头结点查找/按值查找O(n)在已知结点 p 后插/删除后继O(1) (无需判空逻辑极简)在表头插入/删除O(1)在表尾插入/删除O(n) →优化若 L 指向尾结点则为 O(1)【高级推导】为什么 L 指向尾结点时表头操作依然是 O(1)如果 L 指向表尾那么表头就是 L-next。在循环链表中头结点的引用不用单独维护直接通过尾结点就可以一步拿到头结点。结语循环链表本质上是把NULL 终止改成了回到起点终止。理解了这一点你就能明白为什么循环链表的遍历是用 p ! L 而不用 p ! NULL也就能理解为什么循环双链表可以省略繁琐的 if(p-next ! NULL) 安全判断。掌握好这些规律循环链表相关的代码题就能轻松拿满分