写链表这题目我太熟悉了。不管是大学课程设计、考研数据结构还是找工作时被面试官追问单链表、双链表、循环链表这几兄弟基本是绕不开的存在。刚开始学的时候很多人会觉得“这不就是一个个结点串起来嘛”但真到动手写代码才发现指针满天飞改着改着就“断链”再不然就是遍历死循环。这篇就把我写“单/双链表循环单/双链表C语言”这套代码的完整思路、代码细节和踩坑经验全盘托出照着写一遍不敢说你立刻变成链表高手但至少下次再见到“不带头结点的单链表逆序”这种题心里是有底的。写这个项目之前我其实先给自己提了一个问题链表这东西到底在练什么表面上是练“结构体指针动态内存分配”实际上练的是对内存中“地址关系”的理解。数组是一片连续内存下标随手能算链表是散落在堆上的一个个结点靠指针指来指去。你只有真的把指针变量的值、指针指向的地址、指针解引用这几个概念揉碎了才算是入门了C语言。所以这个项目我选了最经典的四种形态单链表、双链表、循环单链表、循环双链表并且全部用C语言实现。为什么用C而不是Java或Python因为C语言里没有对象引用这种说法一切都是指针你需要自己malloc、自己free没人帮你管理内存这反而最能看清链表的本质。1. 四种链表形态拆解先搞清楚项目到底要做什么1.1 单链表、双链表、循环链表是怎么一步步“变形”的我从一个最简单的比喻讲起。单链表就好比一支“只准向后看”的队伍每个人手里拿着一张纸条上面写着下一个人的位置。你想找队伍里的第10个人只能从第1个人开始一个一个往后问因为除了“下一个人”之外你对其他信息一无所知。双链表则是在这个基础上给每个人多了一张纸条写的是“前一个人的位置”。这样一来队伍既能从头往后走也能从尾往前走。代价是每个结点多了一个指针字段本质是用空间换时间。循环单链表就是让队伍最后一个人的纸条不再写“空”而是重新指向第一个人形成一个环。好处在于你可以从任意一个结点出发遍历完整支队伍而不是必须从头开始。循环双链表则是“首尾相连前后双向”四个方向都能走到。它其实是双链表的“环形版本”在实现操作系统的任务队列、游戏实体管理等场景中非常常见。四种结构放在一张表里看就非常清晰结构结点字段最后一个结点的next第一个结点的prev适用场景单链表data, nextNULL无简易栈、多项式相加、邻接表双链表data, prev, nextNULLNULL需要频繁前驱后继访问的场景循环单链表data, next指向头结点/首结点无轮询调度、约瑟夫环循环双链表data, prev, next指向首结点指向尾结点缓存管理LRU、编辑器撤销栈1.2 为什么这个题目是C语言课程设计与面试的常客在我看过的各个学校课程设计题目里链表基本是“万能底座”。你看到“网吧计费管理小项目”、“虚拟存储器管理”、“学生成绩管理系统”剥开外观核心数据结构都是链表。为什么因为这类业务的数据量不确定会频繁插入和删除而链表在这两件事上恰恰是强项。数组插入中间位置需要搬动后面所有元素链表只需要改两个指针代价是O(1)级别的。面试官喜欢问链表图的其实是另外两件事。第一链表是递归和指针的天然训练场特别是“单链表逆序”这种题能同时考察你的指针操作熟练度和边界条件意识。第二链表相关题目容易扩展出进阶问题比如“如何判断链表有没有环”、“如何找到环的入口”、“如何找中间结点”由浅入深非常容易判断一个人的水平。换句话说要么你被单链表的基本操作卡住要么在快慢指针这种经典解法上露馅。我在设计这个项目时没有把四种链表拆成四个完全独立的程序而是统一采用“带头结点”的风格先实现一套单链表再在它基础上扩展双链表最后改造成循环链表。这样做的原因是带头结点能让空表和非空表的处理逻辑保持统一避免在插入删除时单独判“是不是第一个结点”代码量能少三分之一错误率也明显下降。2. 数据结构定义与关键设计决策动手之前的必修课2.1 结点结构体怎么定义单链表和双链表的三行代码差别链表的底层单位是结点C语言里用结构体表达。单链表结点非常简单typedef struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个结点 } Node;注意这里的写法struct Node *next里的struct Node是自引用这在C语言里是被允许的。不能写成Node *next因为typedef还没生效。双链表多了一个前驱指针typedef struct DNode { int data; // 数据域 struct DNode *prev; // 指向前一个结点 struct DNode *next; // 指向下一个结点 } DNode;数据域我用的是int这是为了方便课程设计和刷题。但如果你要拿它做正经项目比如存储学生信息、管理字符串更通用的写法是把数据域换成void *或者封装一个包含长度信息的结构体。我在这套代码里统一用int成本和可读性都更合适。2.2 带头结点还是不带头结点这是一个争论不休的问题链表初学者最困惑的一个点就是为什么要有“头结点”这种东西。我先说结论推荐带头结点尤其是你刚开始学、还在找手感的时候。头结点是一个“哨兵结点”它本身不存有效数据只作为链表起点存在。它的好处有三点。第一空表和非空表的判断统一了。带头结点时空表的判断是head-next NULL不带头结点时空表的判断是head NULL。看起来差不多但涉及到插入和删除操作时差别就大了。带头结点后在头部插入新结点不需要修改头指针本身因为头指针一直指向那个哨兵结点。不带头结点的话你要么使用二级指针Node **head要么让插入函数返回新头指针否则在头部插入的结点根本“挂”不上去。第二删除操作不用特殊处理“删除第一个元素”的情况。不带头结点的链表删除第一个结点时需要把头指针指向第二个结点这就要求删除函数能修改头指针。第三循环链表里头结点可以给你提供一个稳定的遍历终止点。循环单链表的遍历条件是p-next ! head如果没有头结点你得额外拿一个“起始结点”变量来标记麻烦不少。那有没有场景必须用不带头结点也有。比如某些面试题明确规定“不带头结点”比如“不带头结点的单链表逆序”这时候你不能依赖哨兵必须老老实实用指针操作。我的建议是先把带头结点的版本写熟练再自己改造一版不带头结点的彻底搞懂“为什么带头结点能简化操作”而不是只会背代码。2.3 遍历终止条件的三种写法决定了你会不会死循环链表代码里最隐蔽的坑就是遍历循环的终止条件。我总结成三句话普通单链表/双链表遍历到最后一个结点p ! NULL因为最后一个结点的next是NULL带头结点的循环链表遍历p-next ! head当回到头结点时停止不带头结点的循环链表遍历先记录start直到p-next start停止经常有人把普通链表的p ! NULL直接搬到循环链表里结果就是指针永远等不到NULL因为循环链表的最后一个结点指向的是头结点于是程序一头扎进死循环CPU风扇开始起飞。这个问题我在后面“常见问题”部分还会细聊。3. 全套操作代码从初始化到销毁的可复用实现3.1 单链表的基本操作创建、插入、删除、遍历、逆序下面这段代码是我自己写项目时反复打磨过的版本没有花哨的宏定义就是朴素的实现。建议你在编译器里自己敲一遍不要直接复制粘贴敲的过程就是建立肌肉记忆的过程。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 创建带头结点的空链表 Node *initList(void) { Node *head (Node *)malloc(sizeof(Node)); if (head NULL) { printf(内存分配失败\n); exit(1); } head-next NULL; return head; } // 头插法新结点永远插在头结点后面 void insertAtHead(Node *head, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data value; newNode-next head-next; head-next newNode; } // 尾插法找到最后一个结点在其后追加 void insertAtTail(Node *head, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data value; newNode-next NULL; Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; } // 删除第一个值为 value 的结点成功返回1失败返回0 int deleteByValue(Node *head, int value) { Node *prev head; Node *p head-next; while (p ! NULL) { if (p-data value) { prev-next p-next; free(p); return 1; } prev p; p p-next; } return 0; } // 遍历打印 void printList(Node *head) { Node *p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 单链表逆序经典三指针操作 void reverseList(Node *head) { Node *prev NULL; Node *cur head-next; Node *next NULL; while (cur ! NULL) { next cur-next; cur-next prev; prev cur; cur next; } head-next prev; } // 销毁整个链表防止内存泄漏 void destroyList(Node *head) { Node *p head; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } }头插法的代码每次执行newNode-next head-next; head-next newNode;这两行的顺序绝不能反。如果先执行head-next newNode那原来头结点后面的那一整段链表就断了新结点和旧链表就失去了关联。这种错误非常隐蔽编译器不会报错运行时数据会悄悄丢失。单链表逆序是整个项目里的重中之重。它的核心逻辑是每遍历到一个结点就把它从链上“摘下来”让它指向前一个结点。用prev、cur、next三个指针保证在改变cur-next之前先把原来的后继保存下来。很多人的代码在cur-next prev这一步执行之后就不知道接下来该往哪走了原因就是没有提前保存next。3.2 双链表插入删除两对指针都要处理双链表比单链表多一个前驱指针写起来最直观的感受是“每个操作都要改动两对指针”。插入一个结点时新结点的prev和next都要赋值同时前一个结点的next、后一个结点的prev也都要改。删除操作更麻烦被删除结点的前后两个结点需要互相“牵手”。#include stdio.h #include stdlib.h typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode; DNode *initDList(void) { DNode *head (DNode *)malloc(sizeof(DNode)); if (head NULL) { exit(1); } head-prev NULL; head-next NULL; return head; } // 在结点 pos 后面插入新结点 void insertAfter(DNode *pos, int value) { if (pos NULL) return; DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) { exit(1); } newNode-data value; newNode-prev pos; newNode-next pos-next; if (pos-next ! NULL) { pos-next-prev newNode; } pos-next newNode; } // 删除指定结点 p void deleteNode(DNode *p) { if (p NULL) return; if (p-prev ! NULL) { p-prev-next p-next; } if (p-next ! NULL) { p-next-prev p-prev; } free(p); }这段代码里最关键的是insertAfter中判断pos-next ! NULL这一行。如果pos是最后一个结点pos-next是NULL你不能去访问NULL-prev否则立刻段错误。我第一次写双链表时就在这栽了跟头——在末尾插入程序直接崩后来才知道要先判断。链表的插入删除操作我建议你养成画图的习惯。不要怕麻烦画一个矩形代表结点用箭头代表指针每一步操作把旧箭头擦掉画上新箭头。画到第三遍的时候你就会发现代码基本是顺着箭头“翻译”出来的再也不用来回试错。3.3 循环链表把尾结点和头结点“接起来”循环单链表和循环双链表本质上就是普通链表走完后再回头。定义为循环链表时初始化与普通链表最大的不同是头结点的next要指向自己而不是NULL。#include stdio.h #include stdlib.h typedef struct CNode { int data; struct CNode *next; } CNode; // 初始化循环单链表头结点自己指自己 CNode *initCLinkList(void) { CNode *head (CNode *)malloc(sizeof(CNode)); if (head NULL) { exit(1); } head-next head; return head; } // 判断循环链表是否为空 int isCLinkListEmpty(CNode *head) { return head-next head; } // 尾插法在头结点前插入因为是循环链表头结点的前一个位置就是尾 void insertAtTailCLink(CNode *head, int value) { CNode *newNode (CNode *)malloc(sizeof(CNode)); if (newNode NULL) { exit(1); } newNode-data value; newNode-next head-next; head-next newNode; } // 遍历循环单链表注意终止条件是 p-next head void printCLinkList(CNode *head) { if (isCLinkListEmpty(head)) { printf(空链表\n); return; } CNode *p head-next; while (p-next ! head) { printf(%d , p-data); p p-next; } printf(%d\n, p-data); }循环链表有个很有意思的性质如果你只知道某一个结点的指针你就能遍历整条链表。普通单链表做不到这一点你必须拿到头指针才敢出发。这个性质让循环链表特别适合做“轮询”类任务比如操作系统里的进程时间片轮转调度每次从当前进程出发运行完就跳到下一个进程而不是每次都从头开始找。循环双链表同样经典它只需要在循环单链表的定义上加上prev指针并且让头结点的prev指向尾结点、尾结点的next指向头结点。初始化时typedef struct CDNode { int data; struct CDNode *prev; struct CDNode *next; } CDNode; CDNode *initCDLinkList(void) { CDNode *head (CDNode *)malloc(sizeof(CDNode)); if (head NULL) { exit(1); } head-prev head; head-next head; return head; }这样初始化后头结点的前后指针都指向自己空表判断依然是head-next head没有额外负担。3.4 用循环单链表解决约瑟夫环问题是一道经典组合拳如果你学完循环链表想验证一下自己有没有真懂我推荐你去做约瑟夫环问题。题目描述很简单n个人围成一圈从第一个人开始报数报到m的人出列然后从下一个人重新报数直到最后只剩一个人求最后存活者的编号。这个题用循环单链表实现非常直接。你不需要头结点哨兵核心就是把数到 m 的结点从环上摘掉然后继续往下数。我用循环单链表实现时代码的核心是这个循环// 假设 ringsize 个结点从当前结点开始每次数到 m 删一个 CNode *josephus(CNode *head, int m) { CNode *p head; while (p-next ! p) { // 只剩下一个结点时它自己指向自己 for (int i 1; i m; i) { // 走 m-1 步让 p 指向待删除结点的前一个 p p-next; } CNode *del p-next; p-next del-next; free(del); } return p; }这里还有个小细节如果报数从当前结点算起循环i m而不是i m否则会多走一步删除错误的结点。我当时因为这个问题调试了半天最后画图才发现。你如果自己做建议也画一下第一个人报1所以找待删除结点的前驱只需要走m-1次。3.5 一个能直接编译运行的完整示例前面的代码分成了很多片段为了让你更直观地看到整个项目长什么样我再给一个完整的“单链表 逆序 销毁”的测试程序。这个程序可以直接保存为list_demo.c用gcc list_demo.c -o demo ./demo运行#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *initList(void) { Node *head (Node *)malloc(sizeof(Node)); if (!head) { printf(分配失败\n); exit(1); } head-next NULL; return head; } void insertAtTail(Node *head, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (!newNode) { exit(1); } newNode-data value; newNode-next NULL; Node *p head; while (p-next) { p p-next; } p-next newNode; } void printList(Node *head) { Node *p head-next; while (p) { printf(%d , p-data); p p-next; } printf(\n); } void reverseList(Node *head) { Node *prev NULL; Node *cur head-next; while (cur) { Node *next cur-next; cur-next prev; prev cur; cur next; } head-next prev; } void destroyList(Node *head) { Node *p head; while (p) { Node *tmp p; p p-next; free(tmp); } } int main(void) { Node *list initList(); for (int i 1; i 6; i) { insertAtTail(list, i); } printf(原始链表: ); printList(list); reverseList(list); printf(逆序后: ); printList(list); destroyList(list); return 0; }输出结果应该是一行1 2 3 4 5 6另一行6 5 4 3 2 1。如果运行环境里没有配置C语言编译环境不管是Windows还是Ubuntu虚拟机安装gcc之后基本都能跑。我在Ubuntu上一般用gcc -Wall -g编译加上-Wall会把潜在的警告暴露出来加-g是为了后面用gdb调试时能定位到行号。4. 常见问题与排查技巧那些年我们踩过的坑4.1 段错误十个段错误八个是空指针或野指针链表程序最常见的崩溃就是Segmentation fault。我在帮学弟学妹看代码的时候发现大部分段错误都出在这几种情况第一访问了未初始化或已释放的指针。比如你free(p)之后没有把p置为NULL紧接着又写了p-data这块内存可能已经被系统回收甚至被其他变量占用。解决方法是养成习惯free(p); p NULL;。第二对空链表直接访问head-next-data。如果链表是空的head-next是NULL你再取-data就没法访问了。所以遍历和访问前一定要判断。我一般写while (p ! NULL)而不是while (p)虽然结果一样但显式写出! NULL对初学者更友好避免误以为p本身就是某个值。第三插入删除时没有考虑边界位置。前面双链表pos-next-prev的问题就是典型。边界条件只能用穷举法去练空链表插入、末尾插入、删除第一个结点、删除最后一个结点、链表只剩一个结点。每个分支都跑一遍代码的健壮性就是靠这些“边角料”喂出来的。如果段错误已经发生我建议用gdb。编译时加-g选项然后gcc -g -o demo list_demo.c gdb ./demo进入gdb后输入run程序崩溃时输入bt就能看到函数调用栈。再输入frame定位到具体行号然后print p、print head-next看哪个指针的值不对。这个流程练熟之后排查链表的bug会快很多。4.2 断链插入顺序不对整条链表就“腰斩”了断链是指链表中的某一段因为错误操作丢失了引用结点还在内存里但你已经没有指针能走到它。这类问题不会直接崩溃而是表现为“打印到一半就没了”或者“插入的数据找不到”。举一个最典型的反例。某次我在尾插法里这样写Node *p head; p p-next; Node *newNode createNode(value); newNode-next p-next; p-next newNode;如果p恰好是最后一个结点p-next是NULL这段代码没问题。但如果p之后还有数据p-next指向原来的后续结点这逻辑也没错。错的是另一种忘了把newNode-next先接到后续结点上直接p-next newNode这样的话原本在p后面的所有结点全部丢失链表从中间断掉了。正确的插入操作顺序永远是先把新结点的指针“连到”后面的结点再把前一个结点的指针“改到”新结点。先接后断就不会丢数据。这个规则对所有链表插入都适用包括双链表。你可以把这句话抄在代码注释里或者刻在脑子里。4.3 死循环循环链表最经典的折磨循环链表为什么会死循环我前面已经提到了终止条件的问题。这里补充一个容易出错的操作——在循环链表中搜索某个值。如果你用普通链表那套while (p ! NULL)永远找不到出口。正确写法是CNode *findValue(CNode *head, int target) { CNode *p head-next; while (p ! head) { if (p-data target) { return p; } p p-next; } return NULL; }注意这个循环默认了p最终能等于head。如果链表本身已经被污染某个结点的next被改成NULL你又会提前终止如果某个结点的next被改成了环内的其他结点而不是头结点你还是会死循环。排查死循环时我常用的办法是在循环里加一个计数器打印走到第几圈比如if (count 100000) break;先跳出死循环再回头检查指针指向。这种临时调试代码加完记得删掉。4.4 内存泄漏malloc 和 free 必须“数量守恒”C语言手写链表内存泄漏几乎是必然经历的。原因很简单你malloc了多少次就该free多少次。但在插入、删除、销毁的代码里经常顾此失彼。尤其是删除操作很多人只改了指针忘了free(p)结果被删的结点变成“孤儿”还在堆上占着位置。检查内存泄漏有两个思路。第一个思路用Valgrind。在Ubuntu上安装后执行valgrind --leak-checkfull ./demo如果输出里有definitely lost信息说明有内存没释放它会告诉你泄漏发生的位置很方便。第二个思路自己检查。每次写删除结点、销毁链表、程序退出这三个位置数一下你的free和malloc是不是能对得上。销毁链表时不要只释放头结点要遍历整条链逐个free。我见过不少同学只free(head)看起来程序不崩溃但每个结点都泄漏了。还有一个常见的“二次释放”问题你删除一个结点时把它free了但后面遍历时又走到它再次free。这会导致堆管理器的元数据被破坏程序可能当场崩溃也可能在很晚之后才出现诡异行为。防止二次释放的办法除了前面提到的free后置NULL更重要的是删除时一定先把前驱结点的next改好别让后续代码还能访问到已释放的结点。链表这种数据结构代码量不大但每一行都藏着指针的脾气。写的时候别急先把图画明白再把四种结构的初始化、插入、删除、销毁各写一遍。循环链表和双链表可以在单链表的基础上改改完你会发现它们之间其实没有本质区别只是“从哪来、到哪去”的问题。我个人在这些代码上花的时间不少但也正因为被段错误和断链折磨过现在看到任何链表题目第一反应都是画指针箭头而不是直接写代码。你也试试这个习惯效果比背十遍代码都好。 
长河君 · 2026/10/3 1:53:27 · 阅读 1.2k C语言链表详解：单链表、双链表与循环链表实现与调试
写链表这题目我太熟悉了。不管是大学课程设计、考研数据结构还是找工作时被面试官追问单链表、双链表、循环链表这几兄弟基本是绕不开的存在。刚开始学的时候很多人会觉得“这不就是一个个结点串起来嘛”但真到动手写代码才发现指针满天飞改着改着就“断链”再不然就是遍历死循环。这篇就把我写“单/双链表循环单/双链表C语言”这套代码的完整思路、代码细节和踩坑经验全盘托出照着写一遍不敢说你立刻变成链表高手但至少下次再见到“不带头结点的单链表逆序”这种题心里是有底的。写这个项目之前我其实先给自己提了一个问题链表这东西到底在练什么表面上是练“结构体指针动态内存分配”实际上练的是对内存中“地址关系”的理解。数组是一片连续内存下标随手能算链表是散落在堆上的一个个结点靠指针指来指去。你只有真的把指针变量的值、指针指向的地址、指针解引用这几个概念揉碎了才算是入门了C语言。所以这个项目我选了最经典的四种形态单链表、双链表、循环单链表、循环双链表并且全部用C语言实现。为什么用C而不是Java或Python因为C语言里没有对象引用这种说法一切都是指针你需要自己malloc、自己free没人帮你管理内存这反而最能看清链表的本质。1. 四种链表形态拆解先搞清楚项目到底要做什么1.1 单链表、双链表、循环链表是怎么一步步“变形”的我从一个最简单的比喻讲起。单链表就好比一支“只准向后看”的队伍每个人手里拿着一张纸条上面写着下一个人的位置。你想找队伍里的第10个人只能从第1个人开始一个一个往后问因为除了“下一个人”之外你对其他信息一无所知。双链表则是在这个基础上给每个人多了一张纸条写的是“前一个人的位置”。这样一来队伍既能从头往后走也能从尾往前走。代价是每个结点多了一个指针字段本质是用空间换时间。循环单链表就是让队伍最后一个人的纸条不再写“空”而是重新指向第一个人形成一个环。好处在于你可以从任意一个结点出发遍历完整支队伍而不是必须从头开始。循环双链表则是“首尾相连前后双向”四个方向都能走到。它其实是双链表的“环形版本”在实现操作系统的任务队列、游戏实体管理等场景中非常常见。四种结构放在一张表里看就非常清晰结构结点字段最后一个结点的next第一个结点的prev适用场景单链表data, nextNULL无简易栈、多项式相加、邻接表双链表data, prev, nextNULLNULL需要频繁前驱后继访问的场景循环单链表data, next指向头结点/首结点无轮询调度、约瑟夫环循环双链表data, prev, next指向首结点指向尾结点缓存管理LRU、编辑器撤销栈1.2 为什么这个题目是C语言课程设计与面试的常客在我看过的各个学校课程设计题目里链表基本是“万能底座”。你看到“网吧计费管理小项目”、“虚拟存储器管理”、“学生成绩管理系统”剥开外观核心数据结构都是链表。为什么因为这类业务的数据量不确定会频繁插入和删除而链表在这两件事上恰恰是强项。数组插入中间位置需要搬动后面所有元素链表只需要改两个指针代价是O(1)级别的。面试官喜欢问链表图的其实是另外两件事。第一链表是递归和指针的天然训练场特别是“单链表逆序”这种题能同时考察你的指针操作熟练度和边界条件意识。第二链表相关题目容易扩展出进阶问题比如“如何判断链表有没有环”、“如何找到环的入口”、“如何找中间结点”由浅入深非常容易判断一个人的水平。换句话说要么你被单链表的基本操作卡住要么在快慢指针这种经典解法上露馅。我在设计这个项目时没有把四种链表拆成四个完全独立的程序而是统一采用“带头结点”的风格先实现一套单链表再在它基础上扩展双链表最后改造成循环链表。这样做的原因是带头结点能让空表和非空表的处理逻辑保持统一避免在插入删除时单独判“是不是第一个结点”代码量能少三分之一错误率也明显下降。2. 数据结构定义与关键设计决策动手之前的必修课2.1 结点结构体怎么定义单链表和双链表的三行代码差别链表的底层单位是结点C语言里用结构体表达。单链表结点非常简单typedef struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个结点 } Node;注意这里的写法struct Node *next里的struct Node是自引用这在C语言里是被允许的。不能写成Node *next因为typedef还没生效。双链表多了一个前驱指针typedef struct DNode { int data; // 数据域 struct DNode *prev; // 指向前一个结点 struct DNode *next; // 指向下一个结点 } DNode;数据域我用的是int这是为了方便课程设计和刷题。但如果你要拿它做正经项目比如存储学生信息、管理字符串更通用的写法是把数据域换成void *或者封装一个包含长度信息的结构体。我在这套代码里统一用int成本和可读性都更合适。2.2 带头结点还是不带头结点这是一个争论不休的问题链表初学者最困惑的一个点就是为什么要有“头结点”这种东西。我先说结论推荐带头结点尤其是你刚开始学、还在找手感的时候。头结点是一个“哨兵结点”它本身不存有效数据只作为链表起点存在。它的好处有三点。第一空表和非空表的判断统一了。带头结点时空表的判断是head-next NULL不带头结点时空表的判断是head NULL。看起来差不多但涉及到插入和删除操作时差别就大了。带头结点后在头部插入新结点不需要修改头指针本身因为头指针一直指向那个哨兵结点。不带头结点的话你要么使用二级指针Node **head要么让插入函数返回新头指针否则在头部插入的结点根本“挂”不上去。第二删除操作不用特殊处理“删除第一个元素”的情况。不带头结点的链表删除第一个结点时需要把头指针指向第二个结点这就要求删除函数能修改头指针。第三循环链表里头结点可以给你提供一个稳定的遍历终止点。循环单链表的遍历条件是p-next ! head如果没有头结点你得额外拿一个“起始结点”变量来标记麻烦不少。那有没有场景必须用不带头结点也有。比如某些面试题明确规定“不带头结点”比如“不带头结点的单链表逆序”这时候你不能依赖哨兵必须老老实实用指针操作。我的建议是先把带头结点的版本写熟练再自己改造一版不带头结点的彻底搞懂“为什么带头结点能简化操作”而不是只会背代码。2.3 遍历终止条件的三种写法决定了你会不会死循环链表代码里最隐蔽的坑就是遍历循环的终止条件。我总结成三句话普通单链表/双链表遍历到最后一个结点p ! NULL因为最后一个结点的next是NULL带头结点的循环链表遍历p-next ! head当回到头结点时停止不带头结点的循环链表遍历先记录start直到p-next start停止经常有人把普通链表的p ! NULL直接搬到循环链表里结果就是指针永远等不到NULL因为循环链表的最后一个结点指向的是头结点于是程序一头扎进死循环CPU风扇开始起飞。这个问题我在后面“常见问题”部分还会细聊。3. 全套操作代码从初始化到销毁的可复用实现3.1 单链表的基本操作创建、插入、删除、遍历、逆序下面这段代码是我自己写项目时反复打磨过的版本没有花哨的宏定义就是朴素的实现。建议你在编译器里自己敲一遍不要直接复制粘贴敲的过程就是建立肌肉记忆的过程。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 创建带头结点的空链表 Node *initList(void) { Node *head (Node *)malloc(sizeof(Node)); if (head NULL) { printf(内存分配失败\n); exit(1); } head-next NULL; return head; } // 头插法新结点永远插在头结点后面 void insertAtHead(Node *head, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data value; newNode-next head-next; head-next newNode; } // 尾插法找到最后一个结点在其后追加 void insertAtTail(Node *head, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data value; newNode-next NULL; Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; } // 删除第一个值为 value 的结点成功返回1失败返回0 int deleteByValue(Node *head, int value) { Node *prev head; Node *p head-next; while (p ! NULL) { if (p-data value) { prev-next p-next; free(p); return 1; } prev p; p p-next; } return 0; } // 遍历打印 void printList(Node *head) { Node *p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 单链表逆序经典三指针操作 void reverseList(Node *head) { Node *prev NULL; Node *cur head-next; Node *next NULL; while (cur ! NULL) { next cur-next; cur-next prev; prev cur; cur next; } head-next prev; } // 销毁整个链表防止内存泄漏 void destroyList(Node *head) { Node *p head; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } }头插法的代码每次执行newNode-next head-next; head-next newNode;这两行的顺序绝不能反。如果先执行head-next newNode那原来头结点后面的那一整段链表就断了新结点和旧链表就失去了关联。这种错误非常隐蔽编译器不会报错运行时数据会悄悄丢失。单链表逆序是整个项目里的重中之重。它的核心逻辑是每遍历到一个结点就把它从链上“摘下来”让它指向前一个结点。用prev、cur、next三个指针保证在改变cur-next之前先把原来的后继保存下来。很多人的代码在cur-next prev这一步执行之后就不知道接下来该往哪走了原因就是没有提前保存next。3.2 双链表插入删除两对指针都要处理双链表比单链表多一个前驱指针写起来最直观的感受是“每个操作都要改动两对指针”。插入一个结点时新结点的prev和next都要赋值同时前一个结点的next、后一个结点的prev也都要改。删除操作更麻烦被删除结点的前后两个结点需要互相“牵手”。#include stdio.h #include stdlib.h typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode; DNode *initDList(void) { DNode *head (DNode *)malloc(sizeof(DNode)); if (head NULL) { exit(1); } head-prev NULL; head-next NULL; return head; } // 在结点 pos 后面插入新结点 void insertAfter(DNode *pos, int value) { if (pos NULL) return; DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) { exit(1); } newNode-data value; newNode-prev pos; newNode-next pos-next; if (pos-next ! NULL) { pos-next-prev newNode; } pos-next newNode; } // 删除指定结点 p void deleteNode(DNode *p) { if (p NULL) return; if (p-prev ! NULL) { p-prev-next p-next; } if (p-next ! NULL) { p-next-prev p-prev; } free(p); }这段代码里最关键的是insertAfter中判断pos-next ! NULL这一行。如果pos是最后一个结点pos-next是NULL你不能去访问NULL-prev否则立刻段错误。我第一次写双链表时就在这栽了跟头——在末尾插入程序直接崩后来才知道要先判断。链表的插入删除操作我建议你养成画图的习惯。不要怕麻烦画一个矩形代表结点用箭头代表指针每一步操作把旧箭头擦掉画上新箭头。画到第三遍的时候你就会发现代码基本是顺着箭头“翻译”出来的再也不用来回试错。3.3 循环链表把尾结点和头结点“接起来”循环单链表和循环双链表本质上就是普通链表走完后再回头。定义为循环链表时初始化与普通链表最大的不同是头结点的next要指向自己而不是NULL。#include stdio.h #include stdlib.h typedef struct CNode { int data; struct CNode *next; } CNode; // 初始化循环单链表头结点自己指自己 CNode *initCLinkList(void) { CNode *head (CNode *)malloc(sizeof(CNode)); if (head NULL) { exit(1); } head-next head; return head; } // 判断循环链表是否为空 int isCLinkListEmpty(CNode *head) { return head-next head; } // 尾插法在头结点前插入因为是循环链表头结点的前一个位置就是尾 void insertAtTailCLink(CNode *head, int value) { CNode *newNode (CNode *)malloc(sizeof(CNode)); if (newNode NULL) { exit(1); } newNode-data value; newNode-next head-next; head-next newNode; } // 遍历循环单链表注意终止条件是 p-next head void printCLinkList(CNode *head) { if (isCLinkListEmpty(head)) { printf(空链表\n); return; } CNode *p head-next; while (p-next ! head) { printf(%d , p-data); p p-next; } printf(%d\n, p-data); }循环链表有个很有意思的性质如果你只知道某一个结点的指针你就能遍历整条链表。普通单链表做不到这一点你必须拿到头指针才敢出发。这个性质让循环链表特别适合做“轮询”类任务比如操作系统里的进程时间片轮转调度每次从当前进程出发运行完就跳到下一个进程而不是每次都从头开始找。循环双链表同样经典它只需要在循环单链表的定义上加上prev指针并且让头结点的prev指向尾结点、尾结点的next指向头结点。初始化时typedef struct CDNode { int data; struct CDNode *prev; struct CDNode *next; } CDNode; CDNode *initCDLinkList(void) { CDNode *head (CDNode *)malloc(sizeof(CDNode)); if (head NULL) { exit(1); } head-prev head; head-next head; return head; }这样初始化后头结点的前后指针都指向自己空表判断依然是head-next head没有额外负担。3.4 用循环单链表解决约瑟夫环问题是一道经典组合拳如果你学完循环链表想验证一下自己有没有真懂我推荐你去做约瑟夫环问题。题目描述很简单n个人围成一圈从第一个人开始报数报到m的人出列然后从下一个人重新报数直到最后只剩一个人求最后存活者的编号。这个题用循环单链表实现非常直接。你不需要头结点哨兵核心就是把数到 m 的结点从环上摘掉然后继续往下数。我用循环单链表实现时代码的核心是这个循环// 假设 ringsize 个结点从当前结点开始每次数到 m 删一个 CNode *josephus(CNode *head, int m) { CNode *p head; while (p-next ! p) { // 只剩下一个结点时它自己指向自己 for (int i 1; i m; i) { // 走 m-1 步让 p 指向待删除结点的前一个 p p-next; } CNode *del p-next; p-next del-next; free(del); } return p; }这里还有个小细节如果报数从当前结点算起循环i m而不是i m否则会多走一步删除错误的结点。我当时因为这个问题调试了半天最后画图才发现。你如果自己做建议也画一下第一个人报1所以找待删除结点的前驱只需要走m-1次。3.5 一个能直接编译运行的完整示例前面的代码分成了很多片段为了让你更直观地看到整个项目长什么样我再给一个完整的“单链表 逆序 销毁”的测试程序。这个程序可以直接保存为list_demo.c用gcc list_demo.c -o demo ./demo运行#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *initList(void) { Node *head (Node *)malloc(sizeof(Node)); if (!head) { printf(分配失败\n); exit(1); } head-next NULL; return head; } void insertAtTail(Node *head, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (!newNode) { exit(1); } newNode-data value; newNode-next NULL; Node *p head; while (p-next) { p p-next; } p-next newNode; } void printList(Node *head) { Node *p head-next; while (p) { printf(%d , p-data); p p-next; } printf(\n); } void reverseList(Node *head) { Node *prev NULL; Node *cur head-next; while (cur) { Node *next cur-next; cur-next prev; prev cur; cur next; } head-next prev; } void destroyList(Node *head) { Node *p head; while (p) { Node *tmp p; p p-next; free(tmp); } } int main(void) { Node *list initList(); for (int i 1; i 6; i) { insertAtTail(list, i); } printf(原始链表: ); printList(list); reverseList(list); printf(逆序后: ); printList(list); destroyList(list); return 0; }输出结果应该是一行1 2 3 4 5 6另一行6 5 4 3 2 1。如果运行环境里没有配置C语言编译环境不管是Windows还是Ubuntu虚拟机安装gcc之后基本都能跑。我在Ubuntu上一般用gcc -Wall -g编译加上-Wall会把潜在的警告暴露出来加-g是为了后面用gdb调试时能定位到行号。4. 常见问题与排查技巧那些年我们踩过的坑4.1 段错误十个段错误八个是空指针或野指针链表程序最常见的崩溃就是Segmentation fault。我在帮学弟学妹看代码的时候发现大部分段错误都出在这几种情况第一访问了未初始化或已释放的指针。比如你free(p)之后没有把p置为NULL紧接着又写了p-data这块内存可能已经被系统回收甚至被其他变量占用。解决方法是养成习惯free(p); p NULL;。第二对空链表直接访问head-next-data。如果链表是空的head-next是NULL你再取-data就没法访问了。所以遍历和访问前一定要判断。我一般写while (p ! NULL)而不是while (p)虽然结果一样但显式写出! NULL对初学者更友好避免误以为p本身就是某个值。第三插入删除时没有考虑边界位置。前面双链表pos-next-prev的问题就是典型。边界条件只能用穷举法去练空链表插入、末尾插入、删除第一个结点、删除最后一个结点、链表只剩一个结点。每个分支都跑一遍代码的健壮性就是靠这些“边角料”喂出来的。如果段错误已经发生我建议用gdb。编译时加-g选项然后gcc -g -o demo list_demo.c gdb ./demo进入gdb后输入run程序崩溃时输入bt就能看到函数调用栈。再输入frame定位到具体行号然后print p、print head-next看哪个指针的值不对。这个流程练熟之后排查链表的bug会快很多。4.2 断链插入顺序不对整条链表就“腰斩”了断链是指链表中的某一段因为错误操作丢失了引用结点还在内存里但你已经没有指针能走到它。这类问题不会直接崩溃而是表现为“打印到一半就没了”或者“插入的数据找不到”。举一个最典型的反例。某次我在尾插法里这样写Node *p head; p p-next; Node *newNode createNode(value); newNode-next p-next; p-next newNode;如果p恰好是最后一个结点p-next是NULL这段代码没问题。但如果p之后还有数据p-next指向原来的后续结点这逻辑也没错。错的是另一种忘了把newNode-next先接到后续结点上直接p-next newNode这样的话原本在p后面的所有结点全部丢失链表从中间断掉了。正确的插入操作顺序永远是先把新结点的指针“连到”后面的结点再把前一个结点的指针“改到”新结点。先接后断就不会丢数据。这个规则对所有链表插入都适用包括双链表。你可以把这句话抄在代码注释里或者刻在脑子里。4.3 死循环循环链表最经典的折磨循环链表为什么会死循环我前面已经提到了终止条件的问题。这里补充一个容易出错的操作——在循环链表中搜索某个值。如果你用普通链表那套while (p ! NULL)永远找不到出口。正确写法是CNode *findValue(CNode *head, int target) { CNode *p head-next; while (p ! head) { if (p-data target) { return p; } p p-next; } return NULL; }注意这个循环默认了p最终能等于head。如果链表本身已经被污染某个结点的next被改成NULL你又会提前终止如果某个结点的next被改成了环内的其他结点而不是头结点你还是会死循环。排查死循环时我常用的办法是在循环里加一个计数器打印走到第几圈比如if (count 100000) break;先跳出死循环再回头检查指针指向。这种临时调试代码加完记得删掉。4.4 内存泄漏malloc 和 free 必须“数量守恒”C语言手写链表内存泄漏几乎是必然经历的。原因很简单你malloc了多少次就该free多少次。但在插入、删除、销毁的代码里经常顾此失彼。尤其是删除操作很多人只改了指针忘了free(p)结果被删的结点变成“孤儿”还在堆上占着位置。检查内存泄漏有两个思路。第一个思路用Valgrind。在Ubuntu上安装后执行valgrind --leak-checkfull ./demo如果输出里有definitely lost信息说明有内存没释放它会告诉你泄漏发生的位置很方便。第二个思路自己检查。每次写删除结点、销毁链表、程序退出这三个位置数一下你的free和malloc是不是能对得上。销毁链表时不要只释放头结点要遍历整条链逐个free。我见过不少同学只free(head)看起来程序不崩溃但每个结点都泄漏了。还有一个常见的“二次释放”问题你删除一个结点时把它free了但后面遍历时又走到它再次free。这会导致堆管理器的元数据被破坏程序可能当场崩溃也可能在很晚之后才出现诡异行为。防止二次释放的办法除了前面提到的free后置NULL更重要的是删除时一定先把前驱结点的next改好别让后续代码还能访问到已释放的结点。链表这种数据结构代码量不大但每一行都藏着指针的脾气。写的时候别急先把图画明白再把四种结构的初始化、插入、删除、销毁各写一遍。循环链表和双链表可以在单链表的基础上改改完你会发现它们之间其实没有本质区别只是“从哪来、到哪去”的问题。我个人在这些代码上花的时间不少但也正因为被段错误和断链折磨过现在看到任何链表题目第一反应都是画指针箭头而不是直接写代码。你也试试这个习惯效果比背十遍代码都好。