单链表这东西，我在项目里用过无数次，也帮人排查过无数次问题。每次讲到它，我都觉得这玩意儿是C语言指针和内存管理最浓缩的试炼场——你搞懂它，后面学树、学图、学操作系统里的各种链表结构，都会顺很多；搞不懂它，写再多业务代码，心里也总悬着一块。

我不打算给你堆砌教材式的定义。单链表，本质就是“一串串在一起的数据节点”。每个节点除了存自己的数据，还要存一个指向下一个节点的指针，就像寻宝游戏里每张纸条上写着下一张纸条藏在哪里。这套设计极其简单，却支撑起了栈、队列、哈希表分离链、内核的任务队列这些数不清的上层结构。

这篇文章我会直接从考试和工程项目里最常遇到的几个角度往下拆：节点怎么设计、内存怎么分配、增删查操作为什么这么写、头插法和尾插法选哪个、以及双链表和单链表在实际里怎么取舍。我尽量说人话，关键代码给全，坑点直接标出来。学完这一篇，你遇到“反转单链表”“合并两个有序链表”这类题，至少心里有张地图。

1. 单链表的设计思路与结构拆解

1.1 为什么会有单链表这种结构

数组在内存里是连续一片空间，查找很快，按下标就能直接定位。但数组有两个绕不开的痛：第一，插入和删除得挪动大量元素，除非你从尾部操作；第二，长度是固定的，扩容要么靠realloc，要么干脆换新数组，代价不小。

单链表就是冲这两个痛点去的。它不要求在内存里连续存放，每个节点散落各处，通过指针串起来。这样插入和删除只需要改指针指向，不需要挪数据；长度也不需要预知，需要新节点就动态申请，用完了释放，内存按需分配。

代价就是牺牲了随机访问能力。你想找第k个节点，必须从头一个节点一个节点走。这正好引出了工程里经常说的“链表和数组各有各的适用场景”：频繁按位置查找、对缓存友好，数组占优；频繁插入删除、长度动态变化大，链表占优。

1.2 节点的存储结构：数据域加指针域

经典单链表节点定义长这样：

typedef struct Node { int data; // 数据域，存储用户数据 struct Node *next; // 指针域，指向下一个同类型节点 } Node;

这里的struct Node *next很多新手第一次看会懵：结构体里面怎么还能有指向自己类型的指针？这其实没问题，next是一个指针，不是结构体本身的完整拷贝。指针在任何平台上都占固定大小（32位下4字节，64位下8字节），所以Node这个结构体的大小是sizeof(int) + sizeof(指针)。这并不构成递归定义，因为指针的大小是确定的。

考试里有个高频概念：节点类型Node和指向节点的指针类型Node*是两个东西。你可以写Node *head = NULL;表示空链表，也可以写Node *p = (Node*)malloc(sizeof(Node));申请新节点。后面所有操作，本质都是维护这个head和经过next串起来的一连串指针。

我一般在定义结构体时就把Node和Node*都用typedef给出来：

typedef struct Node { int data; struct Node *next; } Node, *NodePtr;

这样代码里少写几个struct关键字，在工程中可读性好一点。但要注意，如果你习惯混用Node和NodePtr，千万别以为一个NodePtr就是数组，它就是个指针。

1.3 头结点、头指针和首元节点的区别

这个问题是我接触到的初学者栽跟头最多的地方，也是很多学校期末考填空题的常客。

• 头指针：指向链表第一个节点的指针变量。链表存在的前提就是有头指针，哪怕链表为空，头指针也不能是野指针，一般是NULL。
• 首元节点：存储第一个实际数据的节点。
• 头结点：人为在首元节点之前加的一个节点。它的data可以不用，或者用来存链表长度等信息，next指向首元节点。

头结点不是必须的，但加了一个头结点之后，链表的很多操作会统一不少。比如带头结点时，在第一个位置插入新节点和在其他位置插入，代码逻辑就能一致，因为头结点充当了统一的前驱角色。删除也一样，有头结点的话，删除首元节点就不需要单独改head指针。

我在小项目里经常带头结点，在算法题里通常不带头结点——因为大多数OJ题给的链表本身就是不带头结点的，你得学会同时适应两种写法。

// 带头结点初始化 Node *initList() { Node *head = (Node*)malloc(sizeof(Node)); if (!head) { printf("内存分配失败\n"); return NULL; } head->next = NULL; return head; }

// 不带头结点，直接让头指针为NULL Node *head = NULL;

不要觉得这是小事。我维护过某段上千行的链表代码，里面混用了带头和不带头两种节点，每次删除操作都要先判断head当前是不是首元，又判断是不是空表，逻辑复杂度直接翻倍。所以动手前先想清楚到底用哪种，统一风格。

2. 核心操作与实现细节

2.1 动态内存分配的正确姿势

单链表几乎所有节点都来自malloc，用完再free。这里有一条铁律：malloc多少次，free就必须多少次；而且free完的指针要置NULL，避免出现悬空指针。

申请节点的标准动作：

Node *createNode(int val) { Node *newNode = (Node*)malloc(sizeof(Node)); if (newNode == NULL) { fprintf(stderr, "内存分配失败\n"); return NULL; } newNode->data = val; newNode->next = NULL; return newNode; }

很多人写代码不判断malloc的返回值，这在竞赛里可能没事，但在产品环境里，内存分配失败就是灾难性的空指针解引用。我见过线上服务崩溃的日志，根本查不到业务逻辑问题，最后定位到就是一次malloc返回了NULL，代码直接往下访问了。

补充一个细节：free(p)之后，p指向的内存已经归还系统，但p这个变量本身还存着老地址。此时如果你不把它置成NULL，后面任何if (p != NULL)的判断都会骗过你。我习惯释放完立刻写p = NULL;，要养成肌肉记忆。

申请的时候也有人会纠结用sizeof(Node)还是sizeof(*p)。我推荐sizeof(Node)，因为直观；当然如果你写newNode->data = val之前忘了给data赋值，等会儿访问到的就是随机值，这是更常见的低级错误。

2.2 尾部插入和头部插入的选择

尾部插入是最符合直觉的插入方式，新节点总是放在链表末尾，保持原有顺序。核心逻辑：先找到最后一个节点，它的next目前是NULL，让它的next指向新节点。

void insertAtTail(Node **head, int val) { Node *newNode = createNode(val); if (newNode == NULL) return; if (*head == NULL) { *head = newNode; return; } Node *temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; }

这里我用了二级指针Node **head。为什么？因为当链表为空时，我需要修改头指针本身，让它指向新节点。如果函数的参数只是Node *head，那你在函数里改的只是头指针的副本，函数一结束就丢了。

头插法的代码更短，新节点直接插到最前面：

void insertAtHead(Node **head, int val) { Node *newNode = createNode(val); if (newNode == NULL) return; newNode->next = *head; *head = newNode; }

注意顺序：先把新节点的next指向原来的头节点，再把头指针挪到新节点上。反过来的话，头指针先被换掉，旧的第一个节点就再也找不到了。

工程中如果需要“后进先出”的数据顺序，头插法很合适；如果保持队列式先进先出，尾插法更合适。一定要留意的是，尾插法每次都要遍历到末尾，复杂度是O(n)。如果这个操作非常频繁，一个更好的办法是维护一个尾指针tail指向最后一个节点，插入时直接tail->next = newNode，然后更新tail。后面我会专门讲这个优化。

2.3 按位置插入：前驱节点的定位

按位置插入，核心难点不在于构造新节点，而在于找到“该插入位置的前一个节点”。很多人写插入代码老是差一个位置，都是因为对“前驱”这个概念理解得不够透。

假如链表是 A -> B -> C，想在索引1的位置（B之前）插入X，我们要做的是：

1. 找到A，因为A是B的前驱。
2. X->next = A->next（也就是B）
3. A->next = X

int insertAtIndex(Node *head, int index, int val) { Node *newNode = createNode(val); if (newNode == NULL) return -1; Node *prev = head; for (int i = 0; i < index - 1 && prev != NULL; i++) { prev = prev->next; } if (prev == NULL) { // 说明index越界 free(newNode); return -1; } newNode->next = prev->next; prev->next = newNode; return 0; }

索引从0开始的时候，插入到第0个位置意味着prev就是head本身。在带头结点的链表里，这仍然成立。在不带头结点的链表里，你单独得处理head变化的情况，所以写起来会多一点if分支。

我自己习惯的逻辑是：先特判位置是否合法，再特判是否要插入到头部，之后统一走“找前驱”的逻辑。这样分支清晰，出bug概率低。

2.4 删除操作的指针修改顺序

删除节点本质就是让前驱跨过被删节点，直接连到被删节点的后继。但这里有个新手最容易漏的地方：先保存后继，再释放空间。

int deleteNode(Node **head, int val) { if (*head == NULL) return -1; Node *prev = NULL; Node *cur = *head; // 如果删除的是第一个节点 if (cur->data == val) { *head = cur->next; free(cur); return 0; } // 否则继续往后找 while (cur != NULL && cur->data != val) { prev = cur; cur = cur->next; } if (cur == NULL) { return -1; // 没找到这个值 } prev->next = cur->next; free(cur); // 释放的是cur，不是cur->next return 0; }

我看到过有人写成free(cur->next); prev->next = cur;，那等于把后面的节点删了，还把当前节点接到后面，逻辑完全乱了。

另外一个常见误区是在free之后还去访问cur->data。这点尤其隐蔽：如果删的是最后一个节点，你free(cur)之后，cur->next本身也是无效访问，虽然某些编译器不报错，但这是未定义行为。你不知道它会在哪个角落炸。

删除完节点，记得让前一个节点直接指向后一个节点。然后想都不用想，cur = NULL;。

2.5 遍历与链表的长度统计

遍历单链表是所有操作的基础。你查某个值存不存在、打印所有元素、统计长度，都是同一种模式：用一个临时指针从head出发，循环到NULL为止。

void traverseList(Node *head) { Node *cur = head; while (cur != NULL) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULL\n"); }

有一个小细节：遍历时不要拿head直接走，宁可多用几个辅助指针。如果你把head挪没了，整个链表就丢了。面试写链表的时候尤其要养成这个习惯。

int listLength(Node *head) { int len = 0; Node *cur = head; while (cur != NULL) { len++; cur = cur->next; } return len; }

这里的循环到底是while(cur != NULL)还是while(cur->next != NULL)，取决于你的目标。如果只是“走过每个节点”，用前者；如果要在某个场景下找“最后一个节点”，用后者。我自己写遍历固定都用前者，需要最后一个节点时才单独换。

3. 进阶操作与算法思维

3.1 反转单链表的两种思路

反转单链表是链表面试题中出镜率前三的题，也最能检验你到底有没有理解指针的修改。表面上是“一个循环就做完了”，但真动手的时候很容易纠结。

思路一：迭代反转，逐个把方向掰过来。

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

这里的关键是：先存next，再改指针方向，否则一旦改了cur->next，原来那个后继节点就找不到了。

你可以把反转理解成“把一串珠子拿在手里，一颗一颗从原串上摘下来，重新串到一根新线上”，每次都是新串的头部变成当前珠子。整个过程就三行逻辑，却让很多人写出各种版本，核心还是对“下一个节点要提前保存”体会不够深。

思路二：递归反转。递归的写法看起来很省事，但初学时容易想不通：

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; }

这段代码的思维顺序是：先反转后面的子链表，得到新头；再把原来当前节点接到尾部；最后返回新头。其实递归版的中心思想，是“假设后面的链表已经反转好了，我只需要处理当前节点”。

对我来说，迭代版更通用，递归版更优雅但容易在“栈溢出”边缘试探。如果链表特别长，例如十几万个节点，递归深度过深就会爆栈。工程里我还是偏好迭代实现，考试里两种都要会写。

3.2 双指针技巧：快慢指针找到中间节点

很多链表操作都可以用双指针来简化，其中最常见的场景就是找到链表的中间节点。

思路：slow每次走一步，fast每次走两步。

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

为什么这样就能找到中间？因为fast走完整个链表时，slow正好走了一半。这里的边界条件fast != NULL && fast->next != NULL要仔细理解，否则偶数和奇数长度下容易出错。如果你想要靠左的中间点，循环条件是fast->next != NULL；如果你想要靠右的中间点，循环条件稍加变化就可以了。

快慢指针的应用不止于此。比如判断链表是否有环：fast每次走两步，slow每次走一步，如果有环，fast会从后面追上slow；如果无环，fast会先到NULL。这类题是算法竞赛里经常碰见的，多练几遍自然就熟了。

3.3 合并两个有序单链表

这道题也是经典中的经典。给定两个升序链表，要合并成一个新的升序链表。最直接的做法是拿个虚拟头结点，然后同时遍历两条链表，谁小谁先接上。

Node *mergeTwoLists(Node *l1, Node *l2) { Node dummy; // 栈上临时节点，不必malloc dummy.next = NULL; Node *tail = &dummy; while (l1 != NULL && l2 != NULL) { if (l1->data <= l2->data) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } if (l1 != NULL) tail->next = l1; if (l2 != NULL) tail->next = l2; return dummy.next; }

用栈上虚拟头结点dummy的好处是：不用处理“结果链表第一个节点是谁”这种分支，统一走tail->next即可。最后返回dummy.next，注意别返回&dummy，那个在函数结束后就失效了。

3.4 尾指针优化：从O(n)到O(1)

前面提到尾插法每一次都要遍历到尾部，这是O(n)的。如果你要频繁在尾部插入，很自然的优化就是维护一个尾指针tail。

typedef struct { Node *head; Node *tail; } List;

初始化时让tail和head都指向NULL；插入时：

void pushBack(List *list, int val) { Node *newNode = createNode(val); if (newNode == NULL) return; if (list->head == NULL) { list->head = newNode; list->tail = newNode; } else { list->tail->next = newNode; list->tail = newNode; } }

这样插入尾部变成O(1)。但是注意：如果你在头部插入，或者删除节点，tail可能就不再指向真正的尾节点了。比如删除唯一一个节点后，tail就得重置为NULL。

维护尾指针在实现队列的时候特别省心。我当初给某个模拟缓冲区写队列数据存储，用的就是带头结点加尾指针的单链表，出队从头结点后摘，入队从尾部接，两个操作全是O(1)，结构简单又高效。

4. 性能对比与工程场景分析

4.1 单链表和顺序表的取舍

我在实际项目里选结构的时候，往往不是“链表一定好”，而是看读写模式。下表是我比较习惯的参考口径：

注意表中链表“中间插入O(n)”虽然和数组一样，但链表的O(n)开销在遍历查找上，数组的O(n)开销在搬移数据上。链表找到了前驱节点后，插入本身是O(1)的，不需要搬移任何数据；而数组找到了位置后还得把后面所有元素挪一遍。所以在插入删除频繁的场景，链表优势很明显。

内存规划上，数组需要预分配或扩容，链表每个节点都是按需分配。但链表的每个节点都多一个指针域，而且每个节点都是独立malloc，内存碎片可能更严重。这个在嵌入式或长时间运行的服务端要特别注意。

4.2 单链表与双链表的选择

双链表每个节点多一个前驱指针prev，这让它能双向遍历。带来的直接好处是：如果你知道某个节点，删除它的操作可以达到O(1)（前提是你能随时拿到该节点），不用再从头找前驱。

但代价也不小：每个节点多一个指针域，内存开销大了；插入删除时维护的指针数量变多，代码出错率上升；缓存局部性不如单链表。

我自己的选型经验：

• 只需要顺序访问、频繁在表头或表尾操作：优先单链表。
• 需要从尾部往头部反向遍历、或者频繁删除“已知节点”：双链表。
• 算法题里LRU缓存淘汰、某些内核队列：双链表几乎必备，因为它需要在O(1)时间内把桶中某个节点摘下来并整体调整顺序。

单链表还有一种环形变体：尾节点的next指向头结点，形成环。环形链表支持从任意节点开始遍历整个链表，常用来做轮询调度。我写过的一个模拟时间片轮转调度器，就用循环单链表存任务队列，每次从当前位置往下走一个节点就是下一个要执行的任务，数据结构上非常契合。

4.3 内存管理与性能隐患

单链表的内存问题是实战里最大的坑。最常见的有这几类：

• malloc失败不检查，直接解引用空指针；
• 忘记free，产生内存泄漏。服务端程序每删除一个节点漏一批，时间一长内存就飙上去了；
• free之后没有置NULL，后面误用悬空指针，造成逻辑错误甚至崩溃；
• 删除节点时把next弄丢，导致整条链表后半截变成孤儿内存。

我自己排查线上问题的时候，遇到“链表操作偶发崩溃”的case，十有八九跟悬空指针有关。后来我养成了一些固定习惯：

void destroyList(Node *head) { Node *cur = head; while (cur != NULL) { Node *next = cur->next; free(cur); cur = next; } }

销毁链表的逻辑和反转链表一样，核心都是“先保存下一个，再释放当前”。这个写法永远不会丢节点。

4.4 工程中单链表的实际应用

单链表写在教科书里看着简单，其实工程里随处可见。

比如哈希表的拉链法：每个哈希桶是一个单链表头，冲突的元素挂到链表下面。Java的HashMap早期版本也用过类似思路。再比如内存分配器里的空闲块链表：按大小把空闲内存块串起来，分配时摘一块。还有文件系统目录树、图的邻接表表示等，底层大量依赖链表结构。

我参与过的一个模拟操作系统任务调度模块，就维护了几个不同的单链表来存不同优先级的待执行任务，插入新任务按优先级入队，删除任务用值查找后摘除。整个模块查代码、改代码都非常直观。核心原因并不是链表性能无敌，而是它结构透明、内存可控，适合这种“短任务频繁增删”的模型。

如果你以后写内核模块、驱动、中间件，链表更是基础。很多内核结构就是带prev和next的侵入式链表，节点内部嵌着链表字段，再通过container_of得到宿主结构体。不过那是进阶玩法，初学阶段先把独立链表搞扎实。

5. 常见问题与调试技巧

5.1 空指针和野指针

空指针解引用是链表代码里最常见的崩溃原因。要么head为NULL，但你直接head->data；要么查找过程中指针已经走到NULL，你还继续cur->next。

我的经验是：每次while循环里要不要判断cur != NULL，取决于你的逻辑。如果你要访问cur->data，那必须确保cur不为空。一个通用习惯：查完NULL再解引用，宁多勿少。

while (cur != NULL && cur->data != val) { cur = cur->next; }

这里的顺序是先判cur != NULL，再访问cur->data。由于&&的短路特性，前一个条件为假后面就不会执行，所以不会产生空指针访问。

5.2 死循环问题

初始化的时候忘了把节点的next置NULL，或者插入时没有正确设置末尾节点，就可能形成环，造成遍历死循环。

我有一个排查死循环的笨办法：遍历循环里打印当前节点值和next。如果发现某个节点next指向了前面的节点，那基本可以确定循环了。如果链表很长，直接限制打印次数，比如只能走1000步，超过就退出。

更科学的办法是快慢指针检测环：一旦fast追上slow，环就必然存在。这也正是判环题的核心思路，你在调试过程中顺手就能验证算法。

5.3 插入删除操作中的指针丢失

指针丢失的典型场景：

• 反转链表时不保存next，改cur->next后找不到后继；
• 链表头部插入时，先改head再改newNode->next，导致新节点自成一串，和原链表断开；
• 删除节点后，重新连接顺序写反，导致前驱指向被删节点，甚至形成环路。

调试的时候我喜欢在每一步关键操作后打印一次链表，对比预期。说白了，指针修改就是“旧链断开之前，先留好退路”。

5.4 如何用调试器快速定位

我调试链表问题的标准姿势：

1. 用GDB或Visual Studio调试器设置断点，观察head、cur、prev这几个指针对应的节点。
2. 在关键循环处查看cur->next是否指向有效地址。
3. 如果内存地址异常，很大概率是使用已释放的内存。
4. 多节点数据用手工绘制一版简图，画节点的data和next，每一步更新，比盯内存快得多。

尤其画图这个方法，看着笨，但真的能帮你绕过很多抽象层面上的死磕。我甚至见过线上排查问题的老同事，在记事本里手画指针状态图找bug，十分钟就定位了。

5.5 一个完整的示例程序

最后给一个尽量完整的示例：创建链表、头插、尾插、删除、反转、销毁，全串起来跑一遍。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node* createNode(int val) { Node *newNode = (Node*)malloc(sizeof(Node)); if (newNode == NULL) { fprintf(stderr, "内存分配失败\n"); return NULL; } newNode->data = val; newNode->next = NULL; return newNode; } void insertAtHead(Node **head, int val) { Node *newNode = createNode(val); if (newNode == NULL) return; newNode->next = *head; *head = newNode; } void insertAtTail(Node **head, int val) { Node *newNode = createNode(val); if (newNode == NULL) return; if (*head == NULL) { *head = newNode; return; } Node *temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } int deleteByValue(Node **head, int val) { if (*head == NULL) return -1; Node *cur = *head; Node *prev = NULL; if (cur->data == val) { *head = cur->next; free(cur); return 0; } while (cur != NULL && cur->data != val) { prev = cur; cur = cur->next; } if (cur == NULL) return -1; prev->next = cur->next; free(cur); return 0; } Node* reverseList(Node *head) { Node *prev = NULL; Node *cur = head; while (cur != NULL) { Node *next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } void traverseList(Node *head) { Node *cur = head; while (cur != NULL) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULL\n"); } void destroyList(Node *head) { Node *cur = head; while (cur != NULL) { Node *next = cur->next; free(cur); cur = next; } } int main() { Node *head = NULL; insertAtTail(&head, 10); insertAtTail(&head, 20); insertAtTail(&head, 30); insertAtHead(&head, 5); printf("初始链表: "); traverseList(head); deleteByValue(&head, 20); printf("删除20后: "); traverseList(head); head = reverseList(head); printf("反转后: "); traverseList(head); destroyList(head); head = NULL; return 0; }

这段代码你能亲手跑一遍，再自己试着改成“带头结点版”和“带尾指针版”，单链表的基本功就算扎实了。

我在项目里还会把链表封装成独立模块，对外只暴露接口，内部实现细节用.c文件隔离。这样上层业务根本不需要关心节点指针怎么绕，也减少了误用指针的概率。

单链表只是数据结构的起点，但它训练的是“用指针控制内存”的思维。这种思维一旦建立起来，后面学任何复杂结构，比如二叉树的左孩子右兄弟表示、图邻接表、跳表、红黑树里的指针旋转，你都会有似曾相识的感觉。把这篇文章里的代码都自己敲一遍，尤其是反转链表和合并有序链表这两道题，熟练之后你会明显感觉到“指针再也不是玄学了”。