链表这个东西但凡你翻开任何一本数据结构教材它基本都排在顺序表后面出场。我刚开始学的时候也没把它当回事觉得数组用得好好的凭空搞出一个指针指来指去的结构图啥。直到有一次写一个需要频繁在中间插入元素的程序数组每次搬数据的开销把我整破防了才真正回过头把单链表从头到尾啃了一遍。这篇就把我自己实现单链表的完整过程、踩过的内存坑、以及几道绕不开的经典变形题重新梳理一遍。核心围绕数据结构、链表、单链表这三个词展开从节点设计讲到完整源码再到调试实录。不管你是正在啃数据结构教材的学生还是准备面试刷题的求职者或者只是想把C语言指针练扎实的人这篇都能直接拿去用代码可以编译运行思路可以照着复现。1. 为什么数组不够用——从链表存在的理由说起1.1 数组的三个硬伤要用好一个数据结构第一步永远是搞明白它到底为了解决什么问题而生。顺序表也就是我们常说的数组最大的优点就是随机访问只要你给个下标arr[i]一步就能定位到元素时间复杂度 O(1)。这个优点太香了导致很多人习惯了数组之后就再也懒得看别的结构。但是数组有三个绕不开的硬伤。第一个是容量固定。C语言里你声明int arr[100]它就占着 400 字节不动了你存 5 个元素浪费想存 101 个又直接越界。你可能说可以用动态数组realloc扩容啊对但扩容的代价是把整块老数据全部搬到新地址这个搬运的成本是 O(n)。第二个硬伤是中间插入和删除代价高。假设你要在数组第 0 位插入一个元素后面 999 个元素全部得往后挪一格一次插入就是 O(n)。删除同理。第三个是内存必须连续。你要开一个 100 万的数组操作系统得给你找到一整块连续的 4MB 空间内存碎片一多就可能分配失败。提示判断该不该用链表核心就一句话——你的操作是查得多还是改得多。查得多用数组改得多才考虑链表。1.2 链表用指针换来的灵活性链表解决上面三个问题的思路非常直接我不要求元素挨着放了每个元素自己记住下一个元素在哪。这样一来元素可以散落在内存的任意角落插入删除的时候只要改几个指针不用搬数据代价直接降到 O(1)前提是你已经拿到了要操作位置的前驱节点指针。代价是什么呢代价就是你失去了随机访问能力。想找第 100 个元素次数没法算只能从头一个个往下数时间复杂度变成 O(n)。而且每个节点除了存数据还要额外存一个指针这叫空间换时间在 64 位机器上一个指针就是 8 字节的开销。所以链表不是更高级的数据结构它只是做了不同的取舍。我个人的经验是当你的数据规模不确定、需要频繁增删、并且对随机访问要求不高时链表才有意义。比如操作系统里的空闲内存块管理、哈希表解决冲突用的拉链法、LRU 缓存淘汰算法里的双向链表这些都是链表的经典战场。1.3 单链表、双链表、循环链表该选谁刚开始学的时候容易迷糊链表家族到底怎么分。其实按两个维度拆就清楚了类型指针方向能否反向遍历典型用途单链表只有 next不能内存最省栈、简单队列双链表next prior能LRU、需要前驱的场景循环链表尾节点指回头看单双约瑟夫环、轮询调度单链表是最基础的一种把它的指针操作吃透了双链表和循环链表基本就是加一个指针或者改一下尾部指向的事。所以这篇先把单链表讲穿其他的后面自然就通了。2. 单链表的骨架——节点、头指针与内存布局2.1 节点结构体为什么这么定义单链表的最小单元叫节点Node一个节点里装两样东西一份数据一个指向下一个节点的指针。用C语言描述出来就是这么几行typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域指向下一个同类型节点 } LNode, *LinkList;这里有个新手必问的点为什么next的类型写的是struct LNode *而不是LNode *因为typedef还没执行完在结构体内部LNode这个别名还不存在编译器不认识它所以必须老老实实写完整的struct LNode。这是C语言语法的一个经典细节考试爱考实际写代码也必须这么写否则直接编译报错。typedef后面同时起了两个名字LNode表示节点本身LinkList表示指向节点的指针。这样写的好处是语义清晰我们声明头指针时用LinkList L声明临时节点时用LNode *p一眼就能看出这个变量是表还是节点。当然你也可以只留一个名字纯属风格问题但在教材和面试里这两种写法都很常见看懂就行。2.2 带头结点还是不带头结点这是个问题这是单链表实现里第一个真正的分岔口。带头结点的意思是我们额外申请一个节点放在链表最前面它不存有效数据也可以拿来存表长它的next才指向第一个真实元素。不带头结点就是头指针直接指向第一个真实元素。对比项带头结点不带头结点第一个位置的插入/删除和其他位置统一处理需要单独写分支改头指针空表判断L-next NULLL NULL代码复杂度低边界统一高处处要考虑头指针变化是否浪费一个节点浪费一个不浪费我强烈建议初学和考试都用带头结点的版本。原因很实在不带头结点时你在第 1 个位置插入元素必须修改头指针本身而修改头指针意味着函数参数得传二级指针LinkList *L但在第 2 个及以后的位置插入又不需要改头指针。这种有时要改有时不用改的差异会让你的代码到处是if分支极易写错。带头结点把这个差异抹平了所有位置的插入删除逻辑完全一致。那一个节点的空间开销换来代码整洁和调试省心太值了。2.3 一张图看懂指针的走向不画图很难讲清楚我用文字给你描述一遍内存里的样子。假设我们存了 3 个元素 7、13、29带头结点的链表在内存里大概长这样这里的数字是示意地址头指针 L - [ 头结点 | next ] - [ 7 | next ] - [ 13 | next ] - [ 29 | nextNULL ] 地址0x100 0x200 0x300 0x400注意三个关键点。第一头指针 L 永远指向头结点头结点永远不动这是带头结点结构稳定的根基。第二物理地址 0x100、0x200 这些是不连续的它们之间靠next指针串起来这就是链表和数组最大的区别。第三最后一个节点的next必须是NULL这是遍历能停下来的唯一依据忘了置空或者置错程序就会一路读下去直到崩溃。理解了这张图后面所有的插入删除操作本质都是在改这几根箭头。3. 单链表核心操作逐个拆解3.1 初始化与两种建表方式头插法和尾插法初始化就是造出那个头结点并把它的next置空表示一条空表。注意参数是LinkList *L的二级指针形式因为我们改的是调用方那个头指针变量本身bool InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); // 申请头结点 if (*L NULL) return false; // 内存申请失败要兜底 (*L)-next NULL; // 空表next置空 return true; }这里malloc之后一定要判空。很多人图省事不判平时跑没问题但一旦在嵌入式或内存紧张环境里malloc返回NULL紧接着(*L)-next就是往地址 0 写数据直接段错误。这是好习惯不是多余。建表有头插法和尾插法两种。尾插法读入的顺序和链表里元素的顺序一致逻辑是维护一个尾指针r每来一个新节点就挂到r后面然后r前移到新节点。头插法正好相反每个新节点都插到头结点后面最终链表里的顺序和输入顺序完全颠倒。头插法有个额外好处它天然实现了逆序所以不用额外的反转函数就能把一串数据倒过来建表。// 尾插法顺序一致 void List_TailInsert(LinkList L, int arr[], int n) { LNode *r L; // r 是尾指针一开始指向头结点 for (int k 0; k n; k) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data arr[k]; r-next s; // 新节点挂到尾部 r s; // 尾指针后移 } r-next NULL; // 收尾置空千万别忘 } // 头插法顺序颠倒 void List_HeadInsert(LinkList L, int arr[], int n) { for (int k 0; k n; k) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data arr[k]; s-next L-next; // 新节点先接住原来的第一个 L-next s; // 头结点再指向新节点 } }尾插法最后那句r-next NULL是最容易被漏掉的。如果你忘了最后一个节点的next就是个野值打印的时候程序会顺着这个随机地址读下去轻则打印一堆乱码重则段错误。我踩过这个坑debug 花了半小时最后发现就是少写一行。3.2 查找按位查找和按值查找的边界处理按位查找是给一个序号i返回第i个节点。这里有个细节必须厘清带头结点时头结点算第 0 个节点第一个真实元素才是第 1 个。所以从头结点出发走i步正好停在第i个节点上。LNode *GetElem(LinkList L, int i) { if (i 0) return NULL; // 序号非法 LNode *p L; int j 0; // j 记录当前 p 是第几个节点 while (p ! NULL j i) { // 走到第 i 个或者走到底 p p-next; j; } return p; // 可能返回NULL调用方要判 }这个函数的返回值可能是NULL比如i超过了表长调用方拿到结果后必须判空否则后续p-next直接崩。按值查找LocateElem逻辑类似从头结点的下一个开始逐个比对找到就返回节点指针找不着返回NULL。这两个查找平均都是 O(n)因为链表没法像数组那样一步定位。注意面试里经常考GetElem 走了几步这种问题记住带头结点时取第 i 个元素需要从头结点走 i 步时间复杂度 O(i)。3.3 插入与删除指针操作的顺序是命门插入和删除是单链表最容易写错的地方因为指针操作的顺序不能乱。先说插入要在第i个位置插入新元素先找到第i-1个节点p然后bool ListInsert(LinkList L, int i, int e) { if (i 1) return false; LNode *p GetElem(L, i - 1); // 找到前驱节点 if (p NULL) return false; // 前驱不存在位置非法 LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return false; s-data e; s-next p-next; // 第1步新节点先接上后继 p-next s; // 第2步前驱再指向新节点 return true; }关键就在最后两句的顺序。必须先把新节点的 next 指向原来的后继再让前驱的 next 指向新节点。如果你写反了先执行p-next s那原来p后面的那一串节点就全丢了因为没有任何指针还记着它们的地址内存泄漏加断链。这个顺序的道理其实很简单你得先让自己站稳了再去动别人的指针否则中间状态就会丢失信息。删除也是同款逻辑。找到第i-1个节点p它后面那个q p-next就是要删的bool ListDelete(LinkList L, int i, int *e) { if (i 1) return false; LNode *p GetElem(L, i - 1); if (p NULL || p-next NULL) return false; // 前驱或目标不存在 LNode *q p-next; *e q-data; // 保存被删数据 p-next q-next; // 前驱跨过q直接连到q的后继 free(q); // 释放节点防止泄漏 return true; }删除里两个细节一是先用一个临时指针q记住要删的节点不然改完p-next你就找不到它了没法free二是删除后free(q)必须调不调就是内存泄漏。很多人写链表删除忘了free程序跑起来看着没毛病但内存一路涨直到某次malloc失败。4. 单链表完整源码可直接编译运行4.1 结构定义与函数声明把上面的碎片拼起来就是一份完整的、可以直接gcc编译跑起来的单链表实现。我按从易到难的顺序组织函数顶部是结构定义#include stdio.h #include stdlib.h #include stdbool.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; bool InitList(LinkList *L); void List_TailInsert(LinkList L, int arr[], int n); void List_HeadInsert(LinkList L, int arr[], int n); LNode *GetElem(LinkList L, int i); LNode *LocateElem(LinkList L, int e); bool ListInsert(LinkList L, int i, int e); bool ListDelete(LinkList L, int i, int *e); void PrintList(LinkList L); LinkList Reverse(LinkList L); void DestroyList(LinkList *L);4.2 全部函数实现查找和插入删除前面已经给过这里补上打印、反转和销毁三个凑成完整的一份void PrintList(LinkList L) { LNode *p L-next; // 跳过头结点从第一个真实元素开始 while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 迭代法反转三个指针 pre / p / next 一路翻转箭头 LinkList Reverse(LinkList L) { LNode *pre NULL; LNode *p L-next; while (p ! NULL) { LNode *next p-next; // 先记住后继 p-next pre; // 箭头反向 pre p; // pre 前移 p next; // p 前移 } L-next pre; // 头结点接到新的第一个节点 return L; } void DestroyList(LinkList *L) { LNode *p *L; while (p ! NULL) { LNode *q p-next; // 先存后继 free(p); // 再释放当前 p q; } *L NULL; // 头指针置空防止悬空 }反转这一段是面试高频题pre / p / next三个指针的角色要分清楚p是当前正在处理的节点pre是它前面已经反转好的部分next是临时保存的未处理部分。循环里先存后继、再翻转、再集体前移这三步一气呵成。判断条件p ! NULL保证链表走到尽头就停。销毁函数同理先存后继再 free 当前顺序反了就访问了已释放内存。4.3 测试用例与实测输出主函数里跑一遍全流程造表、打印、插入、删除、反转、销毁一条龙验证int main(void) { LinkList L; InitList(L); int arr[] {7, 13, 29, 42, 55}; List_TailInsert(L, arr, 5); printf(尾插建表: ); PrintList(L); // 7 13 29 42 55 ListInsert(L, 3, 99); printf(第3位插入99: ); PrintList(L); // 7 13 99 29 42 55 int del; ListDelete(L, 1, del); printf(删除第1位(%d): , del); PrintList(L); // 13 99 29 42 55 Reverse(L); printf(反转后: ); PrintList(L); // 55 42 29 99 13 LNode *found LocateElem(L, 29); printf(查找29: %s\n, found ? 找到了 : 没找到); DestroyList(L); printf(销毁后 L %s\n, L NULL ? NULL : 非空); return 0; }我实测下来的输出完全符合预期每一步的链表内容都和注释里标注的一致。这里ListDelete的第三个参数传的是del因为函数要把被删元素带回来所以用指针接收。这个设计在考试里很常见比单纯删除多了个数据回传的功能。你把这整份代码存成一个list.cgcc list.c -o list编译./list跑一下就能看到全部结果。实操心得验证链表代码对不对最省事的办法就是每做一步操作就PrintList打印一次肉眼比对。链表出错往往不是崩溃就是静默断链打印能最快暴露问题。5. 高频踩坑、调试实录与经典变形题5.1 段错误、内存泄漏排查清单写链表代码八成的崩溃都能归到下面几类我按自己被坑的频率排个序症状常见原因排查方向编译报错 unknown type结构体内部写了LNode *而非struct LNode *检查 typedef 内部类型名打印出现乱码/死循环尾部节点next没置NULL检查建表末尾遍历到一半段错误用 NULL 指针去访问-next循环里加p ! NULL判断内存持续增长删除时忘了free检查每个删除分支插入后断链丢数据p-next s写在了s-next p-next前面检查指针操作顺序free 后崩溃释放后又访问了该节点先存后继再 free关于段错误我最想强调的是循环条件里对 NULL 的判断。像while (p-next ! NULL)这种写法在链表非空时没事一旦链表为空p本身可能就是NULL这时p-next直接越界访问。稳妥的写法是while (p ! NULL ...)先判 p 自己再访问它的成员短路求值会保护你不越界。5.2 反转链表等经典题型单链表吃透之后有几道经典题基本是绕不过去的我挑两个最常考的说思路。第一道是寻找中间节点要求只能遍历一次。技巧是快慢指针慢指针每次走一步快指针每次走两步快指针走到尾部时慢指针正好在中间。这个技巧在判断链表有没有环、找倒数第 k 个节点等题目里反复出现是单链表面试的万能钥匙。第二道是合并两个有序链表思路是双指针 尾插两个指针分别指着两条链表谁小就拿谁尾接到结果链表后面然后该指针后移直到一条走空再把另一条剩下的整段挂上去。这类题的关键永远是用哨兵节点也就是头结点简化边界避免结果链表的头节点单独处理。// 快慢指针找中间节点 LNode *FindMid(LinkList L) { LNode *slow L-next, *fast L-next; while (fast ! NULL fast-next ! NULL) { slow slow-next; // 慢指针走1步 fast fast-next-next; // 快指针走2步 } return slow; // 偶数个节点时返回靠后的中间 }注意快指针的判断条件是fast ! NULL fast-next ! NULL两个都不能少。只写fast-next ! NULL的话节点数为偶数时fast会变成NULL再取fast-next就崩了。这个细节我在模拟面试里见过太多人栽跟头。5.3 几个容易被忽视的实操细节再补几个教材上不太讲、但实际写起来很有用的经验点。第一销毁链表和清空链表是两回事。销毁是把所有节点包括头结点全free掉头指针置NULL清空只是把数据节点删掉、保留头结点让链表回到空表状态。你要是把这两个搞混要么该清空的时候把头指针弄没了要么该销毁的时候留了个孤零零的头结点导致泄漏。第二传参时的指针层级要数清楚。凡是需要修改头指针本身的操作初始化、销毁函数参数都得是LinkList *L二级指针凡是只修改节点内部next的操作插入、删除传一级的LinkList L就够了。判断方法很简单问自己这个操作会不会让调用方的头指针变量换个指向会就用二级不会就一级。这块我建议你拿张纸画一下调用栈一眼就清楚。第三malloc出来的节点地址不保证连续别拿它去做任何基于地址连续性的假设。有些新手看到链表节点地址不连续会觉得奇怪其实这正是链表的正常状态恰恰是它的设计初衷。要是地址连续了那它跟数组还有什么区别。第四调试链表优先用打印而不是断点。链表结构复杂断点单步容易迷失在指针里不如在关键操作前后插PrintList把每一步的形态都打印出来对照效率高得多。配合一个能打印节点地址的辅助函数断链、环、野指针无所遁形。这套调试习惯是我从无数次深夜 debug 里攒出来的比任何技巧都实在。最后说个我个人踩过的坑收尾。我刚开始写单链表时最烦的就是什么时候传二级指针、什么时候传一级总是靠死记硬背。后来自己动手把那张内存图画了三遍把初始化、插入、删除三个操作在纸上把指针的每一次变化都标出来突然就通透了——原来判据根本不用背就问一句这个动作会不会改变调用方手里的那个头指针答案自然就出来了。链表这东西看十遍不如自己动手敲一遍敲完再画一遍图基本就刻在脑子里了。你可以拿这份代码当骨架把里面的函数一个个自己默写出来默到不看答案也能一次写对单链表这关就算真正过了。