很多人学链表卡在第一步不是代码写不出来而是根本没明白链表到底在解决什么问题。我当年学数据结构的时候也一样看严蔚敏那本C语言版教材结构体、指针、malloc看得一头雾水直到自己动手把单链表从零到一实现了一遍才真正理解“节点”和“指针”这两个词的含义。今天这篇内容我尽量用大白话把链表讲透从结构设计到完整代码从单链表到双链表再到循环链表最后把面试和考研里高频的几个考点也捋一遍。不管你是大一正在写实验报告还是准备408数据结构那门课或者工作后回头补基本功这篇都值得看完。1. 为什么学链表之前先想清楚数组的局限1.1 数组的“连续内存”带来什么问题我们天天用的数组本质上是在内存里开辟一块连续的空间。这也意味着如果你想在中间插入一个元素后面的所有元素都得往后挪一步。假设你有一个长度为十万的数组在最后插入一个元素代价可以忽略不计但要在最前面插入一个元素就要把十万个元素全部移动一次时间复杂度是O(n)。这在真实业务里是非常常见的场景比如维护一个消息队列、保存用户的操作历史记录都是频繁地在头部或中间插入数据数组这种结构在这种场景下就显得笨重。而且数组在定义时就得确定长度。如果你用C语言写int arr[100]这个100就不能再变了用动态分配的话扩容时要重新申请一块更大的空间还要把旧数据整体拷贝过去。这个“一次性分配一整块连续空间”的思路天然就跟动态增删的需求有矛盾。1.2 链表用“离散空间”破解连续分配的困局链表的思路完全不同它不要求内存是连续的每个节点各管各的存储位置。节点之间靠“指针”串联起来前一个节点里存着后一个节点的地址就像一串珠子每颗珠子上写着下一颗珠子的位置。这样一来想在中间插入数据只需要改变两个节点的指针方向不需要移动任何其他数据时间复杂度是O(1)只是找到插入位置需要O(n)。删除操作也一样修改一下指针就断了节点之间的连接。用一个通俗的比喻数组像火车车厢每节车厢焊死在轨道上想在中途加一节车厢后面的都得重新编组链表像手拉手的一队人想插队的话只需要让前面的人放开手拉住新来的人新来的人再拉住后面的人整个队伍不用动。这就是为什么链表能成为各种动态数据结构的基石。后面接触的树、图的邻接表存储核心也是链表的思路。1.3 链表的代价空间换时间代价不止一个指针当然天下没有免费的午餐。链表能换来插入删除的高效付出的代价也很明显每个节点都要额外存储一个指针双链表还要存两个内存开销比数组大。无法随机访问。数组可以用下标直接定位到第n个元素链表必须从头开始一个一个往后走。频繁的malloc和free或new和delete会带来内存碎片和管理负担。理解了这几点你再看网上那些“数组和链表怎么选”的讨论心里就有数了。核心就一句话读多、固定容量、随机访问频繁的场景选数组写多、容量动态增长、频繁增删的场景选链表。这也是后面理解HashMap等复杂数据结构的前提。HashMap之所以能高效应对数据量增长正是因为它内部结合了数组的随机访问优势和链表的插入优势。2. 单链表最基础也最核心的形态2.1 节点结构到底怎么定义单链表是最简单的链表形态每个节点只包含两个部分数据域和指向下一个节点的指针。在C语言里是这样定义的typedef struct Node { int data; // 数据域这里以int为例 struct Node *next; // 指针域指向下一个节点 } Node;这里第一眼看上去容易绕的是struct Node *next这个写法。关键理解一句话next是一个指针变量它的类型是“指向这个结构体的指针”它存的是另一个节点的地址。你要访问下一个节点里的数据不是直接拿next而是通过next-data来取。C语言里p-next等价于(*p).next这个箭头符号就是“解引用加取成员”的缩写。我见过很多新手在定义时纠结命名一会儿LNode一会儿LinkList。其实这两种命名区别不大如果用的是严蔚敏教材的风格往往会把节点类型和链表类型分开定义typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;这里LNode表示节点LinkList是“指向LNode的指针”类型等价于LNode *。习惯上用LinkList L表示一个链表头指针用LNode *p表示一个工作指针。理解了这个套路之后你读王道、看408真题里的代码就不会觉得别扭。2.2 创建链表头插法和尾插法的本质区别在“在指定位置插入建立单链表”这个场景里大部分人一开始用的是尾插法。尾插法的逻辑是新节点总是接到链表末尾需要一个指针tail一直指向当前的末尾节点。Node *createByTail(int a[], int n) { Node *head NULL; Node *tail NULL; for (int i 0; i n; i) { Node *s (Node *)malloc(sizeof(Node)); s-data a[i]; s-next NULL; if (head NULL) { head s; tail s; } else { tail-next s; tail s; } } return head; }头插法则完全不同每次把新节点插到链表头部让新节点的next指向原来的头节点。操作虽然只有两三行但效果是数据顺序被颠倒了Node *createByHead(int a[], int n) { Node *head NULL; for (int i 0; i n; i) { Node *s (Node *)malloc(sizeof(Node)); s-data a[i]; s-next head; head s; } return head; }头插法输出结果会反转这是很多人写实验报告时踩的第一个坑。比如输入1,2,3尾插法输出是1,2,3头插法输出是3,2,1。如果你做的是一个排队系统的模拟用头插法建表结果就全反了。而在某些场景里这种反转是有意为之的比如实现链表的原地逆序思路就是遍历原链表的同时用头插法重建一个新链表。判定用什么方法核心看你想要的顺序。2.3 在指定位置插入节点的关键细节插入操作看着简单但边界条件特别多。思路是要在第i个位置插入节点s核心是找到第i-1个位置的节点p然后执行两条语句s-next p-next; p-next s;这两条语句的顺序绝对不能反。先执行p-next s的话s后面原本的链表就丢了因为p-next已经被覆盖你再也找不到原来p后面的节点了。这就像排队时你拉住新来的人结果一松手原来拉着的人跑了。完整实现还需要考虑几个边界情况i是有效位置吗插入前最好判断一下链表长度和位置范围如果领头结点后面详细讲插在第一个位置和插在其他位置代码逻辑一样比较方便如果不领头结点插在头部得单独处理头指针的修改。int insertNode(Node **pHead, int i, int val) { if (i 0 || *pHead NULL) return 0; Node *p *pHead; int pos 1; while (p ! NULL pos i - 1) { p p-next; pos; } if (p NULL) return 0; // 位置超出链表实际长度 Node *s (Node *)malloc(sizeof(Node)); s-data val; s-next p-next; p-next s; return 1; }注意这里函数参数用了Node **pHead也就是“头指针的指针”。为什么要这么麻烦因为如果插入的是第一个位置函数内部就要修改外界的头指针变量C语言传值的话修改只对副本生效传指针的指针才能把修改带出去。这也是一个典型的“二级指针”考点面试里经常有人在这里露怯。3. 带头结点与不带头结点一个经常被忽略的思路设计差异3.1 带头结点到底带的是什么“头”很多教材在讲链表时会默认有一个头结点也就是一个不存有效数据的节点它的next才指向第一个真正存数据的节点。严蔚敏教材里用的LinkList L常常就是带头结点的链表。头结点和头指针是两个不同的概念头指针是链表存在的标志它指向链表的第一个节点头结点是第一个节点之前附加的一个节点数据域通常不设值指针域指向真正的首元节点。为什么要多弄一个空节点出来最大的好处是针对第一个位置的操作和针对中间位置的操作变成了一样的逻辑。不带头结点的链表head指向首元节点你在head处插入需要改head本身你删首元节点也需要改head本身。这逼迫你在所有涉及首元节点的操作上都得写条件判断。带头结点之后头结点永远是头结点插入删除的逻辑统一了代码写起来清爽很多。3.2 不带头结点的场景空间极致省时怎么办那是不是带头结点永远更好也不是。某些算法题为了节省那一个节点的空间或者为了考察你对指针操作的理解深度会故意用不带头结点的链表。比如“判断两个链表是否相交”这类题给的往往是带头结点或不带头结点的混合情况你得自己判断。另外在某些嵌入式、内存极紧张的环境里多一个头结点就是多一份空间开销哪怕只是8字节一个指针的大小积少成多也心疼。不带头结点的链表处理插入时必须专门对i1做特殊处理int insertNoHead(Node **pHead, int i, int val) { Node *s (Node *)malloc(sizeof(Node)); s-data val; if (i 1) { s-next *pHead; *pHead s; return 1; } // 其他位置逻辑与带头结点相同 Node *p *pHead; int pos 1; while (p ! NULL pos i - 1) { p p-next; pos; } if (p NULL) return 0; s-next p-next; p-next s; return 1; }不管头上有没有结点你都要把“第一个位置”单独拎出来考虑。这也解释了为什么很多408真题的代码题给出的链表都是带头结点的——出题人想考算法逻辑而非边界条件的处理。但你自己练习时两种形态都写一遍会明显提升对指针的理解。3.3 清空和销毁最容易遗漏的两个函数链表题里还有两个操作容易被学生忽略一个是“清空”一个是“销毁”。清空是从头到尾把数据节点释放掉只保留头结点如果链表带头结点的话让链表变空销毁是连头结点也释放head置为NULL。两者的区别类似于清空购物车和注销账号。void clearList(Node *head) { Node *p head-next; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } head-next NULL; } void destroyList(Node **pHead) { Node *p *pHead; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } *pHead NULL; }很多人写程序只malloc不free考试时没关系但你在工程项目里这么干内存泄漏的clock会一直跑。尤其是嵌入式或服务端长期运行的程序里泄漏一点点内存都可能最终拖垮整个进程。清空时为什么释放完节点后马上把head-next NULL因为你若不清空指针一旦有人误用这个“已经释放了的头结点”就变成了典型的悬空指针问题。4. 单链表遍历与双链表从只会头到尾到可以倒着走4.1 遍历时最容易踩的坑用head本身当指针很多新手写遍历是这样void printList(Node *head) { while (head ! NULL) { printf(%d , head-data); head head-next; } }功能上讲这没问题但问题是遍历完之后head已经变成了NULL外界的头指针虽然没变但这个函数把参数副本用掉了。你接下来还想用这个链表做别的操作还得重新建一个临时变量来遍历。正确习惯是永远借助另一个工作指针p让头指针一直指向链表的头部void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }这不仅仅是代码习惯的问题在很多递归判断链表长度、查找倒数第k个节点等问题里头指针是否保留决定了你能不能继续操作。保留头指针这个习惯越早养成越好。4.2 单链表的局限催生双链表单链表只有一个next方向导致一个问题你走到某个节点之后想回去找上一个节点做不到只能从头再来。如果业务上经常需要双向遍历比如浏览器的前进后退历史、文本编辑器的撤销重做栈单链表就不够用了。双链表就是每个节点再加一个prev指针指向前驱节点typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;双链表的插入操作看起来代码更多但逻辑上更对称核心还是先处理新节点的前后指针再处理前后节点的连接顺序不能乱。在p节点后面插入s节点s-prev p; s-next p-next; if (p-next ! NULL) { p-next-prev s; } p-next s;注意p如果是最后一个节点p-next是NULL这时p-next-prev这句代码就不能执行所以要加个判空。双链表的删除操作也一样多了一个前驱指针要改但好处是删除某个节点时不需要从头找它的前驱直接通过p-prev就能拿到时间复杂度从O(n)降到了O(1)代码也更优雅p-prev-next p-next; if (p-next ! NULL) { p-next-prev p-prev; } free(p);4.3 循环链表与约瑟夫环问题循环单链表的最后一个节点的next不再指向NULL而是回头指向头结点或第一个节点整个链表变成一个环。循环双链表类似头结点的prev指向表尾节点。判断一个链表是不是循环链表最经典的做法是快慢指针快指针每次走两步慢指针每次走一步如果链表有环两个指针迟早相遇。这个思路不仅用于循环链表判断也是LeetCode“环形链表”这道题的核心解法。约瑟夫环是循环链表一个非常经典的实战案例n个人围成一圈从第一个人开始报数报到m的人出列之后从下一个人重新报数直到所有人出列要求输出出列顺序。这类问题如果用数组模拟每次删除一个人的代价是O(n)总代价O(n²)而用循环链表天然贴合“围成一圈”的结构删除一个人只需要改动两个指针。我当年在实验课上用循环链表写约瑟夫环写完才体会到教材里为什么总用它举例它把循环链表的“遍历一圈”、“删除节点”、“遍历终止条件”三个核心点全训练到了。5. 完整实操手写一个带头结点的单链表工具库5.1 编码之前先画图哪怕只在脑子里画很多人在写链表代码时觉得思路乱根源在于没在脑中画出指针指向关系。我建议你哪怕只是在草稿纸上简单画把每个节点画成一个方块方块的右边引出一条线写着“next”然后手动模拟一遍插入、删除的过程。画过一次之后代码就是照着图翻译基本不会错。对于复杂的链表题我到现在还会用画图来推演边界情况。5.2 一个可直接参考的实验代码框架下面是一个完整可运行的C语言示例包含创建、遍历、插入、删除、清空、销毁全部基于带头结点的单链表。你可以直接复制到本地编译运行建议在此基础上改一改比如头插法反转、按值删除所有匹配的节点这些改动量不大但训练价值很高。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node, *LinkList; // 创建一个带头结点的空链表 LinkList createList() { LinkList head (LinkList)malloc(sizeof(Node)); head-next NULL; return head; } // 尾插法在链表末尾追加值为val的节点 void appendNode(LinkList head, int val) { Node *p head; while (p-next ! NULL) { p p-next; } Node *s (Node *)malloc(sizeof(Node)); s-data val; s-next NULL; p-next s; } // 遍历打印 void printList(LinkList head) { Node *p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 按位置插入位置从1开始 int insertByPos(LinkList head, int i, int val) { Node *p head; int pos 0; while (p ! NULL pos i - 1) { p p-next; pos; } if (p NULL) return 0; // 插入位置不合法 Node *s (Node *)malloc(sizeof(Node)); s-data val; s-next p-next; p-next s; return 1; } // 按位置删除删除成功后返回节点的值失败返回-1表示失败 int deleteByPos(LinkList head, int i, int *value) { Node *p head; int pos 0; while (p-next ! NULL pos i - 1) { p p-next; pos; } if (p-next NULL) return 0; // 第i个节点不存在 Node *del p-next; *value del-data; p-next del-next; free(del); return 1; } // 清空数据节点保留头结点 void clearList(LinkList head) { Node *p head-next; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } head-next NULL; } // 销毁整个链表包括头结点 void destroyList(LinkList *pHead) { Node *p *pHead; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } *pHead NULL; } int main() { LinkList list createList(); int arr[] {1, 2, 3, 4, 5}; for (int i 0; i 5; i) { appendNode(list, arr[i]); } printf(原始链表: ); printList(list); insertByPos(list, 3, 99); printf(在第3个位置插入99: ); printList(list); int val; if (deleteByPos(list, 3, val)) { printf(删除第3个位置的值%d: , val); printList(list); } clearList(list); printf(清空后链表是否为空: ); if (list-next NULL) printf(空\n); destroyList(list); return 0; }这段代码的结构设计上有一个值得注意的地方所有操作都通过头结点进入不需要在main函数里反复修改head本身所以函数参数都可以直接用一级指针LinkList head只有销毁时需要二级指针因为销毁后要把外界的head置空。实验报告里如果设计成这样的分层老师一眼就能看出你对链表的理解到位。5.3 链表逆序手撕高频考题的完整思路链表逆序是一个必考操作。基本思路是用三个指针分别记录当前节点的前驱、当前节点、后继逐个把箭头反向。下面这段代码是“不带头结点”链表的原地逆序逻辑更通用Node *reverseList(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; // 保存后继防止丢失 cur-next prev; // 反转指针 prev cur; cur next; } return prev; // 遍历结束时prev就是新的头节点 }这里最容易犯的错误是反转了前一个节点的指针之后没有先保存cur-next就直接用cur cur-next结果发现cur已经指回前一个节点去了链表就断了。事后你排查这种bug时一定要回到“指针指向关系”去捋而不是瞎试。逆序之后原来链表的最后一个节点成了新链表的头这也是测试时最容易验证的点。6. 常见问题排查与避坑指南6.1 用着用着程序就崩了十大链表崩溃原因对照表链表代码里的崩溃绝大多数都跟指针有关。我把最常见的几类问题和排查思路整理成一张表你调试的时候可以对着找现象常见原因排查与修复思路程序直接Segmentation fault对NULL指针解引用检查是否访问了p-next但p是NULL遍历时死循环链表中存在环检查尾节点的next是否忘了置NULL打印出来的顺序不对头插法建表导致顺序反转按需选择头插法或尾插法删除节点后链表乱套没有先把后续节点地址保存下来删除前用临时指针记录被删节点的后继运行结果随机崩溃访问了已释放的节点悬空指针释放指针后立即置NULL避免二次解引用内存占用只增不减malloc了没free删除和清空时补上free插入位置不对位置下标从0还是1没搞清楚明确约定位置编号统一处理修改链表后外部头指针不变函数参数传值而非传指针的指针需要修改head时用Node **倒数第k个节点找不到没考虑k等于链表长度的情况快慢指针法或先求长度再走反转链表结果只是部分反转没保存cur-next或没更新头指针按三步走逐节点反转最后返回新头这张表是我自己调代码时反复踩过的坑对照着排查能节省大量时间。6.2 调试链表的三个实用技巧第一打印游标。在关键操作前后都打印一下当前节点的地址和数据域用类似printf(p%p, p-data%d\n, p, p-data)的语句能快速定位到哪一步指针断开了。第二画图推演。前面提过遇到复杂的插入删除画图是最有效的。不夸张地说我至今遇到链表相关的bug第一反应还是拿出纸笔画一遍链表当前的连接状态而不是直接在屏幕上看代码。第三最小化测试。链表代码有很强的边界效应空链表、只有一个节点、两个节点、插入到头部、插入到尾部、删除头部、删除尾部这些case都要单独测一遍。很多程序挂在99%的时间没问题、但1%的边界case上把边界全测一遍比写一万行代码更管用。这也是为什么408真题和面试题里总爱考边界条件你能把这些case都写对说明你真的理解了链表。6.3 面试/编程题中的高频形态逆序、相交与合并除了前面讲的逆序链表相关的常见考题还有“判断链表有环并在环入口处返回节点”典型的快慢指针题目、“两个单链表相交求交点”、“合并两个有序链表”、“删除链表倒数第n个节点”“、寻找链表中间节点”等等。你复习的时候不需要追求把所有变种都刷完但要把核心套路掌握牢快慢指针解决循环检测、找中间点、求倒数第k个节点递归解决逆序打印、反转链表、合并有序链表双指针解决相交链表、去重等需要同时操作两个位置的场景哑节点dummy node统一边界情况本质就和“头结点”的思路一致。把这四个套路搞熟基本能覆盖大部分链表类编程题。408王道那本书里的链表代码必背清单核心也就是这些套路你照着练就行。7. 链表的延伸从专业课到实际工程7.1 操作系统和内核里为什么离不开链表很多人学链表觉得只是考试内容实际上操作系统内核里链表到处可见。Linux内核的list_head结构就是一个经典的循环双链表它不包含数据而是嵌在你的业务结构体里通过指针把自定义结构体串起来。这种“侵入式链表”的设计思路比我们在教材里学的“节点包含数据”更反直觉但空间利用率更高。理解教材版链表之后再看内核链表有种“原来还能这么设计”的豁然感。7.2 高级语言里链表被包装成了你熟悉的样子Java的LinkedList是标准双向链表C STL的list也是。Python的list严格来说是动态数组但如果你用Python自己写链表类逻辑跟C语言完全一致只是指针被引用对象替代了。用Python实现单链表逆序代码比C精简很多可核心逻辑还是那几个步骤保存后继、反转指针、移动游标。语言变了数据结构的思想没变。7.3 从链表到更复杂的数据结构树和图的邻接表存储本质上就是“数组链表”的组合。比如二叉树的二叉链表表示法每个节点存数据加左孩子指针和右孩子指针这跟双链表的结构惊人地相似只是两个指针的语义从“前驱后继”变成了“左子树右子树”。所以链表不只是孤立的知识点它是理解整个数据结构体系的地基。地基打不牢的话后面的树、图、哈希表都会受影响。8. 最后再分享一点实用的学习经验如果你现在正在为一个链表的实验报告发愁我的建议是别急着抄代码。先花20分钟把你手头这道题目的链表图画一遍把每个节点的next指向关系画清楚把增删改查的手工过程全部走一遍再动手写代码。写完之后留10分钟测试边界case。这套流程看着慢实际是最快的因为大部分时间都消耗在“看着代码想不通哪里错了”上而画图可以从根源上杜绝这个问题。我个人在带新人、帮学弟学妹改实验报告的时候发现十个人里有七个会忘记给尾节点的next置NULL五个会删除节点后继续访问被删的节点三个会传参时只传了头指针却指望函数能改头指针的值。这三类错误几乎占了链表bug的一大半。你要是发现自己写链表代码老出问题先自查这三类大概率能省下很多调试时间。数据结构这门课链表是第一个真正的分水岭。跨过去了后面树的递归、图的遍历、哈希表的冲突处理你都会觉得顺理成章跨不过去后面每一步都是空中楼阁。希望这篇内容能帮你在链表这个分水岭上站稳脚跟。等你熟练到能把单链表的增删改查闭着眼睛写出来再回头看那些曾经的困惑会发现一切其实很简单节点、指针、画图就够了。
链表从入门到精通：单链表、双链表与高频考点全解析
很多人学链表卡在第一步不是代码写不出来而是根本没明白链表到底在解决什么问题。我当年学数据结构的时候也一样看严蔚敏那本C语言版教材结构体、指针、malloc看得一头雾水直到自己动手把单链表从零到一实现了一遍才真正理解“节点”和“指针”这两个词的含义。今天这篇内容我尽量用大白话把链表讲透从结构设计到完整代码从单链表到双链表再到循环链表最后把面试和考研里高频的几个考点也捋一遍。不管你是大一正在写实验报告还是准备408数据结构那门课或者工作后回头补基本功这篇都值得看完。1. 为什么学链表之前先想清楚数组的局限1.1 数组的“连续内存”带来什么问题我们天天用的数组本质上是在内存里开辟一块连续的空间。这也意味着如果你想在中间插入一个元素后面的所有元素都得往后挪一步。假设你有一个长度为十万的数组在最后插入一个元素代价可以忽略不计但要在最前面插入一个元素就要把十万个元素全部移动一次时间复杂度是O(n)。这在真实业务里是非常常见的场景比如维护一个消息队列、保存用户的操作历史记录都是频繁地在头部或中间插入数据数组这种结构在这种场景下就显得笨重。而且数组在定义时就得确定长度。如果你用C语言写int arr[100]这个100就不能再变了用动态分配的话扩容时要重新申请一块更大的空间还要把旧数据整体拷贝过去。这个“一次性分配一整块连续空间”的思路天然就跟动态增删的需求有矛盾。1.2 链表用“离散空间”破解连续分配的困局链表的思路完全不同它不要求内存是连续的每个节点各管各的存储位置。节点之间靠“指针”串联起来前一个节点里存着后一个节点的地址就像一串珠子每颗珠子上写着下一颗珠子的位置。这样一来想在中间插入数据只需要改变两个节点的指针方向不需要移动任何其他数据时间复杂度是O(1)只是找到插入位置需要O(n)。删除操作也一样修改一下指针就断了节点之间的连接。用一个通俗的比喻数组像火车车厢每节车厢焊死在轨道上想在中途加一节车厢后面的都得重新编组链表像手拉手的一队人想插队的话只需要让前面的人放开手拉住新来的人新来的人再拉住后面的人整个队伍不用动。这就是为什么链表能成为各种动态数据结构的基石。后面接触的树、图的邻接表存储核心也是链表的思路。1.3 链表的代价空间换时间代价不止一个指针当然天下没有免费的午餐。链表能换来插入删除的高效付出的代价也很明显每个节点都要额外存储一个指针双链表还要存两个内存开销比数组大。无法随机访问。数组可以用下标直接定位到第n个元素链表必须从头开始一个一个往后走。频繁的malloc和free或new和delete会带来内存碎片和管理负担。理解了这几点你再看网上那些“数组和链表怎么选”的讨论心里就有数了。核心就一句话读多、固定容量、随机访问频繁的场景选数组写多、容量动态增长、频繁增删的场景选链表。这也是后面理解HashMap等复杂数据结构的前提。HashMap之所以能高效应对数据量增长正是因为它内部结合了数组的随机访问优势和链表的插入优势。2. 单链表最基础也最核心的形态2.1 节点结构到底怎么定义单链表是最简单的链表形态每个节点只包含两个部分数据域和指向下一个节点的指针。在C语言里是这样定义的typedef struct Node { int data; // 数据域这里以int为例 struct Node *next; // 指针域指向下一个节点 } Node;这里第一眼看上去容易绕的是struct Node *next这个写法。关键理解一句话next是一个指针变量它的类型是“指向这个结构体的指针”它存的是另一个节点的地址。你要访问下一个节点里的数据不是直接拿next而是通过next-data来取。C语言里p-next等价于(*p).next这个箭头符号就是“解引用加取成员”的缩写。我见过很多新手在定义时纠结命名一会儿LNode一会儿LinkList。其实这两种命名区别不大如果用的是严蔚敏教材的风格往往会把节点类型和链表类型分开定义typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;这里LNode表示节点LinkList是“指向LNode的指针”类型等价于LNode *。习惯上用LinkList L表示一个链表头指针用LNode *p表示一个工作指针。理解了这个套路之后你读王道、看408真题里的代码就不会觉得别扭。2.2 创建链表头插法和尾插法的本质区别在“在指定位置插入建立单链表”这个场景里大部分人一开始用的是尾插法。尾插法的逻辑是新节点总是接到链表末尾需要一个指针tail一直指向当前的末尾节点。Node *createByTail(int a[], int n) { Node *head NULL; Node *tail NULL; for (int i 0; i n; i) { Node *s (Node *)malloc(sizeof(Node)); s-data a[i]; s-next NULL; if (head NULL) { head s; tail s; } else { tail-next s; tail s; } } return head; }头插法则完全不同每次把新节点插到链表头部让新节点的next指向原来的头节点。操作虽然只有两三行但效果是数据顺序被颠倒了Node *createByHead(int a[], int n) { Node *head NULL; for (int i 0; i n; i) { Node *s (Node *)malloc(sizeof(Node)); s-data a[i]; s-next head; head s; } return head; }头插法输出结果会反转这是很多人写实验报告时踩的第一个坑。比如输入1,2,3尾插法输出是1,2,3头插法输出是3,2,1。如果你做的是一个排队系统的模拟用头插法建表结果就全反了。而在某些场景里这种反转是有意为之的比如实现链表的原地逆序思路就是遍历原链表的同时用头插法重建一个新链表。判定用什么方法核心看你想要的顺序。2.3 在指定位置插入节点的关键细节插入操作看着简单但边界条件特别多。思路是要在第i个位置插入节点s核心是找到第i-1个位置的节点p然后执行两条语句s-next p-next; p-next s;这两条语句的顺序绝对不能反。先执行p-next s的话s后面原本的链表就丢了因为p-next已经被覆盖你再也找不到原来p后面的节点了。这就像排队时你拉住新来的人结果一松手原来拉着的人跑了。完整实现还需要考虑几个边界情况i是有效位置吗插入前最好判断一下链表长度和位置范围如果领头结点后面详细讲插在第一个位置和插在其他位置代码逻辑一样比较方便如果不领头结点插在头部得单独处理头指针的修改。int insertNode(Node **pHead, int i, int val) { if (i 0 || *pHead NULL) return 0; Node *p *pHead; int pos 1; while (p ! NULL pos i - 1) { p p-next; pos; } if (p NULL) return 0; // 位置超出链表实际长度 Node *s (Node *)malloc(sizeof(Node)); s-data val; s-next p-next; p-next s; return 1; }注意这里函数参数用了Node **pHead也就是“头指针的指针”。为什么要这么麻烦因为如果插入的是第一个位置函数内部就要修改外界的头指针变量C语言传值的话修改只对副本生效传指针的指针才能把修改带出去。这也是一个典型的“二级指针”考点面试里经常有人在这里露怯。3. 带头结点与不带头结点一个经常被忽略的思路设计差异3.1 带头结点到底带的是什么“头”很多教材在讲链表时会默认有一个头结点也就是一个不存有效数据的节点它的next才指向第一个真正存数据的节点。严蔚敏教材里用的LinkList L常常就是带头结点的链表。头结点和头指针是两个不同的概念头指针是链表存在的标志它指向链表的第一个节点头结点是第一个节点之前附加的一个节点数据域通常不设值指针域指向真正的首元节点。为什么要多弄一个空节点出来最大的好处是针对第一个位置的操作和针对中间位置的操作变成了一样的逻辑。不带头结点的链表head指向首元节点你在head处插入需要改head本身你删首元节点也需要改head本身。这逼迫你在所有涉及首元节点的操作上都得写条件判断。带头结点之后头结点永远是头结点插入删除的逻辑统一了代码写起来清爽很多。3.2 不带头结点的场景空间极致省时怎么办那是不是带头结点永远更好也不是。某些算法题为了节省那一个节点的空间或者为了考察你对指针操作的理解深度会故意用不带头结点的链表。比如“判断两个链表是否相交”这类题给的往往是带头结点或不带头结点的混合情况你得自己判断。另外在某些嵌入式、内存极紧张的环境里多一个头结点就是多一份空间开销哪怕只是8字节一个指针的大小积少成多也心疼。不带头结点的链表处理插入时必须专门对i1做特殊处理int insertNoHead(Node **pHead, int i, int val) { Node *s (Node *)malloc(sizeof(Node)); s-data val; if (i 1) { s-next *pHead; *pHead s; return 1; } // 其他位置逻辑与带头结点相同 Node *p *pHead; int pos 1; while (p ! NULL pos i - 1) { p p-next; pos; } if (p NULL) return 0; s-next p-next; p-next s; return 1; }不管头上有没有结点你都要把“第一个位置”单独拎出来考虑。这也解释了为什么很多408真题的代码题给出的链表都是带头结点的——出题人想考算法逻辑而非边界条件的处理。但你自己练习时两种形态都写一遍会明显提升对指针的理解。3.3 清空和销毁最容易遗漏的两个函数链表题里还有两个操作容易被学生忽略一个是“清空”一个是“销毁”。清空是从头到尾把数据节点释放掉只保留头结点如果链表带头结点的话让链表变空销毁是连头结点也释放head置为NULL。两者的区别类似于清空购物车和注销账号。void clearList(Node *head) { Node *p head-next; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } head-next NULL; } void destroyList(Node **pHead) { Node *p *pHead; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } *pHead NULL; }很多人写程序只malloc不free考试时没关系但你在工程项目里这么干内存泄漏的clock会一直跑。尤其是嵌入式或服务端长期运行的程序里泄漏一点点内存都可能最终拖垮整个进程。清空时为什么释放完节点后马上把head-next NULL因为你若不清空指针一旦有人误用这个“已经释放了的头结点”就变成了典型的悬空指针问题。4. 单链表遍历与双链表从只会头到尾到可以倒着走4.1 遍历时最容易踩的坑用head本身当指针很多新手写遍历是这样void printList(Node *head) { while (head ! NULL) { printf(%d , head-data); head head-next; } }功能上讲这没问题但问题是遍历完之后head已经变成了NULL外界的头指针虽然没变但这个函数把参数副本用掉了。你接下来还想用这个链表做别的操作还得重新建一个临时变量来遍历。正确习惯是永远借助另一个工作指针p让头指针一直指向链表的头部void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }这不仅仅是代码习惯的问题在很多递归判断链表长度、查找倒数第k个节点等问题里头指针是否保留决定了你能不能继续操作。保留头指针这个习惯越早养成越好。4.2 单链表的局限催生双链表单链表只有一个next方向导致一个问题你走到某个节点之后想回去找上一个节点做不到只能从头再来。如果业务上经常需要双向遍历比如浏览器的前进后退历史、文本编辑器的撤销重做栈单链表就不够用了。双链表就是每个节点再加一个prev指针指向前驱节点typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;双链表的插入操作看起来代码更多但逻辑上更对称核心还是先处理新节点的前后指针再处理前后节点的连接顺序不能乱。在p节点后面插入s节点s-prev p; s-next p-next; if (p-next ! NULL) { p-next-prev s; } p-next s;注意p如果是最后一个节点p-next是NULL这时p-next-prev这句代码就不能执行所以要加个判空。双链表的删除操作也一样多了一个前驱指针要改但好处是删除某个节点时不需要从头找它的前驱直接通过p-prev就能拿到时间复杂度从O(n)降到了O(1)代码也更优雅p-prev-next p-next; if (p-next ! NULL) { p-next-prev p-prev; } free(p);4.3 循环链表与约瑟夫环问题循环单链表的最后一个节点的next不再指向NULL而是回头指向头结点或第一个节点整个链表变成一个环。循环双链表类似头结点的prev指向表尾节点。判断一个链表是不是循环链表最经典的做法是快慢指针快指针每次走两步慢指针每次走一步如果链表有环两个指针迟早相遇。这个思路不仅用于循环链表判断也是LeetCode“环形链表”这道题的核心解法。约瑟夫环是循环链表一个非常经典的实战案例n个人围成一圈从第一个人开始报数报到m的人出列之后从下一个人重新报数直到所有人出列要求输出出列顺序。这类问题如果用数组模拟每次删除一个人的代价是O(n)总代价O(n²)而用循环链表天然贴合“围成一圈”的结构删除一个人只需要改动两个指针。我当年在实验课上用循环链表写约瑟夫环写完才体会到教材里为什么总用它举例它把循环链表的“遍历一圈”、“删除节点”、“遍历终止条件”三个核心点全训练到了。5. 完整实操手写一个带头结点的单链表工具库5.1 编码之前先画图哪怕只在脑子里画很多人在写链表代码时觉得思路乱根源在于没在脑中画出指针指向关系。我建议你哪怕只是在草稿纸上简单画把每个节点画成一个方块方块的右边引出一条线写着“next”然后手动模拟一遍插入、删除的过程。画过一次之后代码就是照着图翻译基本不会错。对于复杂的链表题我到现在还会用画图来推演边界情况。5.2 一个可直接参考的实验代码框架下面是一个完整可运行的C语言示例包含创建、遍历、插入、删除、清空、销毁全部基于带头结点的单链表。你可以直接复制到本地编译运行建议在此基础上改一改比如头插法反转、按值删除所有匹配的节点这些改动量不大但训练价值很高。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node, *LinkList; // 创建一个带头结点的空链表 LinkList createList() { LinkList head (LinkList)malloc(sizeof(Node)); head-next NULL; return head; } // 尾插法在链表末尾追加值为val的节点 void appendNode(LinkList head, int val) { Node *p head; while (p-next ! NULL) { p p-next; } Node *s (Node *)malloc(sizeof(Node)); s-data val; s-next NULL; p-next s; } // 遍历打印 void printList(LinkList head) { Node *p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 按位置插入位置从1开始 int insertByPos(LinkList head, int i, int val) { Node *p head; int pos 0; while (p ! NULL pos i - 1) { p p-next; pos; } if (p NULL) return 0; // 插入位置不合法 Node *s (Node *)malloc(sizeof(Node)); s-data val; s-next p-next; p-next s; return 1; } // 按位置删除删除成功后返回节点的值失败返回-1表示失败 int deleteByPos(LinkList head, int i, int *value) { Node *p head; int pos 0; while (p-next ! NULL pos i - 1) { p p-next; pos; } if (p-next NULL) return 0; // 第i个节点不存在 Node *del p-next; *value del-data; p-next del-next; free(del); return 1; } // 清空数据节点保留头结点 void clearList(LinkList head) { Node *p head-next; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } head-next NULL; } // 销毁整个链表包括头结点 void destroyList(LinkList *pHead) { Node *p *pHead; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } *pHead NULL; } int main() { LinkList list createList(); int arr[] {1, 2, 3, 4, 5}; for (int i 0; i 5; i) { appendNode(list, arr[i]); } printf(原始链表: ); printList(list); insertByPos(list, 3, 99); printf(在第3个位置插入99: ); printList(list); int val; if (deleteByPos(list, 3, val)) { printf(删除第3个位置的值%d: , val); printList(list); } clearList(list); printf(清空后链表是否为空: ); if (list-next NULL) printf(空\n); destroyList(list); return 0; }这段代码的结构设计上有一个值得注意的地方所有操作都通过头结点进入不需要在main函数里反复修改head本身所以函数参数都可以直接用一级指针LinkList head只有销毁时需要二级指针因为销毁后要把外界的head置空。实验报告里如果设计成这样的分层老师一眼就能看出你对链表的理解到位。5.3 链表逆序手撕高频考题的完整思路链表逆序是一个必考操作。基本思路是用三个指针分别记录当前节点的前驱、当前节点、后继逐个把箭头反向。下面这段代码是“不带头结点”链表的原地逆序逻辑更通用Node *reverseList(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; // 保存后继防止丢失 cur-next prev; // 反转指针 prev cur; cur next; } return prev; // 遍历结束时prev就是新的头节点 }这里最容易犯的错误是反转了前一个节点的指针之后没有先保存cur-next就直接用cur cur-next结果发现cur已经指回前一个节点去了链表就断了。事后你排查这种bug时一定要回到“指针指向关系”去捋而不是瞎试。逆序之后原来链表的最后一个节点成了新链表的头这也是测试时最容易验证的点。6. 常见问题排查与避坑指南6.1 用着用着程序就崩了十大链表崩溃原因对照表链表代码里的崩溃绝大多数都跟指针有关。我把最常见的几类问题和排查思路整理成一张表你调试的时候可以对着找现象常见原因排查与修复思路程序直接Segmentation fault对NULL指针解引用检查是否访问了p-next但p是NULL遍历时死循环链表中存在环检查尾节点的next是否忘了置NULL打印出来的顺序不对头插法建表导致顺序反转按需选择头插法或尾插法删除节点后链表乱套没有先把后续节点地址保存下来删除前用临时指针记录被删节点的后继运行结果随机崩溃访问了已释放的节点悬空指针释放指针后立即置NULL避免二次解引用内存占用只增不减malloc了没free删除和清空时补上free插入位置不对位置下标从0还是1没搞清楚明确约定位置编号统一处理修改链表后外部头指针不变函数参数传值而非传指针的指针需要修改head时用Node **倒数第k个节点找不到没考虑k等于链表长度的情况快慢指针法或先求长度再走反转链表结果只是部分反转没保存cur-next或没更新头指针按三步走逐节点反转最后返回新头这张表是我自己调代码时反复踩过的坑对照着排查能节省大量时间。6.2 调试链表的三个实用技巧第一打印游标。在关键操作前后都打印一下当前节点的地址和数据域用类似printf(p%p, p-data%d\n, p, p-data)的语句能快速定位到哪一步指针断开了。第二画图推演。前面提过遇到复杂的插入删除画图是最有效的。不夸张地说我至今遇到链表相关的bug第一反应还是拿出纸笔画一遍链表当前的连接状态而不是直接在屏幕上看代码。第三最小化测试。链表代码有很强的边界效应空链表、只有一个节点、两个节点、插入到头部、插入到尾部、删除头部、删除尾部这些case都要单独测一遍。很多程序挂在99%的时间没问题、但1%的边界case上把边界全测一遍比写一万行代码更管用。这也是为什么408真题和面试题里总爱考边界条件你能把这些case都写对说明你真的理解了链表。6.3 面试/编程题中的高频形态逆序、相交与合并除了前面讲的逆序链表相关的常见考题还有“判断链表有环并在环入口处返回节点”典型的快慢指针题目、“两个单链表相交求交点”、“合并两个有序链表”、“删除链表倒数第n个节点”“、寻找链表中间节点”等等。你复习的时候不需要追求把所有变种都刷完但要把核心套路掌握牢快慢指针解决循环检测、找中间点、求倒数第k个节点递归解决逆序打印、反转链表、合并有序链表双指针解决相交链表、去重等需要同时操作两个位置的场景哑节点dummy node统一边界情况本质就和“头结点”的思路一致。把这四个套路搞熟基本能覆盖大部分链表类编程题。408王道那本书里的链表代码必背清单核心也就是这些套路你照着练就行。7. 链表的延伸从专业课到实际工程7.1 操作系统和内核里为什么离不开链表很多人学链表觉得只是考试内容实际上操作系统内核里链表到处可见。Linux内核的list_head结构就是一个经典的循环双链表它不包含数据而是嵌在你的业务结构体里通过指针把自定义结构体串起来。这种“侵入式链表”的设计思路比我们在教材里学的“节点包含数据”更反直觉但空间利用率更高。理解教材版链表之后再看内核链表有种“原来还能这么设计”的豁然感。7.2 高级语言里链表被包装成了你熟悉的样子Java的LinkedList是标准双向链表C STL的list也是。Python的list严格来说是动态数组但如果你用Python自己写链表类逻辑跟C语言完全一致只是指针被引用对象替代了。用Python实现单链表逆序代码比C精简很多可核心逻辑还是那几个步骤保存后继、反转指针、移动游标。语言变了数据结构的思想没变。7.3 从链表到更复杂的数据结构树和图的邻接表存储本质上就是“数组链表”的组合。比如二叉树的二叉链表表示法每个节点存数据加左孩子指针和右孩子指针这跟双链表的结构惊人地相似只是两个指针的语义从“前驱后继”变成了“左子树右子树”。所以链表不只是孤立的知识点它是理解整个数据结构体系的地基。地基打不牢的话后面的树、图、哈希表都会受影响。8. 最后再分享一点实用的学习经验如果你现在正在为一个链表的实验报告发愁我的建议是别急着抄代码。先花20分钟把你手头这道题目的链表图画一遍把每个节点的next指向关系画清楚把增删改查的手工过程全部走一遍再动手写代码。写完之后留10分钟测试边界case。这套流程看着慢实际是最快的因为大部分时间都消耗在“看着代码想不通哪里错了”上而画图可以从根源上杜绝这个问题。我个人在带新人、帮学弟学妹改实验报告的时候发现十个人里有七个会忘记给尾节点的next置NULL五个会删除节点后继续访问被删的节点三个会传参时只传了头指针却指望函数能改头指针的值。这三类错误几乎占了链表bug的一大半。你要是发现自己写链表代码老出问题先自查这三类大概率能省下很多调试时间。数据结构这门课链表是第一个真正的分水岭。跨过去了后面树的递归、图的遍历、哈希表的冲突处理你都会觉得顺理成章跨不过去后面每一步都是空中楼阁。希望这篇内容能帮你在链表这个分水岭上站稳脚跟。等你熟练到能把单链表的增删改查闭着眼睛写出来再回头看那些曾经的困惑会发现一切其实很简单节点、指针、画图就够了。
