链表这个东西，但凡你翻开任何一本数据结构教材，它基本都排在顺序表后面出场。我刚开始学的时候也没把它当回事，觉得数组用得好好的，凭空搞出一个"指针指来指去"的结构图啥。直到有一次写一个需要频繁在中间插入元素的程序，数组每次搬数据的开销把我整破防了，才真正回过头把单链表从头到尾啃了一遍。这篇就把我自己实现单链表的完整过程、踩过的内存坑、以及几道绕不开的经典变形题重新梳理一遍。核心围绕数据结构、链表、单链表这三个词展开，从节点设计讲到完整源码，再到调试实录。不管你是正在啃数据结构教材的学生，还是准备面试刷题的求职者，或者只是想把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 == NULL | L == NULL |
| 代码复杂度 | 低，边界统一 | 高，处处要考虑头指针变化 |
| 是否浪费一个节点 | 浪费一个 | 不浪费 |
我强烈建议初学和考试都用带头结点的版本。原因很实在：不带头结点时，你在第 1 个位置插入元素，必须修改头指针本身，而修改头指针意味着函数参数得传二级指针LinkList *L；但在第 2 个及以后的位置插入，又不需要改头指针。这种"有时要改有时不用改"的差异会让你的代码到处是if分支，极易写错。带头结点把这个差异抹平了，所有位置的插入删除逻辑完全一致。那一个节点的空间开销，换来代码整洁和调试省心，太值了。
2.3 一张图看懂指针的走向
不画图很难讲清楚，我用文字给你描述一遍内存里的样子。假设我们存了 3 个元素 7、13、29，带头结点的链表在内存里大概长这样（这里的数字是示意地址）：
头指针 L -> [ 头结点 | next ] -> [ 7 | next ] -> [ 13 | next ] -> [ 29 | next=NULL ] 地址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.c，gcc 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 里攒出来的，比任何技巧都实在。
最后说个我个人踩过的坑收尾。我刚开始写单链表时，最烦的就是"什么时候传二级指针、什么时候传一级"，总是靠死记硬背。后来自己动手把那张内存图画了三遍，把初始化、插入、删除三个操作在纸上把指针的每一次变化都标出来，突然就通透了——原来判据根本不用背，就问一句"这个动作会不会改变调用方手里的那个头指针"，答案自然就出来了。链表这东西，看十遍不如自己动手敲一遍，敲完再画一遍图，基本就刻在脑子里了。你可以拿这份代码当骨架，把里面的函数一个个自己默写出来，默到不看答案也能一次写对，单链表这关就算真正过了。
