C语言——单链表

你在学数据结构，迟早绕不开单链表。这东西在学生时代看起来既抽象又枯燥，但放到实际项目里，却是最常被手动实现的基础结构之一——从任务队列、内存池的空闲块管理，到系统内核的进程列表，底层到处是单链表的身影。很多人觉得链表比数组“高级”，其实它只是换了一种组织内存的思维方式。如果你是刚开始接触数据结构、或者学过但总写不出完整代码的C语言学习者，这篇文章会从设计思路到核心操作，再到性能和调试的坑，带你完整走一遍“单链表从0到会写会调”的过程。

1. 单链表的整体设计与思路拆解

1.1 为什么是单链表：和数组的一次认真对比

先把感性认识建立起来。数组和单链表到底差在哪？一句话概括：数组用连续内存换访问速度，单链表用分散内存换插入删除的灵活性。

数组在内存里是一块连续空间，CPU缓存友好，按下标访问是O(1)，非常快。但问题也随之而来：如果你要在中间插入一个元素，得把后续所有元素往后挪；删除中间一个元素，得把后续所有元素往前补。更麻烦的是，数组长度在一开始基本就定死了，C语言里想扩容，通常只能重新malloc一块更大的空间再整体拷贝，代价是O(n)，而且旧空间处理不当很容易泄漏。

单链表不要求连续内存。每个节点可以零零散散分布在堆里，节点之间通过指针串起来。插入和删除操作，时间复杂度在理想情况下是O(1)，只需修改前后节点的指针，不需要移动元素。但代价是访问某个节点你需要从头"遍历"，平均O(n)，对CPU缓存也不友好。

所以单链表适合什么场景？元素数量动态变化大、插入删除频繁、随机访问需求少的场景。实际项目里最常见的比如实现缓存淘汰算法（LRU等）、任务调度队列、哈希表的链式冲突处理。它不是万能的，但在这些场景下，它比数组用起来顺手得多。

1.2 节点结构设计：链表的"积木"到底怎么搭

C语言单链表的核心是"节点"（Node）。每个节点有两个部分：数据域和指针域。

typedef struct Node { int data; /* 数据域：存实际数据，可以是任何类型 */ struct Node *next; /* 指针域：指向下一个节点 */ } Node;

有人会问，为什么指针类型写成struct Node *而不是Node *？因为这里用了typedef，但在定义结构体内部，Node这个别名还没完全建立，必须先用struct Node完整声明。这是C语言的一个经典细节，很多新手在这里编译报错后会很困惑。

数据域这里我简单用了int，实际开发里完全可以是客户信息结构体、网络包缓冲区、任务块等。甚至可以嵌套一个指针指向更复杂的数据结构，因为单链表节点本身只关心"下一个在哪"，数据放什么非常自由。

1.3 一个重要设计：头节点的取舍

单链表要不要单独搞一个头节点？这是新手经常纠结的问题。

所谓的"头节点"，是指在真正的第一个数据节点之前，多分配一个节点，它的data域可以闲置，或者用来记录链表长度等信息，关键点在于它的next指向真正的第一个数据节点。于是链表空和不空的时候，头指针始终指向同一个节点，插入删除操作代码不需要分情况讨论"如果链表为空该怎么办"。

我个人的建议：初学阶段一定用头节点，吃亏少。带了头节点，头插法、尾插法、指定位置插入的代码逻辑大幅统一，边界判断少很多。等写得非常熟练了，再去体会不带头节点的写法——那种写法可以省一个节点，但代价是每次插入删除都要额外判断头指针是否需要被修改，还有可能因为忘记回写头指针导致整个链表丢一半。

用头节点的链表，即使表里没有数据节点，也至少有一个头节点，那"链表是否为空"的判断条件是head->next == NULL，而不是head == NULL。这个细微区别，写代码时非常影响逻辑分支。

2. 单链表核心操作实现与实操要点

2.1 链表的创建与初始化：先把基础打牢

先定义一个头指针，指向头节点。头节点本身也需要分配内存。

Node *list = (Node *)malloc(sizeof(Node)); if (list == NULL) { exit(EXIT_FAILURE); /* 内存分配失败，必须处理 */ } list->next = NULL;

这里有一个非常严肃的习惯：malloc之后必须立刻判断是否为NULL。虽然平时训练时内存不够的概率极低，但实际项目在长时间运行、内存碎片化严重的情况下，malloc失败是真实存在的。不检查还继续向后操作，就是典型的"解引用空指针"故障。

创建好一个空链表之后，随手给相邻节点之间建立联系。严谨一点的做法是把每个节点的next都先置空，避免野指针。很多人之前写数组习惯了，初始化数组就是int a[10] = {0}，但链表每个节点是自己分配出来的，node.next如果不显式赋NULL，它的值就是不确定的垃圾值，后面一旦遍历就全场崩。

2.2 插入操作：头插法、尾插法与指定位置插入

2.2.1 头插法，最直接也最常用

头插法，就是每次把新节点接到头节点后面。它时间复杂度O(1)，但会让链表里元素的顺序刚好和插入顺序相反。

int insertAtHead(Node *list, int val) { Node *node = (Node *)malloc(sizeof(Node)); if (node == NULL) { return -1; /* 返回错误码让调用方处理 */ } node->data = val; node->next = list->next; list->next = node; return 0; }

注意，这里的关键是顺序：先让新节点的next指向原来的第一个节点，再把头节点的next指向新节点。如果反过来，先把list->next赋给新节点，那原来的第一个节点指针就丢了，整个链表链路会断掉。

2.2.2 尾插法：保持顺序但需要遍历

尾插法的逻辑非常简单：先找到最后一个节点，再在它后面接上新节点。

int insertAtTail(Node *list, int val) { Node *p = list; while (p->next != NULL) { p = p->next; } Node *node = (Node *)malloc(sizeof(Node)); if (node == NULL) { return -1; } node->data = val; node->next = NULL; p->next = node; return 0; }

这里有个细节值得注意：我的p初始化为list，也就是从头节点开始。这样即使链表是空的，p指向头节点，也可以直接在头节点后面插入。如果p初始化为list->next而且链表为空，p就是NULL，p->next直接段错误。

尾插法的时间复杂度是O(n)，因为必须走到末尾。频繁尾插的场景，如果性能敏感，通常做法是额外维护一个尾指针tail，专门指向最后一个节点，这样尾插就变成O(1)。但维护tail也有成本：头插、中间删除时，如果删掉的是尾节点，得重新找新的尾节点。这个取舍要结合实际情况。

2.2.3 指定位置插入：这个非常容易出错

指定位置插入，一般约定下标从0开始，插入到第i个位置意味着原来第i个节点及之后所有节点都被往后推一格。

int insertAtIndex(Node *list, int idx, int val) { if (idx < 0) { return -1; /* 下标题无效 */ } Node *p = list; for (int i = 0; i < idx; i++) { if (p->next == NULL) { return -1; /* 位置超出链表长度 */ } p = p->next; } Node *node = (Node *)malloc(sizeof(Node)); if (node == NULL) { return -1; } node->data = val; node->next = p->next; p->next = node; return 0; }

为什么这里p要走到第idx个节点的前一个？因为单链表是"单向"的，你手里有一个节点的指针，就能操作它后面的节点，但你无法从后面一个节点拿回到前一个节点。所以插入到下标idx，实际要找到下标为idx-1的节点，然后让它的next指向新节点。这就叫"前驱定位"。

写到这里我要不厌其烦地强调一个编码细节：在插入操作里，先完成新节点的接线动作，再动原链表指针。你宁可多写一个临时变量，也不要让任何一个链表节点在操作过程中"失联"。失联的节点，在内存泄漏检测工具里就是一个"孤儿块"，因为没有任何指针指向它，但它之前malloc的内存永远无法释放。

2.3 删除操作：从头到指定位置

删除节点比插入更考验对指针的理解，因为你需要"记住前驱"。单链表只能往前走，想删除当前节点p，必须拿到p的前一个节点pre，然后让pre->next直接跨过p指向p->next。

int deleteAtIndex(Node *list, int idx, int *outVal) { if (idx < 0 || list->next == NULL) { return -1; } Node *pre = list; for (int i = 0; i < idx; i++) { if (pre->next == NULL) { return -1; /* 越界 */ } pre = pre->next; } Node *del = pre->next; if (del == NULL) { return -1; /* 要删除的节点不存在 */ } pre->next = del->next; if (outVal != NULL) { *outVal = del->data; } free(del); return 0; }

删除操作最容易犯的两个错误，一个是free之后没有把指针置空，另一个是free的顺序搞错。这里先让pre->next跨过del，再free(del)，顺序不能倒。如果你先free(del)，pre->next还指向一块已释放的内存，这就是经典的悬空指针（dangling pointer）。它比野指针更隐蔽，因为野指针是未初始化，悬空指针是曾经有效但已经释放。

还有个容易被忽略的：删除时把节点的data通过outVal带出去再释放，这是一种比较稳的API设计思路。调用方可能想知道被删除的值，也可能需要用它去做一些后续清理。如果把删除函数设计成静默丢弃数据，那以后再想扩展回收逻辑就要改接口。

2.4 查找与遍历：和数组下标思维区别一下

链表查找，本质上就是从头节点开始，一个个顺着next往下摸。

Node *findByValue(Node *list, int val) { Node *p = list->next; while (p != NULL) { if (p->data == val) { return p; /* 返回节点指针 */ } p = p->next; } return NULL; }

这里有一个我自己踩过很多次的坑：循环用while (p != NULL)而不是靠计数。很多人在学链表之前写习惯了for (i = 0; i < n; i++)，到了链表里就总想着用长度控制循环。但单链表本身不记录长度（除非你专门加一个字段），靠NULL判断是最自然的。当然你也可以维护一个len字段，但新增删除操作时必须同步更新len，成本也不小。

遍历出来只是找到节点，但如果业务逻辑是"要删除这个找到的节点"，这么直接返回节点指针还不够——你缺前驱指针。很多初学者拿到一个节点的指针就free掉它，然后整个链表就断了。正确做法是设计一个findPrev函数，或者直接写一个"查找并删除"的复合函数。为了这个需求，我在实际项目里经常让删除函数自己内部遍历找前驱，而不是暴露节点指针给外部。

3. 进阶操作：反转、排序与合并，最考验功底

3.1 单链表反转：指针操作的巅峰练习

反转单链表，堪称单链表最经典的面试题和基本功。思路不复杂：遍历过程中，把每个节点的next指向前一个节点。但有个致命的坑——你把当前节点的next改了，后面的节点就丢了，所以需要用一个临时指针先把后面的节点保存下来。

void reverse(Node *list) { if (list->next == NULL) { return; /* 空链表不用反转 */ } Node *prev = NULL; /* 前一个节点，初始为空 */ Node *cur = list->next; /* 当前节点，从第一个数据节点开始 */ while (cur != NULL) { Node *nextNode = cur->next; /* 先保存后继 */ cur->next = prev; /* 反转指针 */ prev = cur; cur = nextNode; } list->next = prev; /* 头节点指向新的首节点 */ }

如果你发现自己反转完之后链表断了，十有八九是nextNode = cur->next这行代码的位置写错了，等cur已经指到后面才发现原next信息找不到了。这个错误的典型表现是死循环，因为cur一直在原地，next信息被覆盖成prev，导致链表成环。

反转是检验你指针理解的试金石。很多同学能ac一条一条的题目，但到反转这里总是反转完接不回头节点，或者反转后第一个节点的next没有置空，导致链表尾部不是NULL而变成一个无意义的旧地址。我在代码里先把head->next保存为cur，然后一边迭代一边改方向，最后才把head->next挂回去，这个顺序比较稳。

3.2 有序链表的合并

合并两个O(1)空间的有序单链表，核心就是双指针比较。这里我站在一个更工程化的角度：合并的时候不要搞一堆临时数组再排序，空间的浪费在小数据量上无所谓，但大的数据块会影响性能。

Node *mergeSortedLists(Node *l1, Node *l2) { Node dummy; /* 栈上头节点，省去malloc */ Node *tail = &dummy; dummy.next = NULL; Node *p = l1->next; Node *q = l2->next; while (p != NULL && q != NULL) { if (p->data <= q->data) { tail->next = p; p = p->next; } else { tail->next = q; q = q->next; } tail = tail->next; } tail->next = (p != NULL) ? p : q; return dummy.next; }

这个写法我很喜欢，因为它在栈上用了一个虚拟节点dummy，这样tail初始化不为NULL，下面的循环不需要额外判空。等合并完了，返回dummy.next就是合并后的第一个节点。注意这时候dummy本身在栈上，不需要free，但我们的函数不能直接返回dummy的地址，因为栈地址在返回后无效。返回dummy.next是安全的。

合并的思路延伸一下，归并排序的"分"和"治"环节，也就是这种双指针合并的反复使用。所以链表归并排序的核心代码量其实不大，关键是找中点，这需要快慢指针。

3.3 快慢指针：找中点与环检测

快慢指针，一个每次走1步，一个每次走2步。从链表头同时出发，快指针走到末尾时，慢指针刚好走到中间节点。这个技巧找中间点特别方便，比先数长度再走一半好用。

Node *findMiddle(Node *list) { Node *slow = list->next; Node *fast = list->next; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

注意循环结束条件，一定要同时判断fast != NULL和fast->next != NULL，否则快指针自己就会先踩到NULL然后崩溃。这种"步子大容易扯着蛋"的代码，最容易出的就是空指针问题。

环检测的核心也是快慢指针。如果链表存在环，快指针和慢指针最终会相遇。如果无环，快指针会先走到NULL。实现环检测时特别注意：每走一步都要检查fast和fast->next是否为NULL，两个条件缺一不可。

4. 内存管理与常见问题排查：这块才是工程上最有价值的

4.1 内存泄漏：链表写崩的第一大元凶

写链表最反直觉的点是，链表对象存在于堆上，每malloc一次都要找机会free一次。只要你有一个节点被“丢”了，那个节点以及它后面的所有节点，会变成一个谁都没指针引用的内存孤岛。这个过程不是说程序立刻崩，而是accumulated泄漏，等到程序跑上几天几周，内存越吃越大，然后被系统杀掉。

写了一个删除函数，是让pre->next跨过del，但是忘了free(del)，这种节点直接泄漏。写了第2.2节头插法的过程中经常出现：

node->next = list->next; list->next = node;

如果你顺序搞反，把第2行的list->next先覆盖，那么原来的第一个节点被“丢”，整个链表直接断掉。这种断链的问题靠编译器查不出来，也往往不会立刻崩，等到你遍历链表遍历到一个没有指向的地方，程序才突然异常。最有效的排查办法是在写完插入、删除后，写一个遍历函数把链表完整打印一遍，用眼睛清查节点数量是否匹配预期。

提示：最好写一个destroyList函数来释放整条链表。标准做法是保存一个next指针，再free当前节点，然后继续。绝不能在free之前不去保存下一个节点，那样你就连链都断了。

void destroyList(Node *list) { Node *p = list; while (p != NULL) { Node *nextNode = p->next; free(p); p = nextNode; } }

链表的清理是"先保存下一个再释放当前"，这个顺序和删除节点的逻辑正好是一个反向操作。

4.2 悬空指针与野指针：两个让人头痛的东西

野指针是说指针本身没有初始化，指向了一块随机内存，你访问它纯属"开盲盒"。悬空指针是说指针曾经指向一个有效的内存块，但有别人把它free掉了，你手里的指针还残留着原来的地址值。访问悬空指针比野指针更难发现，因为它的地址看起来"好像正常"。

我建议写链表时养成两个习惯：

一个习惯是"谁分配、谁释放、谁置空"。malloc的代码块最后在free之后，立刻写ptr = NULL。虽然很多时候局部指针马上失效，但这个习惯能防止所有通过该指针再次访问的隐患。

另一个习惯是不要在多个函数之间来回传递裸指针而无任何约定。如果某个函数负责删除节点并free，就一定不要让另一个函数继续持有这个节点的指针。实际项目里为了降低这种偶然错误，就是把节点封装在不透明的句柄里，外部根本不直接持有节点指针。

4.3 边界条件：我们的敌人是"空的输入"

不管写什么链表算法，条件判断永远要多想一层：如果链表是空的怎么办？如果只有一个节点怎么办？如果我删的是第一个节点怎么办？如果我要插入到末尾怎么办？

我写链表代码的经验是：先把最少节点的那条路径理清楚，再去写正常路径的逻辑。比如写插入函数，先把list->next == NULL的情况想好，不然正常人满脑子都在想"插到中间怎么整"，写到一半才发现链表是空的。

调试链表代码时我最常用的技巧是“短的输入样例打出来”。不要一上来就构造5个节点的列表，先用空链表，再用单节点链表，再两个节点、三个节点，逐个验证。这个习惯看着笨，但是真能快速锁定bug在哪一层逻辑。

5. 实用小技巧：让单链表代码更稳健

5.1 防御性编程：接口也别忘了校验

C语言没有异常机制，错误处理全靠返回值。所以链表函数的接口设计，最好像我上面示例那样：插入删除返回int，0表示成功，-1表示参数非法或内存不足。这样调用方只需要检查返回值就可以做相应的容错处理，比写一堆日志再退出更可控。

这里有一个容易被忽略的：很多链表函数里都有一个参数用来"带回"数据，比如删除函数里的int *outVal。这个指针也要检查非空再解引用，否则你把NULL传给一个不检查的函数，它内部直接*outVal = del->data就段错误了。C程序员对空指针要有职业级别的敏感。

5.2 打印遍历函数，调试利器

写一个直观的printList函数，把data一个个打出来：

void printList(Node *list) { Node *p = list->next; int count = 0; while (p != NULL) { printf("%d", p->data); if (p->next != NULL) { printf(" -> "); } p = p->next; count++; } printf(" (length = %d)\n", count); }

这个函数的价值在链表训练阶段怎么强调都不过分：每次插入、删除、反转后都调用一次，链路状态一目了然。看到->符号链不住的情况，基本就能确定断链发生在哪个操作函数里。甚至可以给节点加一个辅助的打印字段，把地址也打出来，判断是否有两个节点持有了同一个地址。

5.3 适度封装：从面向过程走向面向对象思维

虽然C语言不支持class，但可以用设计模式的方式来组织链表。我平时写的比较舒适的结构是：

typedef struct LinkedList { Node *head; size_t length; } LinkedList;

再把插入、删除、查找都接受LinkedList *作为第一个参数。这样虽然实现还是C，但调用层的语义更清晰，也可以天然记录链表长度。唯一需要注意的是，length字段的维护是插入加一、删除减一，只要有一处更新遗漏，你就会看到"length明明显示5但遍历只有4个节点"的灵异事件。所以我建议还是先不搞这个字段，等基础操作熟练了再去维护它。

6. 写链表常见问题速查：直接把棘手场景列出来

这些表里的问题，几乎每个从数组思维转链表思维的人都会遇到一遍。数组里你直接操作下标，链表里所有操作都只能围绕指针展开，而指针一旦发展成复杂组合，出错概率呈现指数上升。

7. 最后的实操测试：给自己设计一个完整的场景

数据结构只学不练等于白学。我建议用下面这个场景当自测题，来检验你对单链表是否真的掌握：

做一个学生成绩管理系统，要求：

• 用单链表存储学生记录，每条记录包含学号和成绩
• 支持边录入边按学号升序插入
• 支持按学号查找
• 支持按学号删除
• 支持打印全部成绩并统计平均分

这个场景和时间复杂度最差的学生名单管理正好匹配，也涵盖了我们前面讲的所有核心操作。按学号升序插入，其实就是指定位置插入的变体：先找到第一个学号大于当前学生的节点，把它当作插入位置。删除按学号，就是查找加删除的组合。

我给出的具体操作顺序是：

1. 定义学生结构体，把data域替换成这个结构体，如struct Student { int id; char name[32]; float score; };，节点结构体直接嵌套。
2. 先写好"按学号查找前驱节点"的函数，这个函数几乎可以复用到插入、删除两个功能中。
3. 实现按键插入，注意当学号比现有最大值还大时，应该走尾插逻辑。
4. 实现删除，复用前驱查找。
5. 遍历打印，并顺便统计平均分。

写的过程中如果哪个环节卡住了，回头翻翻前面几节对应的代码，把思路理顺，再自己动手敲一遍。单链表这种东西，读一百遍不如自己完整写三遍，写到第二遍你会慢慢找到一种"指针在我掌控之中"的手感，写到第三遍你基本就能脱离参考代码独立实现了。

8. 个人实操中的一点体会

单链表是C语言里少有的"代码量不大但思维要求不低"的内容。我自己带过不少学弟学妹，发现真正能把单链表写明白的，通常不是记忆力最强的人，而是debug过程中愿意把完整链表打出来多看几轮的人。链表的每一次断链、每一次段错误，都在倒逼你理解数据结构最核心的东西——内存布局和指针关系。

如果让我给一个具体建议，那就是别把单链表当“C语言课的一道作业题”。把它当成你真正要在项目里使用的基础工具，用工程标准去要求自己：每一个函数都要考虑参数合法性，每一次malloc都要思考释放路径，每一条路径都要用空链表和最小用例验证。这样写过一遍，你的指针功底和数据结构的理解都会明显上了一个台阶。之后再接触双链表、二叉树、哈希表，你会发现很多困难其实只是单链表里指针思维的延伸，并没有那么神秘。