第一次被单链表按在地上摩擦是大二那年的数据结构实验课。老师在黑板上画了三个框框两根箭头说就这么简单然后让我们当场写一个带头结点的单链表插入。我盯着屏幕上那个p-next s; s-next p-next;反复看了十分钟程序每跑一次就崩一次调试器里p的地址看起来又不像空。后来才明白我把两行赋值写反了链子从中间断掉后面所有的节点全部成了野内存。这件事说明了一件事数据结构里链表这个东西看懂和写对之间隔着一整条银河。它不像数组那样有下标兜底链表全靠指针自己给自己导航一步踩空就是段错误而且往往是延迟爆炸——错误在现场崩溃在别处。这也是为什么它成了考研数据结构、期末复习、公司面试笔试里的钉子户考的不是你背没背下插入时间复杂度 O(1)而是你能不能在大脑里把内存画成一串带箭头的方块。这篇东西适合三类人看正在啃数据结构课本、需要一份能跑通的单链表原码的学生准备考研或面试、要重新把链表基础捋一遍的人以及平时写业务代码、突然被要求手撕链表发现全忘光的开发者。我会从头把单链表结构设计、每个操作背后的指针逻辑、完整可编译的原码、调试时踩过的坑一直到快慢指针、合并有序链表这类延伸题全部拆开讲一遍。你不用先看完整个数据结构教材只要会写基本的 C 语言函数和结构体就能跟着走完。1. 从一次段错误说起单链表到底难在哪1.1 链表真正劝退人的地方不是概念单链表的概念简单到一句话就能说完一堆节点每个节点存一个数据和一个指向下一个节点的指针最后一个节点的指针为空。任何人五分钟就能理解这个描述。但理解结构和写出正确代码是两码事难点全部集中在指针操作的顺序和边界上。拿插入来说你要在节点 A 后面插入新节点 S得做两件事让 S 指向 A 原来的后继再让 A 指向 S。这两行的先后顺序不能反。如果先写A-next S那 A 原来的后继地址就丢了你再也找不到后面那串节点剩下的内存既没释放也没人引用直接泄漏。反过来写出错S 指向自己程序进入死循环或者打印出无穷无尽的垃圾数据。这类错误在数组里根本不存在因为数组的相邻关系是下标算出来的不是你手动维护的。删除更麻烦。很多人写删除只记住了p-next q-next忘了free(q)或者反过来先free(q)再去访问q-next读到的是已经归还给系统的内存。这两种写法在小型测试里都能跑出正确结果因为内存还没来得及被覆盖一旦放进大程序里崩的地方离你写代码的地方十万八千里。链表难难在它有时间维度内存的分配、使用、释放是有先后依赖的这个依赖关系不会报错提醒你只会用结果不对来惩罚你。1.2 数组和链表的取舍别只背复杂度几乎所有教材都会给你一张表数组随机访问 O(1)、插入删除 O(n)链表随机访问 O(n)、插入删除 O(1)。这张表是对的但它会误导人因为它的前提是你已经站在要操作的节点上了。实际写代码时你往往要先花 O(n) 把指针走到那个位置然后再做 O(1) 的插入。所以链表插入是 O(1)这句话只有在你能直接拿到目标节点指针的场景下才成立比如你已经持有某个节点的引用、或者在做遍历时顺便插入。我在实际项目里选择链表而不是数组通常是因为下面三个理由之一一是元素数量变化剧烈今天几百个明天几万个数组每次扩容都要重新分配加拷贝代价太高二是需要在中间频繁插入删除而且插入位置是通过遍历自然到达的比如按顺序维护一个任务队列三是节点本身很大用数组的话扩容时需要整块大内存连续分配容易失败。反过来如果我的场景是频繁按下标读取、很少改动结构那数组或者动态数组几乎是唯一正确答案因为链表的节点分散在堆上每次跳转都可能是一次缓存未命中实测下来遍历速度能差出好几倍。这个差距在数据量小的时候看不出来上到几十万节点就很明显了。提示不要因为链表听起来更高级就到处用链表。链表是用空间换灵活性每个节点都要多存一个指针还要额外承担内存分配的开销。数据结构选型要看访问模式不看名字好不好听。2. 单链表的骨架设计节点、头指针与头结点2.1 头结点的取舍会影响你后面所有代码单链表有两种常见写法带头结点和不带头结点。带头结点就是在第一个真实数据节点前面放一个不存数据的哨兵节点头指针永远指向它不带头结点则是头指针直接指向第一个数据节点。为什么我强烈建议初学和考试都先用带头结点的版本因为不带头结点的代码里插入和删除第一个位置需要单独特判。比如删除第一个节点时你要把头指针指向第二个节点同时释放第一个节点而删除其他节点时你要修改的是前一个节点的next。这两种情况操作的对象不一样——一个改头指针本身一个改节点的字段。写代码时就得写两个分支而且头指针作为一个变量修改它需要传入二级指针或者返回值。带头结点之后第一个数据节点的前驱就是头结点插入删除第一个位置和其他位置逻辑完全统一代码量能砍掉三分之一出错概率也低很多。代价是多占一个节点的内存以及遍历时要记得从head-next开始而不是head开始。这点小成本在绝大多数场景下完全值得。我自己的习惯是只要不是题目明确要求不带头结点一律带头结点写。2.2 结构体定义里的三个细节C 语言里单链表节点通常这样定义typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;这里面有三个细节值得说。第一struct LNode *next里的struct不能省因为此时typedef还没生效编译器不认识LNode这个名字。第二typedef同时给结构体起了两个名字LNode是节点类型LinkList是指向节点的指针类型。后者纯粹是为了可读性LinkList L一眼就能看出 L 是一条链而不是单个节点。第三ElemType单独抽出来是有意义的将来想把 int 换成结构体或者 char改一行就行不用满篇搜索替换。注意LNode和LinkList在语法上完全等价都能指向任意节点。但写代码时请保持约定需要表示整条链的变量用LinkList需要表示某个工作指针的用LNode *。这种语义上的区分能显著降低你自己两周后读代码时的痛苦。还有一个经常被忽略的点sizeof(LNode)在 64 位机器上通常是 16 字节而不是 12 字节因为 int 占 4 字节、指针占 8 字节但结构体要按最大成员对齐会补 4 字节的填充。如果你的节点数据很小、节点数量极大这个填充比例是很可观的。想让内存更紧凑可以把数据字段和指针字段的顺序调一调或者考虑用索引代替指针。2.3 初始化不是可有可无的一步一个刚声明出来的头指针比如LinkList L;它的值是栈上的垃圾数据不是 NULL。你如果直接拿它去做L-next NULL程序立刻崩溃因为你正在往一个随机地址写数据。所以初始化的本质是先在堆上申请一个节点让头指针指向它再把这个节点的next置空。bool InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); if (*L NULL) return false; (*L)-next NULL; return true; }这里我用了二级指针LinkList *L。原因是函数内部要修改调用方的头指针变量本身而不是它指向的内容所以必须传地址进来。很多人第一次写会写成void InitList(LinkList L)结果函数里申请的内存赋给了形参函数一返回就丢了外面拿到的还是垃圾值而且那块内存泄漏了。这是个非常经典的错误我自己也犯过。另一种避免二级指针的做法是让函数返回头指针LinkList InitList(void)调用时L InitList();同样干净。两种都行选一种自己顺手的别混着用。3. 核心操作的实现逻辑逐个拆解3.1 按位查找循环条件里的 j 到底停在哪按位查找要求返回第 i 个节点i 从 1 开始计数注意不是 0。带头结点的版本是这样的LNode *GetElem(LinkList L, int i) { if (i 0) return NULL; LNode *p L; int j 0; while (p ! NULL j i) { p p-next; j; } return p; }这里有个特别容易绕晕的地方j的初始值是 0代表p现在指向头结点也就是第 0 个节点。当j i时循环结束p正好指向第 i 个节点。如果i 0循环一次都不执行直接返回头结点——这恰好是正确的因为头结点就是第 0 个节点。如果 i 比链表长度大循环会在p NULL时退出返回 NULL。提示while (p ! NULL j i)里两个条件的顺序有讲究。必须先判p ! NULL再做别的事因为进入循环体马上要访问p-next。虽然这个写法里j i写在后面在逻辑上也安全但养成先判空、后解引用的习惯能帮你躲掉大量段错误。还有一种常见的写法是用j i - 1来找第 i 个节点的前驱这个版本在插入和删除里更常用因为插入删除真正需要的是前驱节点。两种写法没有对错关键是你自己要清楚当前 p 指的是谁。我的经验是在代码里写一行注释标明不变量比如/* p 指向第 j 个节点 */调试时能救命。3.2 头插法与尾插法同一件事的两种代价建立链表有两种主流方式。头插法是每次把新节点插到头结点后面代码只有三行s-next L-next; L-next s;好处是简单、O(1) 一次插入。坏处是它会把输入顺序完全颠倒——你依次输入 1、2、3最后链表里是 3、2、1。这个逆序特性其实很有用后面讲就地逆置的时候会用到同样的思路。尾插法要维护一个尾指针r每次在r后面追加r-next s; r s;最后一定要补一句r-next NULL否则尾节点的next是未初始化的垃圾值遍历时会冲出去。我见过太多次这个错误代码看起来每一步都对就是打印的时候多出一堆乱码然后崩溃原因就是漏了这句。从工程角度看尾插法保持了顺序符合直觉代价是需要额外维护一个尾指针4 到 8 字节。如果链表很长每次插入都从头遍历找尾节点的写法是 O(n²)绝对不能用。如果题目只给头指针、又要求尾插可以维护一个循环链表或者额外带长度字段但考试里一般允许你声明一个r变量。3.3 插入与删除断链顺序决定程序死活先看插入。在第 i 个位置插入元素 e也就是在结点 i-1 和 i 之间插进去bool ListInsert(LinkList L, int i, ElemType e) { if (i 1) return false; LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) return false; LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return false; s-data e; s-next p-next; p-next s; return true; }核心是最后两行顺序不能反先让新节点接管 p 的后继再让 p 指向新节点。反过来的话p 原来的后继节点就永远找不到了。删除同理bool ListDelete(LinkList L, int i, ElemType *e) { if (i 1) return false; LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL || p-next NULL) return false; LNode *q p-next; *e q-data; p-next q-next; free(q); return true; }这里if (p NULL || p-next NULL)这个判断很关键。p NULL说明 i-1 超过了链表长度p-next NULL说明第 i 个位置不存在p 已经是最后一个节点了。少了任何一个判断都可能对 NULL 解引用。注意删除操作的参数e最好用指针传出去因为C语言函数只能返回一个值而删除既需要返回成功与否又需要把被删的数据带出来。用ElemType *e是标准做法。如果确实不需要返回数据那写一个只返回 bool 的版本也行但考试里通常要求带回。3.4 就地逆置三根指针的搬运工单链表逆置是笔试题里的常客也是最能看出一个人指针功底的地方。思路是把链表从头到尾扫一遍每遇到一个节点就把它摘下来插到新链表的头部。因为头插天然逆序扫完就逆置完了。LinkList Reverse(LinkList L) { LNode *p L-next, *r; L-next NULL; while (p ! NULL) { r p-next; p-next L-next; L-next p; p r; } return L; }这段代码里有三根指针分工必须清楚p是当前待处理节点r是保存 p 的后继因为马上要改 p 的 next不改前先存L-next是已经处理好的逆置部分的头。循环体四行的顺序一步都不能错先存后继再挂链再接头最后前进。我第一次写这个的时候把r p-next;写在了p-next L-next;后面结果就是每处理一个节点就把后面的整串丢了。调试的时候看到链表长度一直是 1加再多的数据也只能打出一个特别诡异。这类丢失后继的错误在链表里占了一大半记住一句话就够了任何要修改p-next的代码前面必须先保存p-next。3.5 销毁与置空free 之后必须做的事链表用完了要销毁释放所有节点。写法是按顺序释放不能先断链再释放void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *q p-next; free(p); p q; } }注意这里先保存p-next再free(p)顺序别搞反。free 之后那块内存的内容可能还是原来的数据你去读它未必立刻出错但这是未定义行为换个编译器换个运行环境就可能崩。还有一个容易忽略的点释放完所有节点后调用方的头指针变量依然指向那块已经归还的内存成了悬空指针。如果后面还拿它判断if (L ! NULL)条件为真但内存已失效非常危险。所以销毁函数最好接收二级指针释放完顺手把调用方那个变量也置成 NULL。这是我在实际项目里养成的一个习惯多写一行代码能解决将来一整个下午的排查。4. 完整可编译原码一份能直接跑的单链表实现4.1 整体框架与依赖下面这份代码我按能直接编译运行的标准来写用标准C不依赖任何第三方库。包含结构定义、初始化、插入、删除、查找、逆置、遍历、建表、销毁以及一个测试主函数。你可以直接存成list.c用gcc list.c -o list -g编译-g是为了出问题时能上调试器。#include stdio.h #include stdlib.h #include stdbool.h typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; bool InitList(LinkList *L); bool ListInsert(LinkList L, int i, ElemType e); bool ListDelete(LinkList L, int i, ElemType *e); LNode *GetElem(LinkList L, int i); LNode *LocateElem(LinkList L, ElemType e); void CreateListTail(LinkList L, ElemType a[], int n); void CreateListHead(LinkList L, ElemType a[], int n); LinkList Reverse(LinkList L); int ListLength(LinkList L); void PrintList(LinkList L); void DestroyList(LinkList *L);4.2 函数实现初始化、插入、删除前面已经讲过这里补上按值查找、头插建表、求长度和打印bool InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); if (*L NULL) return false; (*L)-next NULL; return true; } LNode *LocateElem(LinkList L, ElemType e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; } void CreateListTail(LinkList L, ElemType a[], int n) { LNode *r L; for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data a[i]; r-next s; r s; } r-next NULL; } void CreateListHead(LinkList L, ElemType a[], int n) { L-next NULL; for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data a[i]; s-next L-next; L-next s; } } int ListLength(LinkList L) { int len 0; LNode *p L-next; while (p ! NULL) { len; p p-next; } return len; } void PrintList(LinkList L) { LNode *p L-next; printf(head); while (p ! NULL) { printf( - %d, p-data); p p-next; } printf( - NULL (len%d)\n, ListLength(L)); } void DestroyList(LinkList *L) { LNode *p *L; while (p ! NULL) { LNode *q p-next; free(p); p q; } *L NULL; }按值查找的时间复杂度是 O(n)返回的是第一个匹配节点的指针找不到就返回 NULL。这个返回值很有用拿到之后你可以直接做 O(1) 的插入删除。求长度和打印都从L-next开始遍历别从头结点开始否则长度会多算一个打印会多出一个垃圾数据。4.3 测试主函数与预期输出int main(void) { LinkList L; if (!InitList(L)) return 1; ElemType a[] {10, 20, 30, 40, 50}; CreateListTail(L, a, 5); PrintList(L); ListInsert(L, 3, 99); PrintList(L); ElemType del; if (ListDelete(L, 1, del)) { printf(deleted: %d\n, del); } PrintList(L); LNode *found LocateElem(L, 40); printf(found 40 at %p, value%d\n, (void *)found, found ? found-data : -1); Reverse(L); PrintList(L); DestroyList(L); printf(after destroy, L %p\n, (void *)L); return 0; }预期输出大致是这样先是head - 10 - 20 - 30 - 40 - 50 - NULL (len5)插入 99 到第 3 位后变成head - 10 - 20 - 99 - 30 - 40 - 50 - NULL (len6)删除第 1 位后打印deleted: 10链表变成head - 20 - 99 - 30 - 40 - 50 - NULL (len5)逆置之后是head - 50 - 40 - 30 - 99 - 20 - NULL (len5)最后打印after destroy, L (nil)证明置空生效了。提示把预期输出提前写下来再对照程序实际输出是排查链表问题最快的方法。不要只看到程序没崩就以为对了链表出错的典型表现就是不崩但结果错。5. 调试实录链表常见问题与排查手法5.1 段错误的六种典型现场链表调试里九成的崩溃可以归到下面几类我按遇到频率排了个序现象根本原因定位方法一进插入函数就崩头指针未初始化值是垃圾地址打印头指针地址或初始化后立即断言非 NULL遍历时崩在中间尾节点 next 未置 NULL在遍历循环里加计数上限输出当前节点地址删除后崩free 之后继续访问该节点检查 free 后是否还有对该指针的解引用偶发崩溃重跑就好使用未初始化的 malloc 内存对所有 malloc 出来的节点显式赋 next打印出乱码然后崩指针跳到了不属于链表的内存打印每个节点地址看是否连续成链越界写导致别处崩溃数组或缓冲区越界覆盖了指针字段用地址检查工具跑一遍我自己的排查套路是先在一张纸上把链表的逻辑结构画出来标上每个节点的地址范围然后在崩溃点打印p、p-next、p-data三个值对照纸上的图看哪一步对不上。这个笨办法几乎每次都管用比盲目加断点快得多。另一个习惯是给每个节点记一个自增编号结构体里临时加个int id字段打印时输出 id哪根链接断了立刻就能看出来。5.2 内存泄漏和越界检测怎么查在 Linux 上排查链表的内存问题我最常用的两个工具是编译器的地址检查功能和 Valgrind。编译时加上-fsanitizeaddress -g程序运行时如果发生越界访问、使用已释放内存、内存泄漏它会直接在终端里打出完整的调用栈告诉你哪一行代码干的。这个工具对初学者特别友好因为它不需要你理解复杂的内存布局看栈就行。Valgrind 的用法是valgrind --leak-checkfull ./list它会统计程序结束时还没释放的块数和字节数并给出分配位置。如果你的链表销毁函数漏了某个分支比如提前 return 导致部分节点没释放它会精确地告诉你泄漏了多少字节、在哪个 malloc 分配。我第一次用它的时候挺震撼的之前一直觉得程序退出操作系统会回收其实对于常驻服务来说这种泄漏会一直累积最后把内存吃光。注意调试版本和发布版本的编译选项不同很多内存错误只在优化打开时才暴露。如果你在-O0下测试正常上线后偶发崩溃试着用-O2再跑一遍同时开着地址检查。这个问题我踩过优化器会把某些未初始化变量的行为改变导致问题换一种方式出现。5.3 写完先自测这几个边界值链表代码写完别急着交。下面这张清单我每次都会过一遍能挡掉大部分低级错误空链表上做删除应该返回失败而不是崩溃。只在头结点后面插一个节点再删掉它看看L-next是否恢复成 NULL。在第 1 个位置插入和删除验证带头结点的统一逻辑是否真的统一。在最后一个位置之后即 i 等于长度加一插入检查是否允许。插入位置 i 传 0 或负数检查参数校验是否生效。长度为 1 的链表逆置检查是否变成自己。连续两次销毁同一条链检查第二次是否安全置空之后应该安全。打印时链表长度和实际节点数是否一致。这几个用例覆盖了所有长度为 0、1、n和位置在头部、中部、尾部、越界的组合。链表出错基本都是边界没考虑到把这些跑通剩下就是逻辑问题而不是内存问题了。6. 从单链表延伸出去的高频考法与工程变体6.1 快慢指针的两个经典场景快慢指针是单链表上最优雅的技巧之一。一根指针每次走一步另一根每次走两步。当快指针走到链表末尾时慢指针正好在中点。找中点的代码大概是这样LNode *FindMid(LinkList L) { LNode *slow L-next, *fast L-next; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }注意fast-next ! NULL这个判断不能省否则快指针走两步时会解引用空指针。另外链表长度为偶数时返回的是中间偏后的那个节点这个细节在不同题目里要求不一样写之前先确认清楚。判环用的是同一套动作。如果链表里有环快指针一定会在某一刻追上慢指针因为快指针每轮比慢指针多走一步在环里这个相对速度是 1迟早相遇。如果无环快指针会先走到 NULL。这个结论成立的前提是快指针速度是慢指针的两倍如果设成三倍两倍速时也可能相遇但慢指针可能跳过环上的某些节点某些变体题里会因此出错。6.2 合并两个有序链表这个题在面试里出现频率极高思路是维护一个结果链表的尾指针每次比较两个链表当前节点谁小就把谁接上。用带头结点的版本写起来特别顺LinkList MergeList(LinkList A, LinkList B) { LNode *pa A-next, *pb B-next, *r A; while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { r-next pa; pa pa-next; } else { r-next pb; pb pb-next; } r r-next; } r-next (pa ! NULL) ? pa : pb; free(B); return A; }这里有个取巧的地方直接复用 A 的头结点作为结果链表的头省掉一次 malloc最后把 B 的头结点释放掉。这种就地归并的写法在工程里很常见因为它不额外分配节点空间复杂度是 O(1)。代价是原链表 A 和 B 都被破坏了如果调用方后面还要用它们就不能这么写。写之前一定想清楚函数的所有权约定是就地修改还是返回新链表这两种约定在团队协作里必须写进注释。6.3 Python 和 C 的写法差异同样一个单链表换语言写差异很大。Python 里节点就是对象没有指针这个概念你操作的其实是引用class Node: def __init__(self, data): self.data data self.next None def reverse(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prevPython 里你几乎不会遇到段错误因为访问空的属性会抛AttributeError而不是崩掉整个进程而且在循环里把整条链丢给垃圾回收器也不用管。但代价是内存占用更大每个节点对象除了数据还带着一堆解释器层面的开销同样十万个节点Python 的内存占用可能是 C 的好几倍。更关键的是Python 里引用和对象的关系是隐式的写多了容易忘记谁还持有谁反而更难在脑子里画出内存图。C 的写法和 C 类似但可以用nullptr代替NULL用new和delete代替malloc和free另外还有智能指针可以自动管理内存。考试和面试如果允许我倾向于用 C 的nullptr因为类型更安全NULL在重载场景下可能被当成整数 0。6.4 工程里更常见的几种链表变体单链表在真实系统里存在感其实不算高更常见的是它的几个变体。双向链表每个节点多一个前驱指针好处是可以往前遍历、删除当前节点不需要先找前驱代价是每个操作要维护两根指针插错一根就全乱。双向循环链表把首尾连起来很多操作系统里的任务队列就用这种结构取队首和插队尾都是 O(1)。三叉链表在二叉树的存储里会用到每个节点除了左右孩子还有父指针用于需要向上回溯的场景。另外还有一种是带表头长度字段的链表把长度存起来求长度就变成 O(1) 而不是 O(n)这个优化在频繁需要长度的场景里很实用。我个人的建议是学习阶段老老实实把单链表和双向链表各手写一遍不要用现成的库。你手写过一遍之后再看标准库里的std::list或者 Java 的LinkedList就能理解它们为什么在某些操作上有额外的开销也能在选型时做出有依据的判断而不是凭感觉。链表这个东西看十遍不如自己写一遍然后调通一遍这个投入是值得的。心得如果你要准备考研或者面试把这份单链表原码关掉注释重写三遍每遍都自己测一遍边界用例。第一遍看代码回忆第二遍只看题目重写第三遍限时十分钟写完插入删除逆置。三遍下来这类题的通过率基本就稳了。
