数据结构初学者绕不开的一块内容是单链表，单链表的应用几乎遍布在系统底层和各类算法里。很多人学链表停留在“会背代码”的阶段，一到实战就不知道怎么用。这篇笔记归纳单链表最核心的应用思路、常见场景和踩坑点，适合刚学完链表基本操作、想搞懂“链表到底能干什么”的读者。

先给一个基本判断：数组能做的事，链表大多也能做，但两者适用场景完全不同。链表最大的价值是插入和删除不需要挪动大量元素，代价是随机访问能力很弱。初阶阶段不要追求把链表玩出花，先把头插、尾插、删除、反转这些动作吃透，再把几个经典应用案例动手写一遍，远胜于背十遍定义。

1. 单链表到底是什么：从数组的痛点说起

1.1 数组的“身份证”和链条的“线索”

数组在内存里是一块连续空间，每个元素有固定下标。你只要告诉程序“第几个”，它就能直接算出地址，这叫随机访问。但连续空间带来的麻烦也明显：要在中间插入一个元素，后面的数据全部得往后挪；删除同理。更难受的是，数组长度一开始就要定好，或者用动态扩容，一次扩容可能要重新分配整块内存、全量拷贝老数据。

单链表换了个思路。它不要求元素在内存中挨着，每个节点里除了存数据，还要存一个指针，指向下一个节点。就像一群人站成一排，每个人只知道自己后面是谁，从头一个人开始顺着线索一个个往后找，才能找到想要的人。这个“线索”就是 next 指针。

为什么这种方式适合“频繁插入删除”的场景？因为对链表来说，插入和删除只需要改相邻节点的指针，不需要动后面所有数据。比如在第 3 个节点后面插一个新节点，只需要让新节点先指向原第 4 个节点，再让原第 3 个节点指向新节点，两步指针操作就完成，和链表长度完全无关。

1.2 物理不连续带来的三个直觉

学单链表时，先把三个和数组不一样的地方刻在脑子里。

第一，链表没有一个天然的“第 i 个元素”概念。想找第 5 个节点，必须从头节点出发，数 5 次 next。所以遍历是链表最基础、最频繁的动作，几乎所有操作都建立在遍历之上。

第二，链表长度可以是动态的。节点用的时候动态申请，不用就释放，理论上内存够用就能一直往下挂。这让链表天然适合做“数量不确定”的数据结构。

第三，链表多了一个“头指针”的概念。头指针是整个链表的入口，任何操作丢失了头指针，整条链表就找不回来了。实际开发里最常见的严重事故，就是函数里改了头指针但没对外更新。

许多初阶教材会把“带头结点”和“不带头结点”放在一起讲。我的建议是：初学阶段把“不带头结点的版本”理解透，再对比“带头结点”的差异。带头结点相当于额外加了一个永远存在的哨兵节点，好处是空链表也统一处理逻辑，插入删除代码不用分好几种情况。但从理解本质上讲，不带头结点的版本更能逼你考虑空链表、首节点被删除等边界情况，这对后面的工程素养很有帮助。

2. 单链表的实战设计：几个绕不开的核心操作

2.1 头插法和尾插法怎么选

先看最常用的两个构建链表方式。头插法是把新节点插到链表头部，代码短、效率高，但生成结果是逆序的。尾插法是顺着链表走到最后一个节点，再挂新节点，顺序正确，但每次都要遍历到尾，需要维护一个尾指针来优化。

实际数据录入时，如果你希望保持原始的读入顺序，用尾插法自然直观。如果只是临时快速建链、不在乎顺序，用头插法更干脆。

头插法最容易犯的错是顺序不对。正确动作是：

newNode->next = head; head = newNode;

如果先写了head = newNode;再改 newNode->next，链表就断了，后面的节点全部丢失。尾插法也不复杂，但必须处理“链表为空”的情况。空链表时，尾插等价于让 head 直接指向新节点，否则先走到最后一个节点，再把新节点接上去。

提示：很多初学着写尾插时总忘了维护尾指针，结果每插一次都从头遍历。数据量小感觉不到，数据量大了就会明显变慢。工程上做队列之类需求时，一定要额外记录 tail，并且每次插入后把头尾状态同步更新。

2.2 按值删除和按位置删除的坑

删除操作是单链表最容易写崩的地方之一。核心原则只有一条：改指针之前，先把要删除的那个节点记住。

按位置删除，比如删除第 k 个节点，需要先找到第 k-1 个节点，然后：

Node* toDelete = current->next; current->next = toDelete->next; free(toDelete);

这段代码看起来简单，但有三处最容易翻车。第一，k 是不是从 1 开始？如果题目要求删除第 0 个，那就是删除头节点，代码逻辑和删除中间节点不一样。第二，链表可能不够长，遍历到末尾还没到目标位置，就不能继续 next 下去了。第三，如果删的是最后一个节点，删除后尾部指针要更新。

按值删除通常要处理“链表中可能有多个相同值”的情况。有的题目要求只删第一个，有的要求全部删除。只删第一个，找到后立刻 free 并返回。全部删除，就得完整遍历，删除一个后不要急着直接跳下一个，因为下一个可能还要删。

我在实际调试中见过一个很典型的 bug：删除节点后没有让外部头指针感知。如果删除的是第一个节点，函数内部把头指针改了，但外部仍然拿着旧的头指针，下一次访问就直接读到野指针。解决办法是用二级指针，或者把新头返回出去，二者选一个并在整个项目里坚持统一，不要一会儿用一级一会儿用二级。

2.3 反转链表：迭代和递归两条路

反转链表几乎是单链表应用里出镜率最高的题，也是理解指针操作的分水岭。迭代法的思路很朴素：准备三个指针，分别指向前一个、当前、后一个。每次循环，让当前节点指向前一个节点，然后整体往后平移一个节点。

代码结构大概是这样的思路：

Node* prev = NULL; Node* current = head; while (current) { Node* next = current->next; current->next = prev; prev = current; current = next; } return prev;

这段代码的关键在于“先保存 next”。因为 current->next 被改写以后，再想通过 current 找到原来的下一个节点就找不到了。所以每次必须先存 next，再改指针方向。

递归法让很多初学者迷糊，但它写起来更简洁。递归的天然思路是：先把从第二个节点开始的子链表反转，得到新的头；再把原来的头接到子链表反转后的尾部。这里需要边返回新头、边让新链表的尾巴指向原来的头。初学阶段如果迭代法已经能写熟，递归可以慢慢理解，不必死磕，因为两个方法面试和工程里都会遇到。

反转链表的应用不止是做题。比如双向数据展示的方向切换、链表的头尾互换、判断回文链表时，都经常需要反转一半链表来对比。所以不要小看这二十行代码，它背后是把“指针移动顺序”这个基本功练扎实的关键。

3. 单链表的典型应用场景拆解

3.1 约瑟夫环与循环链表思想

约瑟夫环是一个非常经典的问题：一群人围成一圈，按固定步长报数，数到某个数字的人出列，然后从下一个人继续，直到剩下最后一个。用单链表解决时，最常见的是把链表尾节点的 next 指向头节点，形成一个循环链表。

做法不复杂，但每一步都要小心。比如步长是 m，最终应该循环数 m-1 次找到待删除节点的前驱，而不是直接数 m 次，否则想删除的节点定位会偏一位。

我在初学时期犯过一个印象很深的错：删完节点后，没把下一次计数的起点指对。约瑟夫问题的规则是“从被删除位置的下一个节点开始继续报数”，所以删除操作结束后，遍历的 current 应该停留在被删节点的前一个节点。这样才能保证下一轮数 m-1 次后，自然而然地到达下一个要删除的节点。

循环链表在这里的优势就是“自动回到起点”，不需要每次都判断是否到了末尾。

3.2 LRU 缓存淘汰的朴素实现

缓存淘汰策略里有一个很出名的 LRU 算法，它的朴素结构就是用双向链表加哈希表。但初阶阶段如果只想理解“链表怎么用在淘汰场景”，用单链表也能模拟思路。

核心逻辑是：越久没被访问的数据排在越后面，一旦访问了某个数据，就把它移到链表头部。缓存放满时，淘汰链表尾部。这个逻辑里，链表头部代表“最近使用过”，链表尾部代表“最久没使用”的数据。

用单链表实现时，难点在“移动到头部”之前必须先找到它的前驱节点。为了找前驱，你得从头开始遍历，效率为 O(n)。这也是为什么工业级 LRU 大多使用双向链表的原因，因为双向链表能直接拿到前驱，但先理解单链表版本，再对比“为什么需要双向链表”，印象会深得多。

面试时如果能把“单链表版本怎么实现、问题在哪里、为什么换成双向链表”完整讲清楚，通常比只会背双向链表代码更有说服力。

3.3 多项式合并与大数运算

单链表另一个经典应用是表示多项式。每一项作为一个节点，存储系数和指数，Node 里除了 data 还要多一个指数。多项式相加时，只需要按指数降序依次比较两个链表的当前项，哪个指数大就先把哪项加入结果链表；指数相同就系数相加，和为 0 就舍弃这一项。

大数运算也类似。C 语言里的整型有范围上限，要想表示一个几百位的数字，普通变量装不下。可以把一个数字按位拆成一个个节点，比如从低位到高位挂在链表上。加法时从表头方向逐位相加，处理进位。这其实是在自己造高精度计算，比直接数组实现多了一道“动态确定长度”的好处，但实现时要自己管理节点，麻烦程度也会上升一截。

这类“结构体里多带一个字段”的应用思路很值得掌握。初阶学习者很容易把链表想成只有 data 和 next，实际上工程中链表节点里经常放复杂结构体，甚至内嵌一个小结构体。数据域可以是一个坐标点、一条日志、一个任务描述，next 才是负责串起所有节点的“骨架”。

所以我建议初阶阶段把链表的注意力放在“指针把不连续内存串起来”的思想，而不是死记某种固定定义。理解了这一点，后面学双向链表、循环链表、哈希表拉链法等结构时，会发现它们全在同一个思想框架内，只是额外加了不同约束。

4. 从代码到运行的完整实操记录

4.1 一个可复现的 C 语言最小实现

要把前面的操作落地，还是得写代码。这里给出一份我自己常用来演示的完整最小实现，包含创建节点、头插、尾插、打印、按值删除和释放链表。代码尽量保持简短，方便初阶读者直接复现。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; Node* createNode(int value) { Node* node = (Node*)malloc(sizeof(Node)); if (node == NULL) { printf("内存分配失败\n"); exit(1); } node->data = value; node->next = NULL; return node; } void insertAtHead(Node** head, int value) { Node* node = createNode(value); node->next = *head; *head = node; } void insertAtTail(Node** head, int value) { Node* node = createNode(value); if (*head == NULL) { *head = node; return; } Node* current = *head; while (current->next != NULL) { current = current->next; } current->next = node; } void deleteByValue(Node** head, int value) { if (*head == NULL) return; if ((*head)->data == value) { Node* temp = *head; *head = (*head)->next; free(temp); return; } Node* current = *head; while (current->next != NULL) { if (current->next->data == value) { Node* temp = current->next; current->next = temp->next; free(temp); return; } current = current->next; } } void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } void freeList(Node* head) { Node* current = head; while (current != NULL) { Node* temp = current; current = current->next; free(temp); } } int main() { Node* head = NULL; insertAtTail(&head, 10); insertAtHead(&head, 20); insertAtTail(&head, 30); printList(head); deleteByValue(&head, 20); printList(head); freeList(head); return 0; }

这份代码里我统一使用二级指针修改头节点。为什么不直接用一级指针？因为不管是头插还是删除头节点，都可能直接改变外部那个 head 变量的值。C 语言函数参数是值传递，如果只传入一级指针，函数里改动 head 后，外部根本感知不到。

二级指针相当于把“head 这个变量本身”的地址传进去，函数内部通过解引用才能改到真正的头指针。工程中有的人喜欢用返回值，比如head = insertAtHead(head, 20);，也完全可以。两种风格都好，但切忌两种混用。

4.2 编译、运行与测试思路

把上面代码保存成list_demo.c，在装有 gcc 的终端里执行：

gcc -Wall -g list_demo.c -o list_demo ./list_demo

用了-Wall会提示所有可见警告，-g是为了生成调试信息。我强烈建议初学阶段保留这两个选项，不要只写gcc list_demo.c -o list_demo。一个很小的警告可能就是一个隐雷。

运行结果应该会打印两条链，第一条是20 -> 10 -> 30 -> NULL，第二条删除 20 后变成10 -> 30 -> NULL。打印NULL到末尾这一步很重要，它能帮你直观确认链表的结束条件写对了没有。

单测思路建议按这个顺序：

• 空链表中删除一个值，程序不崩溃。
• 删除头节点，打印结果确认头指针更新。
• 删除尾节点，打印结果确认尾部正确置空。
• 连续删除同一个值多次，保证第二次能找到剩余节点。
• 反复插入大量节点，观察最后释放时是否有崩溃。

如果能把这五个场景用一个测试函数跑完，你对单链表的信心会比只是看代码大很多。我经常跟初学者说，链表很难一次写对，但只要把边界情况用测试覆盖住，调试效率会高很多。

5. 常见问题与排查技巧实录

5.1 空指针解引用是万恶之源

写链表时遇到的崩溃，一半以上是空指针问题。典型场景是：循环条件写成current->next != NULL，但 current 本来就可能是 NULL。比如在 deleteByValue 里，链表为空时直接访问了(*head)->data，程序就崩了。

更常见的隐性空指针是“删除后忘记置 NULL”。刚把节点 free 掉，局部变量还残留着指向这块内存的地址。后续误用这个地址时，可能读出一堆乱七八糟的值，或者再次 free 直接触发 double free。初学阶段可以养成习惯：free(temp); temp = NULL;，哪怕临时变量也顺手置空。

检查这类问题的技巧是打印指针地址。我在调试链表时经常在关键位置打印当前指针，比如：

printf("current=%p, current->next=%p\n", current, current->next);

看到某个指针是 0x0 却还在取它的 next，基本就是空指针问题了。

5.2 内存泄漏和悬垂指针

内存泄漏在链表代码里特别隐蔽。freeList 里如果没有逐节点释放，或者只释放了头节点，其余节点就会变成不可达的内存垃圾。进程长期运行时，泄漏会越积越多，最后被系统杀掉。

悬垂指针的问题则和内存泄漏相反：内存已经释放，指针还指着那块地。释放之后如果有代码继续通过旧指针访问，属于未定义行为。有些情况下程序表面还能跑，但实际上数据已经被破坏，排查起来相当折磨。

我在实际练习里遇到过这样一件事：我在 deleteByValue 之后继续遍历链表，遍历用的是早就存下来的另一个指针，而不是重新从头开始。结果每次运行结果都不一样。后来打印指针才发现，那个指针指向的节点已经被 free 掉了，它的内存被后续的插入操作重新使用，打印出来的数据完全不对。

这个教训让我养成了一个习惯：链表操作完成后，如果需要继续使用某个指针，必须判断它指向的节点是“仍然在链表中”还是“已经脱离了链表”。否则就从头重新遍历，或者直接置空。

5.3 调试链表问题的三个土办法

在系统学习调试器之前，有几个土办法效率很高，个人强烈推荐。

第一个是“画图”。遇到指针绕不清楚时，拿笔和纸画出三个方框：前一个节点、当前节点、下一个节点。每一步操作都把箭头重新画一遍，基本一眼就能看出哪里断链。好多看似复杂的问题，画完图就发现是最简单的顺序写错。

第二个是“加打印看每步”。主要针对遍历逻辑。每进入一个循环或每次修改指针后都打印当前节点的值和当前指针地址。虽然输出会比平时多，但你能清楚地看到程序走了哪条路、循环是死循环还是提前退出。

第三个是“构造最小用例”。链表崩溃时，先别直接面对几十个节点的数据，而是用一个只有两三个节点的链表复现。两三个节点时，每一步指针关系都一目了然。如果最小用例不能再现问题，再慢慢扩充数据量。这个过程很像剥洋葱，能快速缩小排查范围。

这三个方法不依赖任何复杂工具，只需要一个可编译的代码环境和一点耐心。等到熟练以后，再考虑用调试器设置断点、单步观察内存，理解会顺畅得多。

另外还有一个经验：所有修改链表的函数，入参最好都改成二级指针或者返回值，并且在函数名里明确体现“可能修改外部头节点”。比如insertAtHead(Node** head, int value)，一看就知道会动头部。如果函数名不清不楚，时间一长，调用方很容易忘记传二级指针，导致修改丢失。

后期扩展时，链表还能往多个方向做。正着遍历能求长度、找中间节点，反着处理能反转、回环判断。双指针技巧比如快慢指针找链表中点、判断链表是否有环，都是基于单链表基础应用的进阶玩法。先把这篇笔记里的操作吃透，再去看那些题目，基本都是一通百通。我个人的体会是，链表写不熟的人，后面学树和图都会心慌，因为树就是“有多个 next 的链表”，图又是“更复杂的链接结构”。所以初阶阶段多花点时间在单链表上，真的不亏。