单链表这东西我在项目里用过无数次也帮人排查过无数次问题。每次讲到它我都觉得这玩意儿是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我们要做的是找到A因为A是B的前驱。X-next A-next也就是BA-next Xint 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(1)O(n)尾部插入/删除O(1)O(1)带尾指针时头部插入/删除O(n)需要搬移O(1)中间插入/删除O(n)大量搬移O(n)主要是查找缓存局部性优秀较差内存占用可能有预分配浪费多一个指针域的开销注意表中链表“中间插入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 如何用调试器快速定位我调试链表问题的标准姿势用GDB或Visual Studio调试器设置断点观察head、cur、prev这几个指针对应的节点。在关键循环处查看cur-next是否指向有效地址。如果内存地址异常很大概率是使用已释放的内存。多节点数据用手工绘制一版简图画节点的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文件隔离。这样上层业务根本不需要关心节点指针怎么绕也减少了误用指针的概率。单链表只是数据结构的起点但它训练的是“用指针控制内存”的思维。这种思维一旦建立起来后面学任何复杂结构比如二叉树的左孩子右兄弟表示、图邻接表、跳表、红黑树里的指针旋转你都会有似曾相识的感觉。把这篇文章里的代码都自己敲一遍尤其是反转链表和合并有序链表这两道题熟练之后你会明显感觉到“指针再也不是玄学了”。