目录一、链表的分类总览1.1 单向链表单链表1.2 双向链表1.3 带头结点 vs 不带头结点1.4 循环链表二、单向循环链表详解三、双向链表 双向循环链表四、各链表对比总结五、带头双向循环链表实现5.1 接口函数定义5.2 初始化 / 销毁 / 打印 / 查找5.3 插入5.4 删除5.5 头尾插入删除5.6 测试代码5.7 题目巩固一、链表的分类总览链表可以从两个维度划分指针方向单向链表、双向链表是否循环循环链表、非循环链表是否带头结点带头结点、不带头结点三个维度组合一共产生8 种链表✅ 学习重点考试与工程实践重点掌握 3 种带头结点单链表、不带头结点单链表、双向循环链表吃透这 3 种剩下的组合结构很容易举一反三。1.1 单向链表单链表单向链表每个结点只包含两部分数据域data后继指针nextnext保存下一个结点的地址最后一个结点next NULL代表链表结束特点只能从前往后遍历缺点想找当前结点的前驱结点必须从头遍历时间复杂度 O(n)如果只知道 pos 指针无法直接在 pos 前面插入、删除结点。1.2 双向链表双向链表结点多了一个前驱指针prev。 结点结构定义typedef int DLDataType; typedef struct DListNode { DLDataType data; // 存放数据 struct DListNode* prev; // 前驱指针指向前一个结点 struct DListNode* next; // 后继指针指向后一个结点 }DNode, *DLinkList;优点可以向前、向后双向遍历拿到当前结点直接找前驱O(1)在 pos 结点前插入、删除 pos 结点操作更方便。缺点每个结点多占一个指针的内存尾结点查找依然麻烦尾插尾删效率低。1.3 带头结点 vs 不带头结点不带头结点头指针直接指向第一个存数据的结点。链表为空时头指针 NULL。 缺点对第一个结点做插入 / 删除操作需要单独处理头指针代码分支多。带头结点头指针指向一个不存储有效数据的头结点。链表为空时头结点依然存在。 优点所有结点的插入删除逻辑统一不需要特殊处理第一个结点代码更简洁工程上优先使用带头结点。1.4 循环链表普通链表尾结点nextNULL循环链表尾结点的 next 不再置空而是指向头结点形成环形。单向循环链表尾结点next指向头结点。双向循环链表尾结点next指向头结点头结点prev指向尾结点。二、单向循环链表详解单向循环链表和普通单链表大部分逻辑一致主要有两处核心区别① 初始化逻辑不同普通单链表初始化头结点next NULL循环单链表初始化头结点的next指向自己。// 普通单链表初始化 void InitList(LinkList L){ L BuyListNode(-1); L-next NULL; } // 单向循环链表初始化 void InitCList(CLinkList L){ L BuyCListNode(-1); L-next L; // 头结点指向自己 }② 遍历终止条件不同普通单链表cur ! NULL遇到空指针结束。循环单链表cur ! L绕一圈回到头结点就结束。// 普通单链表求长度 int ListSize(LinkList L){ int size 0; ListNode* cur L-next; while(cur){ size; cur cur-next; } return size; } // 单向循环链表求长度 int CListSize(CLinkList L){ int size 0; CListNode* cur L-next; while(cur ! L){ // 回到头结点停止 size; cur cur-next; } return size; }⚠️重点循环链表不能用cur NULL判断结束否则会无限循环三、双向链表 双向循环链表普通双向链表头结点prev NULL尾结点next NULL缺点尾插、尾删需要遍历找到尾结点复杂度 O(n)带头双向循环链表结构特点头结点的prev指向尾结点尾结点的next指向头结点链表为空时头结点prev和next都指向自身✅ 两大核心优势尾插、尾删O(1)不需要遍历直接通过L-prev拿到尾结点任意位置插入、删除逻辑简单不需要判断尾结点nextNULL边界。四、各链表对比总结表格链表类型优点缺点适用场景带头单链表结构简单代码好写查找前驱O(n)尾插尾删O(n)简单场景只需要头插、头删双向链表可双向遍历查找前驱O(1)尾结点查找慢结点多占内存需要频繁向前查找但很少尾操作单向循环链表可以环形遍历只能单向尾操作依旧麻烦环形队列、约瑟夫环问题带头双向循环链表头尾操作O(1)任意位置插入删除高效结点内存开销最大STL list工程最常用五、带头双向循环链表实现5.1 接口函数定义#pragma once // DCList.h #include stdio.h #include stdlib.h #include assert.h typedef int DCLDataType; typedef struct DCListNode { DCLDataType data; // 存储数据元素的值 struct DCListNode* prev; // 存放前驱结点的指针 struct DCListNode* next; // 存放后继结点的指针 }DCListNode; // 链表初始化 DCListNode* DCListInit(); // 销毁链表 void DCListDestroy(DCListNode* L); // 获取链表的下标i的结点 DCListNode* DCLListGetElem(DCListNode* L, int i); // 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x); // 删除pos位置的结点 void DCListDelete(DCListNode* pos); // 头插 void DCListPushFront(DCListNode* L, DCLDataType x); // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x); // 头删 void DCListPopFront(DCListNode* L); // 尾删 void DCListPopBack(DCListNode* L); // 打印链表中的元素 void DCListPrint(DCListNode* L);5.2 初始化 / 销毁 / 打印 / 查找#include DCList.h // 创建一个新结点 DCListNode* BuyDCListNode(int data) { // 不能创建一个LNode的结构体变量因为局部变量出了作用域就销毁了 // 所以这里用malloc从堆上动态申请结点并检测是否申请成功 DCListNode* newNode (DCListNode*)malloc(sizeof(DCListNode)); if (NULL newNode) { printf(BuyListNode失败!!!\n); exit(-1); } // 申请成功后对结点中的数据域和指针域进行初始化 newNode-data data; newNode-next NULL; newNode-prev NULL; return newNode; } // 链表初始化 DCListNode* DCListInit() { DCListNode* L BuyDCListNode(-1); L-next L; L-prev L; return L; } // 销毁链表 void DCListDestroy(DCListNode* L) { assert(L); DCListNode* cur L-next; while (cur ! L) { DCListNode* next cur-next; free(cur); cur next; } free(L); } // 获取链表的下标i的结点 DCListNode* DCLListGetElem(DCListNode* L, int i) { assert(L); assert(i 0); //从链表头结点开始逐个往后找第i个结点 DCListNode* cur L-next; int j 0; while (cur ! L j i) { cur cur-next; j; } //ji说明没有第i个结点参数i非法 assert(j i); return cur; } // 打印链表中的元素 void DCListPrint(DCListNode* L) { //从前往后打印链表 // printf(头结点-); DCListNode* cur L-next; while (cur ! L) { printf(%d-, cur-data); cur cur-next; } printf(\n); //从后往前打印链表 cur L-prev; while (cur ! L) { printf(%d-, cur-data); cur cur-prev; } printf(\n); }5.3 插入在 pos 结点之后插入一个新结点 newNode这里要改四个指针的链接关系要注意的是一定不能先动pos-next newNode否则就会找不到 pos 的后继结点。建议把pos-next newNode放到最后就不会出乱子。pos 可以指向的任意结点 (包括头结点)不需要考虑 pos 前一个或者后一个为空的情况。如果是双向链表 (非循环)要注意的是 pos 为尾结点时需要考虑 pos-next 为空的情况并且 pos 不能为头结点。// 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x) { assert(pos); DCListNode* newNode BuyDCListNode(x); ////无关顺序 //DCListNode* posNext pos-next; //pos-next newNode; //newNode-prev pos; //newNode-next posNext; //posNext-prev newNode; //注意顺序 newNode-next pos-next; pos-next-prev newNode; pos-next newNode; newNode-prev pos; }5.4 删除这里改动两个指针链接关系即可注意一定要画图捋清楚指针间的关系否则很容易乱这两个链接指针关系没有前后顺序。pos 可以指向除了头结点以外的任意结点不需要考虑 pos 前一个或者后一个为空的情况。如果是双向链表 (非循环)要注意的是 pos 为尾结点时需要考虑 pos-next 为空的情况。// 删除pos位置的结点 void DCListDelete(DCListNode* pos) { assert(pos); pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); }5.5 头尾插入删除头尾插入删除可以复用上面的DCListInsert和DCListDelete实现// 头插 void DCListPushFront(DCListNode* L, DCLDataType x) { assert(L); DCListInsert(L, x); } // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x) { assert(L); DCListInsert(L-prev, x); } // 头删 void DCListPopFront(DCListNode* L) { assert(L); assert(L-next ! L);//空 DCListDelete(L-next); } // 尾删 void DCListPopBack(DCListNode* L) { assert(L); assert(L-next ! L);//空 DCListDelete(L-prev); }5.6 测试代码// DCList.c #include DCList.h int main() { // 以头插法创建链表 DCListNode* L DCListInit(); // 头插 DCListInsert(L, 1); DCListInsert(L, 2); DCListInsert(L, 3); DCListInsert(L, 4); DCListPrint(L); // 尾插 DCListInsert(L-prev, 5); DCListInsert(L-prev, 6); DCListInsert(L-prev, 7); DCListInsert(L-prev, 8); DCListPrint(L); // 头删 DCListDelete(L-next); DCListDelete(L-next); DCListPrint(L); // 尾删 DCListDelete(L-prev); DCListDelete(L-prev); DCListPrint(L); // 中间插入 DCListInsert(DCListGetElem(L, 2), 100); DCListPrint(L); // 中间删除 DCListDelete(DCListGetElem(L, 2)); DCListPrint(L); DCListDestroy(L); return 0; }5.7 题目巩固题12023 年 408 选择题 02现有非空双向链表 L其结点结构为|prev|data|next|prev 是指向直接前驱结点的指针next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点非尾结点之后插入指针 s 指向的新结点则在执行了语句序列s-nextp-next; p-nexts;后下列语句序列中还需要执行的是。A.s-next-prevp; s-prevp;B.p-next-prevs; s-prevp;C.s-prevs-next-prev; s-next-prevs;D.p-next-prevs-prev; s-next-prevp;答案C解析设 p 原来的后继结点为q。 题目已经执行两句s-next p-next;→s-next qs 的后继指向 qp-next s;→ p 的后继改成指向 s重点现在p-next已经不再是 q变成 s 了双向链表插入还需要完成两件事① s 的前驱指向 p ② q 的前驱指向 s。现在q s-nexts-next-prev就是q-prev而q-prev本来就是 p。s-prev s-next-prev;等价于s-prev p;完成①s-next-prev s;等价于q-prev s;完成②❌选项 B 错因p-next-prevs;此时p-next是 s变成s-prevs逻辑错误。题22016 408 选择题 02已知一个带有表头结点的双向循环链表 L结点结构为 | prev|data|next|其中 prev 和 next 分别是指向其直接前驱和直接后继结点的指针。现要删除指针 p 所指的结点正确的语句序列是____。A.p-next-prevp-prev; p-prev-nextp-prev; free (p);B.p-next-prevp-next; p-prev-nextp-next; free (p);C.p-next-prevp-next; p-prev-nextp-prev; free (p);D.p-next-prevp-prev; p-prev-nextp-next; free (p);答案D解析双向循环链表删除 p 结点只需要让 p 的前驱、后继结点互相连上p-next-prev p-prev;p 后面结点的prev指向 p 前面的结点。p-prev-next p-next;p 前面结点的next指向 p 后面的结点。free(p);释放 p 结点。这两行语句没有先后顺序因为两行赋值读取的p-prev、p-next都没有被修改不会覆盖原值。❌A第二句p-prev-nextp-prev前驱结点的 next 错误指向 p 的前驱❌B、Cp-next-prevp-next明显赋值对象错误。题3已知头指针 h 指向一个带头结点的非空单循环链表结点结构为|data|next|其中 next 是指向直接后继结点的指针p 是尾指针q 是临时指针。现要删除该链表的第一个元素正确的语句序列是 ()。A.h-next h-next-next; q h-next; free(q);B.q h-next; h-next h-next-next; free(q);C.q h-next; h-next q-next; if(p ! q)p h; free(q);D.q h-next; h-next q-next; if(p q)p h; free(q);答案D解析链表带头结点单循环链表h 头结点p 保存尾结点地址删除第一个数据结点。步骤拆解q h-next;先用 q 保存待删除的首元结点如果先改 h-next就找不到待删结点h-next q-next;头结点跳过旧首元结点指向新的第一个数据结点特殊情况链表只有 1 个有效结点。此时待删结点 q 既是首元结点也是尾结点p q。删除之后链表只剩头结点尾指针 p 必须更新为 h。 条件if(p q) p h;free(q);释放结点❌A先修改h-nextq 拿到的是新结点释放错结点❌B没有维护尾指针 p。当链表只有 1 个结点时p 仍然指向已经 free 的结点野指针❌C条件写反if(p ! q)ph只会在多个结点时修改尾指针单个结点场景不会更新 p。