单链表这个题目，几乎每个学C语言的人都绕不过去。但说实话，我在带新人或者看论坛帖子的时候发现，很多人对链表的理解停留在“能写出代码”这个层面，背模板一样把插入删除的指针操作抄下来，一旦遇到内存泄漏、野指针、边界条件就直接懵掉。这篇文章我想换个角度，不单纯讲链表是什么，而是从“为什么要这样设计”“内存里到底发生了什么”这些底层逻辑讲起，再配合完整的可运行代码和调试经验，把单链表真正讲透。不管你是刚学完指针的初学者，还是正在准备机试、面试的在校生，又或者是工作中需要手写数据结构的老手，这篇文章都值得你花二十分钟认真读一遍。
1. 为什么是链表：数组的痛点与链表的解法
1.1 数组在动态场景下的三个尴尬处境
很多教材习惯用“数组和链表的对比表”来引入链表，但我觉得先看实际场景更有感觉。比如你在写一个学生成绩管理系统，要动态录入学生信息，你根本不知道最终会有多少人。如果直接用数组，通常会这么处理：
#define MAX_SIZE 1024 int scores[MAX_SIZE];这就带来了第一个尴尬：你预估了上限，但现实可能超出来。1024个不够用，程序就崩；如果只来了10个学生，剩下的1000多个int空间就白白占着。第二个尴尬是插入和删除的成本。数组在内存里是连续存放的，你要在中间插入一个元素，后面的所有元素都得往后挪，时间复杂度是O(n)。如果这个数组有一万个元素，每次都挪，程序的性能肉眼可见地拉胯。第三个尴尬不那么明显，但更致命：数组的扩容很麻烦。你以为可以用realloc？确实可以，但realloc往往涉及整块内存的拷贝，而且一旦失败，你的原指针还可能被置空，处理不好就是事故现场。
1.2 链表的本质：用指针把“零散”变成“连续”
链表解决的就是上面这三个问题。它的核心思想是：不要求内存连续，每个节点（Node）自己存数据，同时存一个指向下一个节点的指针。这样，你想加一个学生，只需要在堆上申请一个新节点，把指针链上去就行；想删除一个学生，只需要把前后两个节点“绕过去”接上，然后释放掉那个节点。
内存上看起来东一个西一个的节点，通过指针在逻辑上形成了连续的结构。这就像火车车厢，物理上每节车厢是独立的，但通过挂钩连成一列。你要加一节车厢，不需要把整列火车推到铁轨尽头重新拼接，只需要在合适的位置加一个挂钩就行——这就是链表最大的优势。
当然，链表也不是没有代价。每个节点除了数据外还要额外存一个next指针（在64位系统上是8字节），对于存储小数据量的场景这算浪费。而且链表不支持随机访问，你想拿到第5个元素，必须从头结点开始一个个走过去，时间复杂度O(n)。数组用下标访问是O(1)，这一点链表永远比不了。所以链表适用的场景是：数据量不确定、频繁插入删除、对随机访问要求不高。搞清楚了“为什么”，后面写代码的时候你心里才有底。
2. 单链表的核心结构：节点定义与内存布局
2.1 节点定义的两种写法：结构体自引用
链表的基础单元是节点。在C语言里，节点的定义涉及一个比较特殊的知识点：结构体自引用。也就是结构体内部的成员指向同类型的结构体。标准写法是：
typedef struct Node { int data; // 数据域，这里以int为例 struct Node *next; // 指针域，指向下一个节点 } Node;这里有一件值得说道的事：为什么next的类型必须写成struct Node *，而不能直接写Node *？因为typedef是在结构体定义完成之后才生效的，在结构体内部，编译器还不知道“Node”这个别名是什么，所以必须用完整的struct Node来声明指针。这是很多初学者第一次编译报错的原因——把struct Node *next写成了Node *next，然后编译器提示“未知的类型名Node”。
还有一种做法是给结构体加个名字，再单独typedef：
typedef struct _Node { int data; struct _Node *next; } Node;这种写法的好处是内部、外部统一用struct _Node表示结构体类型，逻辑上更清晰。不过现在的主流风格是第一种，代码更简洁。我个人的习惯是，讲课时会用第二种，因为能说清楚自引用是怎么回事；写项目时用第一种，代码短。
2.2 创建节点的正确姿势：malloc与防御性检查
创建节点是链表操作里最频繁的动作，所以一般会封装成一个函数：
Node* createNode(int data) { Node *newNode = (Node*)malloc(sizeof(Node)); if (newNode == NULL) { printf("内存分配失败\n"); exit(1); } newNode->data = data; newNode->next = NULL; return newNode; }这里有两个关键点必须养成习惯。第一，malloc之后一定要检查返回值。很多人觉得malloc失败是小概率事件，但不检查的话，一旦分配失败，你后面接着操作newNode->data，就是在操作空指针，程序直接段错误。第二，新节点的next一定要初始化为NULL。这既是好习惯，也是很多边界算法能正确工作的前提。比如很多链表题目的解法依赖于“链表的尾节点的next是NULL”这个事实，如果你创建节点时忘了初始化，尾节点指向一个随机地址，遍历的时候就会野指针崩溃。
从内存布局的角度看，每个节点在堆上的结构是：[数据域 | 指针域]。数据域和指针域的排列顺序取决于定义顺序，不过访问时编译器会自动处理偏移量，你无需关心。真正需要关心的是：节点变量本身是栈上的指针，指向堆上的结构体；堆上的内存不会自动释放，必须手动free。如果忘了free，时间长了就是内存泄漏；如果free了还在用，就是悬空指针。这两个问题，下面专门有一节讲。
3. 链表的基本操作：创建、遍历、插入、删除的完整实现
3.1 头插法与尾插法：两种建链思路及差异
创建链表有两种常用方式：头插法和尾插法。头插法是在头结点后面插入新节点，新节点每次都成为第一个节点，因此最后链表的顺序和输入顺序相反；尾插法是遍历到链表末尾再加节点，保持输入顺序。先看头插法：
Node* createListByHeadInsert(int arr[], int n) { Node *head = NULL; for (int i = 0; i < n; i++) { Node *newNode = createNode(arr[i]); newNode->next = head; // 新节点指向原来的第一个节点 head = newNode; // 更新头结点 } return head; }头插法的代码非常短，时间复杂度O(1)，因为不需要遍历找尾节点。它的一个典型应用是逆序：如果你有一个链表，想原地逆序，最方便的方法就是遍历原链表，用头插法把它们重新链到一个新链表上。
尾插法需要一个辅助指针tail来记录当前的最后一个节点：
Node* createListByTailInsert(int arr[], int n) { Node *head = NULL; Node *tail = NULL; for (int i = 0; i < n; i++) { Node *newNode = createNode(arr[i]); if (head == NULL) { head = newNode; tail = newNode; } else { tail->next = newNode; tail = newNode; } } return head; }尾插法的关键思路是用tail跟踪尾部，避免每次插入都要从头遍历到尾，这样插入操作的均摊时间复杂度就是O(1)。很多人会问：那为什么还要设计遍历到尾部再插入的“朴素尾插”？我明确说，那种写法在工程上是反模式——每插入一个节点要O(n)时间，创建n个节点就是O(n²)，数据量一大就完蛋。
3.2 遍历打印与链表长度：边界同样不能马虎
遍历是最基础的操作，代码很简单：
void printList(Node *head) { Node *cur = head; while (cur != NULL) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULL\n"); }注意，遍历时千万不要动head本身。很多人图省事，直接while (head) { ... head = head->next; }，打印完头节点就丢了，链表也找不到了。虽然可以通过在函数外重新赋值恢复，但这是一个非常危险的坏习惯，一旦在函数里修改了头结点又没有传回给调用方，整个链表就泄漏了。正确的做法是用一个临时指针cur去遍历，head永远保持在原位。
求链表长度和遍历很像，就是加个计数器。但在实际考试和面试里，这里往往有一个进阶考点：如何判断一个链表是否有环？如果只是求长度，不需要快慢指针；但如果有环，普通遍历会死循环。判断有环的方法是经典快慢指针：慢指针一次走一步，快指针一次走两步，如果有环两者必然相遇。这个方法在C语言面试里出现频率极高，建议顺手掌握。
3.3 删除节点：被删节点的释放与前后节点的重新链接
删除分三种情况：删除头结点、删除中间节点、删除尾节点。头结点特殊是因为head指针本身要更新；尾节点特殊是因为它的前驱节点的next要置NULL。删除中间节点的核心是：找到待删除节点的前驱节点prev，然后把prev->next指向待删节点的next，最后free掉待删节点。
完整代码框架如下：
void deleteNode(Node **head, int target) { if (*head == NULL) return; Node *cur = *head; Node *prev = NULL; // 找到目标节点 while (cur != NULL && cur->data != target) { prev = cur; cur = cur->next; } if (cur == NULL) return; // 没找到 if (prev == NULL) { // 删除的是头结点 *head = cur->next; } else { prev->next = cur->next; } free(cur); }这个代码用了二级指针Node **head，目的是在删除头结点时能直接修改调用方的head变量。这里必须解释一下为什么：如果参数只传Node *head，你在函数里修改*head = cur->next，修改的是head这个副本，调用方那边的head指针根本不会变，删除头结点后调用方手里的head还是一个悬空指针。只有传二级指针，才能修改调用方head本身的内容。这是C语言里非常核心的一个设计点，也是指针学得扎不扎实的分水岭。
3.4 插入节点：指定位置前插和后插的通用写法
指定位置的后插比较简单：找到目标节点p后，新节点newNode->next = p->next; p->next = newNode。但前插就要小心了，因为单链表只有next指针，没有prev指针，没办法直接从p往前找前驱。所以前插一般有两种思路：一是遍历找到前驱节点再插入，时间复杂度O(n)；二是不找前驱，采用“偷梁换柱”的方法，把新数据拷贝到p的下一个位置，再把旧数据留在p里。第二种方法的代码是：
// 在节点p之前插入值为data的新节点 void insertBefore(Node *p, int data) { Node *newNode = createNode(p->data); newNode->next = p->next; p->next = newNode; p->data = data; }这个技巧的核心逻辑是：新节点复制了p的旧数据，然后把p的数据改成新数据。从外部看，就相当于在p前面插入了新数据，而且时间复杂度做到了O(1)。这个方法在很多算法题里都会用到，比如在不知道前驱的情况下删除某个给定节点，同样可以用这种拷贝覆写的方式绕过去。理解了这种“逻辑插入”和“物理插入”的区别，你对链表操作的理解会上一个台阶。
4. 常见错误排查：野指针、断链、内存泄漏的定位思路
4.1 段错误（Segmentation Fault）的第一反应
新手写链表代码报段错误，95%以上的原因是野指针——访问了不该访问的内存。最典型的场景是遍历循环里判断条件写错了。比如：
while (cur->next != NULL) { cur = cur->next; }这个写法在访问cur->data时没问题，因为cur始终不是NULL。但如果写成：
while (cur != NULL) { printf("%d\n", cur->next->data); cur = cur->next; }当cur指向尾节点时，cur->next是NULL，你再去访问NULL->data，直接段错误。所以排查段错误的第一件事，就是检查所有指针解引用之前有没有判空。这个习惯比任何调试工具都重要。
另一种常见情况是链表本身就是坏的，比如创建节点时next没有初始化成NULL，尾节点的next是随机值，遍历时迟早踩到非法地址。这种问题用gdb可以看到“访问了0x地址”之类的情况，但根本原因还是初始化没做好。所以，建议所有新节点的next都显式置NULL，不要依赖malloc的随机初始状态。
4.2 删除节点后的悬空指针：free之后必须置NULL吗
先说结论：free之后，指针变量本身的值不会被改变，它还是指向那块已经释放的内存。这时候如果你再通过这个指针访问数据，是未定义行为——不一定会马上崩溃，但可能在其他地方篡改了数据，造成难以察觉的bug。
一个安全的做法是，free之后立即把指针置为NULL：
free(cur); cur = NULL;这样如果后面代码不小心又用到cur->data，会立刻段错误，你马上就能发现问题。如果没置NULL，错误会被推迟到未来的某个时刻，排查起来极其头疼。这个“fail fast”的原则，在代码质量非常关键的场景里尤其适用。
还有一个更隐蔽的悬空指针场景：释放了某个节点，但还有别的指针指向它。比如a->next指向b，你释放了b，但a->next还存着旧地址，后面a->next->data就变成非法访问。所以删除操作的正确顺序永远是：先改链，再释放。先修改前驱节点的next指向，让链表不再指向待删节点，然后才能free。改链和释放的顺序颠倒，是链表内存问题的集中爆发点。
4.3 在函数中修改链表却“没有效果”：二级指针的缺失
这个问题在上面的删除代码里已经提过，但值得单独强调，因为它是C语言链表初学者最容易困惑的bug之一。比如很多人写插入函数：
void insertAtHead(Node *head, int data) { Node *newNode = createNode(data); newNode->next = head; head = newNode; // 问题：修改的是局部变量 }然后main里调用：
Node *list = NULL; insertAtHead(list, 1); printList(list); // 打印出来还是NULL原因前面说了：head是按值传递的，函数内部修改head不影响调用方的list。正确做法是用二级指针：
void insertAtHead(Node **head, int data) { Node *newNode = createNode(data); newNode->next = *head; *head = newNode; }调用时写成insertAtHead(&list, 1);。这个细节，笔试、机试、面试都可能考到。它的本质是“如果你想通过函数修改一个指针变量本身的值，就得传这个指针变量的地址”，也就是二级指针。理解了这一点，很多“为什么我的链表操作没生效”的问题就能瞬间想通。
4.4 内存泄漏：free的对称性与Valgrind的使用
内存泄漏不像段错误那样直接崩溃，它是慢性杀手。程序跑一天，内存占用逐渐上升，最终被系统杀掉。在链表操作中，最常见的泄漏就是删除一个节点时只改了链，没free。比如：
prev->next = cur->next; // 链改好了 // 忘了 free(cur);cur指向的堆内存就再也找不回来了。还有一种情况是链表整个销毁时，很多人只free了head，后面的节点全部泄漏。正确的销毁链表函数要遍历并逐个释放：
void destroyList(Node *head) { Node *cur = head; while (cur != NULL) { Node *next = cur->next; free(cur); cur = next; } }注意：一定要先保存next再free，因为free之后cur的内容理论上就不该再访问了，虽然很多情况下还能读到，但这是未定义行为。用next提前保存下一步要走的节点，既安全又清晰。
如果你想验证自己的代码有没有泄漏，在Linux下强烈建议用Valgrind：
gcc -g -o test test.c valgrind --leak-check=full ./test如果输出里有“definitely lost”之类的信息，说明某块堆内存泄漏了。配合-g生成的调试信息，还能定位到具体是哪一行malloc的。我见过很多学生写完链表作业，在OJ上怎么都过不了“内存占用异常”的测试点，用Valgrind一查，基本都是销毁函数写得不对。所以这个工具越早学会越省钱。
5. 进阶实战：带头结点与不带头结点的差异，以及链表的排序、逆序、合并问题
5.1 带头结点vs不带头结点：一道经典选择题
链表有两种组织方式：一种是什么都不存，只有一个next指针的“哑结点”（dummy node），也叫头结点；另一种是第一个节点直接就存数据，也就是不带头结点。很多教材两种都会讲，但实际工程和考试里，选择哪种要看场景。
带头结点的最大优势是：插入和删除第一个数据节点时，不需要修改头指针本身。因为头结点永远是那个哑结点，数据节点的前后操作逻辑完全统一，代码更简洁。比如空链表时，head指向的头结点始终存在，你不需要特殊处理“空表插入”和“非空表插入”两个分支。不带头结点的优势是结构上“没有多余节点”，内存省一个指针大小的空间，遍历打印时不需要跳过哑结点。
对于初学者，我强烈建议先练熟带头结点的写法，因为它的边界处理更规整，不容易出bug。等彻底理解了指针操作，再对照着看“不带头结点”版本，会发现两者的差异其实就是在头指针的更新策略上。考试如果指定“不带头结点”，你只需要在插入删除函数里多判断一个“当前操作的是不是头结点”分支即可。
5.2 链表逆序：迭代法与递归法的思维对比
链表逆序是一个非常经典的考点，也是理解指针操作的试金石。迭代法用三个指针pre、cur、next配合，逐个修改节点的next方向：
Node* reverseList(Node *head) { Node *prev = NULL; Node *cur = head; while (cur != NULL) { Node *next = cur->next; // 先保存后继，因为马上要改cur->next cur->next = prev; // 掉头 prev = cur; // prev前进 cur = next; // cur前进 } return prev; // 最后prev就是新头结点 }这个代码建议自己手动模拟一遍。任何链表操作的死记硬背都不可靠，但如果你在纸上用自己的手画一遍指针的“掉头”过程，你会发现很多问题自动清晰了。比如为什么要先保存next？因为cur->next一旦被改成prev，原来的后继就找不到了，不先保存就断了链。
递归法本质上是一个“先走到底，再回头改指针”的过程，代码更短但更烧脑：
Node* reverseListRecursive(Node *head) { if (head == NULL || head->next == NULL) return head; Node *newHead = reverseListRecursive(head->next); head->next->next = head; head->next = NULL; return newHead; }理解递归法的要求是先信任递归：假设reverseListRecursive(head->next)已经能把从head->next开始的子链表逆序，并且返回这个子链表的新头。那么此时head还是指向原来的第二个节点（现在是新子链表的尾），而head->next->next就是那个子链表尾部的next指针，把它指向head，就相当于把head接到了新链表的末尾。最后head->next置NULL，因为它现在是新链表的尾节点。馈入思维是理解这段代码的关键，“假设函数已经正确”是递归的核心。
5.3 链表排序：为什么说用数组排序再还原也很常见
链表的排序也是高频题。最直接的思路是像数组那样用冒泡排序，但要交换节点数据而不是交换节点指针，因为交换指针很容易出错。用数据交换的冒泡如下：
void bubbleSortList(Node *head) { if (head == NULL) return; int swapped; Node *cur; Node *tail = NULL; do { swapped = 0; cur = head; while (cur->next != tail) { if (cur->data > cur->next->data) { int tmp = cur->data; cur->data = cur->next->data; cur->next->data = tmp; swapped = 1; } cur = cur->next; } tail = cur; } while (swapped); }这个写法沿用了数组冒泡的“每轮确定一个最大值放末尾”思路，只是用tail来标识每一轮已排序部分的边界。链表不方便用“n-1-i次”来循环，因为求长度需要额外遍历，所以用“是否有交换”作为循环条件更自然。
多说一句，如果数据量大且排序频繁，往往会把链表转成数组，用快排或qsort排序，再重新构建链表。这不是投机取巧，而是工程上非常常见的优化策略。因为链表本身就不擅长随机访问，而快排内部要求大量随机访问，强行在链表上实现快排，性能反而不如先复制到数组再排序。这种“绕路”的思维，在工程中尤其值得学习：数据结构是工具，不是教条。
5.4 两个有序链表合并：递归解法的直观性
合并两个有序链表，用递归的写法直观得不像真的：
Node* mergeSortedLists(Node *a, Node *b) { if (a == NULL) return b; if (b == NULL) return a; if (a->data <= b->data) { a->next = mergeSortedLists(a->next, b); return a; } else { b->next = mergeSortedLists(a, b->next); return b; } }这里的关键是：每次比较两个链表的当前节点，取较小的那个作为结果链表的当前节点，然后递归处理剩余部分。递归终止条件是其中一个链表为空，这时直接返回另一个链表即可——因为剩下的节点本身就有序，直接拼接就行。
这个递归版本的时间复杂度是O(m+n)，每个节点最多被比较一次，空间复杂度看递归深度，最坏是O(m+n)（栈帧的叠加）。实际面试里，面试官也可能要求迭代版本，用哑结点可以省去判空的麻烦：
Node* mergeSortedListsIterative(Node *a, Node *b) { Node dummy; dummy.next = NULL; Node *tail = &dummy; while (a != NULL && b != NULL) { if (a->data <= b->data) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = (a != NULL) ? a : b; return dummy.next; }迭代版本里有一个小技巧值得注意：我在栈上声明了一个dummy节点，而不是堆上malloc。这样函数结束不需要操心释放dummy。哑结点只用于统一逻辑，不会出现在最终结果里，所以栈上临时变量就够了。这个小技巧在日常编码中使用频率非常高，可以说掌握了它，你的链表代码的边界分支能少一半。
6. 从实验到工程：单链表的使用心得与扩展思考
6.1 单链表vs双向链表vs循环链表：各自适合什么样的场景
学完单链表，很多人会好奇为什么不直接用双向链表或者循环链表。我的判断标准很简单：如果你的操作主要是单向顺序遍历和尾部插入，单链表就够用，省内存、代码逻辑简单；如果需要频繁从尾部往回走（比如撤销操作），那就是双向链表的主场——它的每个节点多一个prev指针，但给逆向遍历带来了O(1)能力；如果需要在尾部快速回到头部，比如循环队列的缓冲区管理，那就用循环链表，让尾节点的next重新指向头结点，形成了一个环。
其实这三者不是竞争关系，而是递归递进的关系。单链表是基础，你只要把单链表的指针操作真正练熟了，掌握双向和循环只是时间问题。每个扩展结构都是在单链表的基础上做加法，但核心的“插入改链”“删除改链”思路完全一样。学数据结构不要贪多，把一个结构彻底掌握，其他结构真的就是变体。
6.2 手写链表常见笔试题：环检测、找中间节点、倒数第K个
这几个题基本属于链表机试的“全家桶”，值得单列一节。
- 找中间节点：用快慢指针，慢指针走一步，快指针走两步，快指针到尾时，慢指针正好在中间。这个技巧本质是利用“速度差”给你一个可以同时判断长度和位置的O(n)方案。
- 找倒数第K个节点：也是双指针，先让快指针走K步，然后快慢指针同步走，快指针到尾时，慢指针就是倒数第K个。
- 环检测：快慢指针法，如果快指针和慢指针相遇，说明链表有环。更进一步，如果要找到环的入口节点，需要再用一个“从头和从相遇点同步走”的技巧，两者相遇的位置就是入口。这个进阶版的推导过程很长，网上资料很多，建议自己推导一遍而不是死记结论。
这几个题的共同点：都是快慢指针的变体。理解了“指针步长可以不同”“指针可以作为位置的偏移量”这两个思想，你不再需要背题，而是可以直接推导出解法。
6.3 内存效率的真实账本：什么时候链表反而不如数组
必须说一句公道话：链表并不是所有情况下都比数组好。如果数据量不大，且基本不插入删除，数组要好得多，原因有三。第一，数组是连续内存，缓存命中率高，链表节点散落堆上，每次访问都可能触发缓存未命中，性能差好几倍。第二，数组没有额外的指针开销，存储密度高。第三，数组可以O(1)随机访问，链表必须从头遍历。
所以在工程里，真正的做法往往是组合拳：用数组存储数据，用额外的索引表或者索引用实现逻辑上的顺序变化；只有在数据量大、插入删除频繁，或者你需要在元素间建立复杂关系（不只是线性序列）时，链表才派上用场。数据结构是工具，工具选型要看场景，不是哪个“高级”就用哪个。
6.4 关于链表销毁和程序退出时的一些小细节
最后分享两个我在实际项目里踩过的坑。第一个是：程序退出前，最好把链表完整销毁并置空。有人觉得操作系统会在进程退出时回收所有内存，不销毁也无所谓。确实系统会回收，但如果你这个链表操作是在一个长期运行的服务器进程里，每次请求创建一个链表而不销毁，那内存就会一直涨，最终OOM。写一个destroyList函数，本身就是一种防呆设计，养成习惯后，排查内存问题会轻松很多。
第二个坑和文件描述符相关：如果链表节点里存的有文件指针或者动态字符串，销毁节点时除了free节点本身，还要先释放节点内部引用的资源。比如节点里有char *name，且name是malloc来的，那释放节点前必须先free(name)再free(node)。顺序反了或者漏了一步，轻则内存泄漏，重则double free。这种“先释放内部资源，再释放容器节点”的原则，在所有含指针成员的结构体上都适用，不只是链表。
个人而言，我翻来覆去强调“为什么”，是因为发现所有链表写不好的人，问题几乎都出在“只会背步骤，不理解指针”。但凡你在纸上画一下节点和指针的关系，把每一步改链操作对应到图上，那些断链、野指针的问题根本不会发生。希望这篇文章能帮你把链表这块地基真正打牢，后面学树、图、哈希表的时候，你会感谢现在认真啃链表的自己。
