我前段时间帮某团队做一段代码审查发现他们用一个数组保存一份会频繁变动的配置清单中间插一条、删一条数据量大点就卡顿再大点直接定时器超时。问题倒不在循环体里写了什么而是底层数据结构选错了。最后把数组换成链表改动不大痛点全消。这类事见多了之后我越来越觉得基础数据结构四个字不是面试装饰品而是真正决定程序效率和稳定性的东西。这篇东西我就围绕链表这一个主题展开它到底比数组强在哪、弱在哪节点和指针在内存里是怎么回事单链表、双向链表、环形链表各自适合什么场景还有写链表代码时那些让人抓狂的边界错误怎么避开。最后聊几个我见过的真实应用场景帮你理解为什么这个东西这么受重视。如果你正准备系统过一遍数据结构或者写了几年代码但一直没真正搞懂链表这篇应该能帮到你。1. 数组没你想的那么便宜链表为什么存在很多人把数组当默认选择觉得用起来简单、性能也不错。没错数组的随机访问确实快a[i]一步到位CPU 还特别喜欢连续内存。但数组的一切优势都建立在一个前提上它占用一整块连续的内存空间。这个前提在有些场景下恰恰是最大的麻烦。1.1 连续内存带来的三个副作用第一个副作用是插入和删除要搬数据。想象一排座位坐满了人新来一个要坐在第三号位那你得让三号以后的所有人往后挪一格。数组操作也是一样的逻辑在中间插入或删除一个元素后面所有元素都要跟着移动时间复杂度是 O(n)。如果这个数组有十万个元素你只要在头部插一个就要搬九万多个。频繁操作时程序慢得肉眼可见。第二个副作用是扩容不可控。数组大小是固定的不够用了怎么办得重新申请一块更大的连续空间再把旧数据全部搬过去。这个操作一来是 O(n)二来是你根本不知道内存里还有没有那么大块的连续空间。找得到还好找不到就会报错。所以你在设计时要么预留很大的容量造成浪费要么冒着运行到一半扩容失败的风险。第三个副作用相对隐蔽是内存碎片。程序跑得久了内存里小块碎片到处都是真正想申请一大块连续内存时反而拿不到。这不是硬件问题是分配策略和生命周期共同作用的结果。对长时间运行的后端服务、嵌入式设备来说这问题很实际。我见过一个很典型的例子某系统用数组维护在线用户列表用户上下线频繁每次都在中间增删垃圾回收一触发就明显卡顿。后来换成链表插入删除只动指针不再搬移数据GC 压力骤降。这不是链表多玄学而是它从结构上绕开了搬移整段数据这个问题。1.2 链表的本质用指针换灵活性链表的结构可以这样理解它不要求一个个节点在内存里挨着坐每个节点带着数据和一个指向下一个节点的指针像珠子一样被一根线串起来。只要你知道第一个节点在哪顺着指针就能走完整个序列。这个设计带来的直接好处就是插入和删除一个新节点只需要改前一个节点的指针指向根本不用动其他节点。哪怕链表有一百万个节点在头部插入一个节点也只是O(1)操作因为剩下的节点连挪都不用挪。代价在于链表失去了随机访问能力。你想找第 k 个节点必须从头部一步一步走时间 O(n)。另外每个节点多存一个指针多占内存节点分散在内存各处遍历时 CPU 缓存的命中率也不如连续数组。这正是我常说的没有最优结构只有是否匹配场景。一句话总结读多写少、大小稳定数组合适写多读少、长度动态链表合适。理解这个差异你才能在自己的项目里做出不那么想当然的选择。2. 链表的核心构造节点、指针与内存布局链表这个名字很好理解但它真正的难点在于节点和指针这两个概念落到代码里之后一个没想清楚就会出现奇奇怪怪的崩溃。这一节我们把内存布局讲透后面的代码你就能看得明明白白。2.1 一个节点到底长什么样单链表的节点从数据结构的视角看只有两个部分数据域和指针域。数据域存你要放的业务数据指针域存下一个节点的地址。用 C 语言定义大概是这样的struct Node { int data; // 数据域这里以 int 为例 struct Node *next; // 指针域指向下一个节点 };内存里大概是这个感觉------------ ------------ ------------ | data | next | --- | data | next | --- | data | next | ------------ ------------ ------------画出来很简单但请务必意识到next里面存的是地址不是链表下一个节点的复制品。很多人写链表代码出问题就是脑子里把next想成了一个实际节点然后对一个地址变量反复做错误的赋值和取值操作。如果你使用高级语言比如 Java、Go 或 Python节点的指针概念被语言隐藏了一部分但本质不变。Java 里的Node nextGo 里的*Node next都是地址只不过语言帮你做了一些校验。理解底层原理不会因为语言不同就失效。2.2 头指针、哨兵节点与空表有经验的工程师写链表几乎都会加一个哨兵节点也叫头节点或 dummy node。这个节点不存业务数据只起一个锚点的作用让链表永远有一个不空的开头。哨兵节点最大的价值是消灭特殊分支。不带头节点的链表在处理删除第一个节点时要单独改头指针代码容易写成if (head target) { head head-next; }。有了哨兵节点删除逻辑统一成让某个节点的 next 跳过目标节点头指针永远不用动。这个变化看着小但对边界情况的处理影响巨大。我举个例子。假设链表结构是dummy - 1 - 2 - 3 - NULL。这里的dummy就是头节点真正的业务数据从dummy-next开始。这样设计的直接好处是删除第一个数据节点也就是1操作和删除中间节点完全一致遍历时判断条件统一为current-next ! NULL空表也有一个确定的节点对象不会被各种空指针问题打得措手不及。用哨兵节点会让内存里多一个不存数据的节点但这点开销换来的代码简洁非常划算。我在实际工程里几乎不会写不带头节点的链表操作。2.3 内存生命周期创建、使用、释放链表节点不是语法自动管理的尤其是在 C/C 这类语言里谁分配谁释放必须搞得很清楚。创建节点一般这样写struct Node *node (struct Node *)malloc(sizeof(struct Node)); if (!node) { // 内存分配失败要做异常处理 } node-data value; node-next NULL;这里有个初学者容易忽略的点malloc返回的是一块未初始化的内存里面的内容垃圾值所以你必须立刻给next赋 NULL否则这个节点就成了一个指向未知地址的野节点。后续遍历时一旦走到这个节点就可能访问一个非法地址。删除节点则涉及另一件重要的事先摘链再释放。也就是先把前驱的next改好让节点从链上摘下来然后再free(node)。顺序反了你释放完节点再去改前驱的指针那就是典型的悬垂指针问题运行时不崩溃是运气崩溃是常态。高级语言虽然有自动内存回收不用你手动free但引用是否还被持有这件事你心里要有数。链表节点被摘下来之后如果还有别的变量指向它对象就不会被回收这在长期运行的服务里就是内存泄漏的隐性来源。3. 单链表的增删查改完整实现与边界处理聊完理论直接上代码。这一节我会给一个能编译、能运行的最小单链表实现然后用为什么这样写的方式解释关键步骤。你在实际项目里可以参考这套骨架根据业务类型替换data字段。3.1 从零定义一个单链表我以 C 语言为例因为指针和内存分配一览无余翻译成其他语言也很容易。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 创建一个带哨兵节点的空链表 Node *createList() { Node *head (Node *)malloc(sizeof(Node)); head-next NULL; return head; } // 根据值创建一个新节点 Node *createNode(int value) { Node *node (Node *)malloc(sizeof(Node)); node-data value; node-next NULL; return node; }createList返回的这个哨兵节点next必须是 NULL。之后所有操作可以统一从这个哨兵开始不用再为链表为空写额外分支。3.2 核心操作插入、删除、查找、反转尾部插入是最简单的操作。循环到最后一个节点把尾部节点的next指向新节点void append(Node *head, int value) { Node *cur head; while (cur-next ! NULL) { cur cur-next; } cur-next createNode(value); }这里有一个关键点while 的判断条件是cur-next ! NULL而不是cur ! NULL。如果写成cur ! NULL循环结束后cur已经变成了 NULL你拿 NULL 去赋next就是空指针解引用。要找到最后那个可以挂新节点的节点而不是走到 NULL 里去。指定位置插入假设在第 index 个位置插入void insertAt(Node *head, int index, int value) { Node *cur head; for (int i 0; i index cur ! NULL; i) { cur cur-next; } if (cur NULL) { return; // 越界不做操作 } Node *newNode createNode(value); newNode-next cur-next; cur-next newNode; }核心思想找到要插入位置的前驱节点把新节点接上去。注意两行赋值的顺序newNode-next cur-next先执行然后cur-next newNode。如果后执行cur-next已经被覆盖成新节点原来的后继就丢了这就是经典的指针丢失。删除指定值的节点需要找到前驱void deleteByValue(Node *head, int value) { Node *cur head; while (cur-next ! NULL cur-next-data ! value) { cur cur-next; } if (cur-next NULL) { return; // 没找到 } Node *toDelete cur-next; cur-next toDelete-next; free(toDelete); }这个函数里哨兵节点的作用体现得很直观删除第一个真正数据节点时cur还是头节点实现逻辑和删除中间节点完全一致。反转链表是很多面试的常客也是真正考验指针操作熟练度的地方Node *reverseList(Node *head) { Node *prev NULL; Node *cur head-next; while (cur ! NULL) { Node *next cur-next; // 先把下一个节点记住 cur-next prev; // 当前节点指向前一个 prev cur; // 前一个移到当前 cur next; // 当前移到下一个 } head-next prev; return head; }这段代码的美感在于它原地反转不需要新建任何节点。但初学者几乎一写就错原因在于没有额外变量保存下一个节点。当你执行cur-next prev时原有的cur-next已经丢了后面想继续遍历就断了。那三行赋值少了任何一行都会出问题。3.3 复杂度对比与边界测试清单把链表和数组的核心操作复杂度放一起对比结论会很清楚操作数组单链表随机访问第 k 个元素O(1)O(n)头部插入/删除O(n)O(1)尾部插入/删除O(1)知道长度O(1)有尾指针中间插入/删除O(n)O(n)但只遍历不搬移内存占用少但有预留浪费多一个指针/节点写链表代码时边界测试请一定覆盖这几类空表、只有一个节点、删除第一个节点、删除最后一个节点、插入位置为 0、插入位置越界。我自己的习惯是把这些场景写进一个测试函数每次跑完主流程再跑一遍边界能挡住绝大多数回归问题。4. 写链表时最容易翻车的几个场景一次完整排查链表出问题的套路其实很固定远没有网上传的那么玄。你把下面这几种情况记牢了90% 的坑都能避开。这一节我用自己的排查经历来讲比干巴巴列规则更好记。4.1 指针丢失经典的两句话顺序问题某个新来的同事写了这样一段插入逻辑cur-next newNode; // 先把前驱的 next 指向新节点 newNode-next nextTemp; // 再把新节点的 next 指向原来后面的节点看起来差不多逻辑上却大错特错。第一行执行后原来cur-next指向的那个节点已经不再通过链表可达临时变量nextTemp又没提前保存导致后半段链表整个丢失。这在大型链表里表现非常诡异数据看起来还在但遍历走不到既不是崩溃也不是立刻报错真的是最难排查的那种 Bug。正确顺序我前面强调过了先接后继再接前驱。一句话口诀先让新节点找到它的下一个再让前驱找到新节点。无论插入还是删除时刻保证链在每一步操作后都是完整的。4.2 空表、单节点、尾节点三种最容易崩的位置空表上执行删除head-next就是 NULL如果代码里直接head-next-data立刻空指针崩溃。单节点链表删除唯一节点后没有把链表状态置为合法二次操作就会出问题。删除尾节点时你很容易想当然地认为那个节点肯定是最后一个于是直接free却没把前驱的next置 NULL变成悬垂指针。我在排查这类问题时最常用的做法是写一个很小的调试函数void printList(Node *head) { Node *cur head-next; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); }一次崩溃立刻在可疑操作前后各打一次链表状态看它是从哪里断的。比脑补快得多。我见过太多人卡在链表 Bug 里其实不是不会写而是没有用工具观察中间状态全靠猜。4.3 一次删除节点后程序崩溃的完整排查路径我印象很深的一次是某模块在批量删除后偶发崩溃。当时的现场是删掉一批节点程序跑几轮后才崩崩溃栈又指向一个看似无关的遍历函数。用printList打印发现链表的尾部不是 NULL而是指向了一个已释放的内存地址。进一步查问题出在删除最后一个节点的逻辑里。那版代码是Node *cur head; while (cur-next ! NULL) { if (cur-next-data target) { Node *tmp cur-next; cur-next tmp-next; free(tmp); } cur cur-next; }乍看没问题其实有几个隐患。删除后没有立即退出循环cur仍然在旧位置然后继续cur cur-next如果新接上的节点也需要处理就会出现跳过节点的情况。更严重的是如果待删除节点是最后一个tmp-next是 NULLfree(tmp)后链表尾部指针没问题但是循环里cur cur-next会让cur走到 NULL下一次 while 判断时cur-next直接解引用空指针必崩。这类问题的通病是删除后继续遍历时循环变量没有正确处理。我的结论是删除操作完成时要么立即 return要么把cur保持在原地重新判断。别让已经被摘掉、甚至已经释放的节点影响后续流程。排查链路总结一下先看崩溃栈定位到哪一行再看那行访问了哪个指针然后用打印或调试器确认该指针指向的内存状态最后根据链表是否被破坏反向找破坏点。大概率的根因就这么几类指针丢失、未判空、释放后继续使用、循环变量推进错误。5. 双向链表与环形链表什么时候值得换结构单链表是最基础的形态但工程里单链表往往不够用。真正的问题是它只能单向走删除一个节点时必须知道前驱它还有一个终点 NULL遍历总是停在一个地方。这两种局限分别催生了双向链表和环形链表。5.1 双向链表用一格内存换掉一个 O(n) 操作双向链表的每个节点多了一个prev指针指向它的前一个节点。定义大约是这样的struct DNode { int data; struct DNode *prev; struct DNode *next; };多了这个prev最直接的变化是在已知某个节点的情况下删除它只需要 O(1)。单链表里你想删一个节点必须从头遍历找前驱双向链表里直接从node-prev就知道前驱是谁改两个指针就完成删除void deleteNode(struct DNode *node) { if (node-prev) { node-prev-next node-next; } if (node-next) { node-next-prev node-prev; } free(node); }代价是每个节点多了一个指针的内存占用。节点数量大、指针占用内存不可忽略时这个开销值得认真评估。我一般这样取舍如果业务里给一个节点立刻删掉它的需求频繁出现双向链表值得如果只是顺序遍历加尾部插入单链表完全够用别白白浪费内存。5.2 环形链表没有终点的遍历环形链表就是把尾节点的next指回头节点整个链表连成一个环。好处是你可以从任意位置出发持续不断循环访问所有节点适合轮询、轮转调度这类走到末尾又重新开始的场景。环形链表的一个经典问题是判断是否有环也就是著名的快慢指针方法快指针每次走两步慢指针每次走一步如果链表有环它们迟早会相遇如果无环快指针最终到 NULL。这个算法写起来很简洁bool hasCycle(Node *head) { if (head NULL) return false; Node *slow head; Node *fast head-next; while (fast ! NULL fast-next ! NULL) { if (slow fast) return true; slow slow-next; fast fast-next-next; } return false; }还有一个衍生问题怎么找到环的入口。这需要一点数学推导思路是在快慢指针首次相遇后再让两个指针以相同速度走最终会在入口相遇。这类题目的价值不在于比赛而在于让你真正理解指针移动步长不同会产生什么效果。5.3 怎么根据自己的场景选型选型的核心维度就三个内存占用、操作效率、实现复杂度。内存紧张且只做顺序访问和尾部添加单链表需要频繁按已知位置删除双向链表需要轮转遍历、或者有天然的循环语义环形链表并发环境下共享链表还需要考虑加锁粒度这一般会把问题复杂化建议先用标准库的并发容器不要自己造轮子。我在实际项目里见过不少人上来就双向链表理由是以后可能用得上。我不太认同这种预优化——内存成本和代码复杂度都是可见的负债而以后大多数时候并不会来。按当前确定的业务需求选比按想象的不确定性选靠谱得多。6. 链表在真实系统里的几个应用不只是面试题很多开发者觉得链表就是面试题面试完就再也用不到了。这个看法真的不对。它只是被封装在标准库的容器里你没有直接看到而已。链表的形态在真实系统里到处都是而且扮演的角色相当核心。6.1 哈希表的链地址法最常见的场景之一就是哈希表。两个不同的键算出来同一个哈希桶位置发生冲突了怎么办很多实现是每个桶挂一个链表相同哈希地址的元素全放到那个桶对应的链表里。你可以理解成一个数组但数组的每个格子不是直接存元素而是指向一条链表的头部。查找时先算哈希定位到桶再顺着链表逐个比较。元素少的时候链短查找很快元素多到链表过长才会触发扩容或转成树结构。链表的插入删除优势在这里发挥得淋漓尽致——桶内增删元素不需要搬移同桶的其他元素。6.2 LRU 缓存里的淘汰队列LRULeast Recently Used缓存淘汰策略背后的数据结构通常就是双向链表加哈希表。哈希表负责 O(1) 找到缓存项双向链表负责记录每个缓存项的访问顺序最新访问过的挪到头部最久没访问的留在尾部缓存满时淘汰尾部即可。这套组合很值得玩味。它同时用到了链表的两个特性插入删除快以及相对顺序可以动态调整。每次访问一个缓存项把它从链表中间摘下来再插到头部只需要改指针不需要搬移其他数据。如果是数组实现这个顺序调整每次都得移动一串元素。LRU 的高效靠的就是链表这个底层结构。我在实际业务里实现过一个规模不小的 LRU 缓存最初想省事用数组加标志位访问命中后要挪位置性能差强人意。后来老老实实换上哈希表双向链表一次命中挪动从 O(n) 变成 O(1)整体的吞吐量提升非常明显。6.3 内存池与空闲链表操作系统和底层中间件里内存池的空闲块管理也大量依赖链表。空闲内存块会被串成一个链表称为空闲链表。你需要分配内存的时候从链上摘下合适大小的块回收的时候再把块挂回去。这里链表的好处是空闲块本身不需要额外存储空间来保存指针因为块本身就是未被使用的指针可以直接存在块头。这种借用空闲空间存数据的手法体现了链表设计里很底层的一面。嵌入式领域尤其常见有时候根本不用标准malloc直接操作自己维护的空闲链表。6.4 链表的经验心得如果你问我链表练到什么程度才算真正掌握我的标准很简单不带参考资料写一个带头节点的单链表覆盖插入、删除、反转、查找然后跑一遍边界测试全程不出错也不犹豫。能做到这一点的开发者写业务代码时对数据结构的感知力通常都不差。练的时候建议多做一件事每一段链表操作代码都画出它在内存里的连接变化。链表所有 Bug 的根源几乎都可以归结为内存里的连接状态和自己脑补的不一致。把你的脑补逼到和真实状态一样链表这道坎就真正过去了。后面不管学树、图还是跳表你都会发现它们的底层逻辑跟链表一脉相承。 
长河君 · 2026/10/10 2:09:53 · 阅读 1.2k 链表 vs 数组：从原理到实战，彻底搞懂这个基础数据结构
我前段时间帮某团队做一段代码审查发现他们用一个数组保存一份会频繁变动的配置清单中间插一条、删一条数据量大点就卡顿再大点直接定时器超时。问题倒不在循环体里写了什么而是底层数据结构选错了。最后把数组换成链表改动不大痛点全消。这类事见多了之后我越来越觉得基础数据结构四个字不是面试装饰品而是真正决定程序效率和稳定性的东西。这篇东西我就围绕链表这一个主题展开它到底比数组强在哪、弱在哪节点和指针在内存里是怎么回事单链表、双向链表、环形链表各自适合什么场景还有写链表代码时那些让人抓狂的边界错误怎么避开。最后聊几个我见过的真实应用场景帮你理解为什么这个东西这么受重视。如果你正准备系统过一遍数据结构或者写了几年代码但一直没真正搞懂链表这篇应该能帮到你。1. 数组没你想的那么便宜链表为什么存在很多人把数组当默认选择觉得用起来简单、性能也不错。没错数组的随机访问确实快a[i]一步到位CPU 还特别喜欢连续内存。但数组的一切优势都建立在一个前提上它占用一整块连续的内存空间。这个前提在有些场景下恰恰是最大的麻烦。1.1 连续内存带来的三个副作用第一个副作用是插入和删除要搬数据。想象一排座位坐满了人新来一个要坐在第三号位那你得让三号以后的所有人往后挪一格。数组操作也是一样的逻辑在中间插入或删除一个元素后面所有元素都要跟着移动时间复杂度是 O(n)。如果这个数组有十万个元素你只要在头部插一个就要搬九万多个。频繁操作时程序慢得肉眼可见。第二个副作用是扩容不可控。数组大小是固定的不够用了怎么办得重新申请一块更大的连续空间再把旧数据全部搬过去。这个操作一来是 O(n)二来是你根本不知道内存里还有没有那么大块的连续空间。找得到还好找不到就会报错。所以你在设计时要么预留很大的容量造成浪费要么冒着运行到一半扩容失败的风险。第三个副作用相对隐蔽是内存碎片。程序跑得久了内存里小块碎片到处都是真正想申请一大块连续内存时反而拿不到。这不是硬件问题是分配策略和生命周期共同作用的结果。对长时间运行的后端服务、嵌入式设备来说这问题很实际。我见过一个很典型的例子某系统用数组维护在线用户列表用户上下线频繁每次都在中间增删垃圾回收一触发就明显卡顿。后来换成链表插入删除只动指针不再搬移数据GC 压力骤降。这不是链表多玄学而是它从结构上绕开了搬移整段数据这个问题。1.2 链表的本质用指针换灵活性链表的结构可以这样理解它不要求一个个节点在内存里挨着坐每个节点带着数据和一个指向下一个节点的指针像珠子一样被一根线串起来。只要你知道第一个节点在哪顺着指针就能走完整个序列。这个设计带来的直接好处就是插入和删除一个新节点只需要改前一个节点的指针指向根本不用动其他节点。哪怕链表有一百万个节点在头部插入一个节点也只是O(1)操作因为剩下的节点连挪都不用挪。代价在于链表失去了随机访问能力。你想找第 k 个节点必须从头部一步一步走时间 O(n)。另外每个节点多存一个指针多占内存节点分散在内存各处遍历时 CPU 缓存的命中率也不如连续数组。这正是我常说的没有最优结构只有是否匹配场景。一句话总结读多写少、大小稳定数组合适写多读少、长度动态链表合适。理解这个差异你才能在自己的项目里做出不那么想当然的选择。2. 链表的核心构造节点、指针与内存布局链表这个名字很好理解但它真正的难点在于节点和指针这两个概念落到代码里之后一个没想清楚就会出现奇奇怪怪的崩溃。这一节我们把内存布局讲透后面的代码你就能看得明明白白。2.1 一个节点到底长什么样单链表的节点从数据结构的视角看只有两个部分数据域和指针域。数据域存你要放的业务数据指针域存下一个节点的地址。用 C 语言定义大概是这样的struct Node { int data; // 数据域这里以 int 为例 struct Node *next; // 指针域指向下一个节点 };内存里大概是这个感觉------------ ------------ ------------ | data | next | --- | data | next | --- | data | next | ------------ ------------ ------------画出来很简单但请务必意识到next里面存的是地址不是链表下一个节点的复制品。很多人写链表代码出问题就是脑子里把next想成了一个实际节点然后对一个地址变量反复做错误的赋值和取值操作。如果你使用高级语言比如 Java、Go 或 Python节点的指针概念被语言隐藏了一部分但本质不变。Java 里的Node nextGo 里的*Node next都是地址只不过语言帮你做了一些校验。理解底层原理不会因为语言不同就失效。2.2 头指针、哨兵节点与空表有经验的工程师写链表几乎都会加一个哨兵节点也叫头节点或 dummy node。这个节点不存业务数据只起一个锚点的作用让链表永远有一个不空的开头。哨兵节点最大的价值是消灭特殊分支。不带头节点的链表在处理删除第一个节点时要单独改头指针代码容易写成if (head target) { head head-next; }。有了哨兵节点删除逻辑统一成让某个节点的 next 跳过目标节点头指针永远不用动。这个变化看着小但对边界情况的处理影响巨大。我举个例子。假设链表结构是dummy - 1 - 2 - 3 - NULL。这里的dummy就是头节点真正的业务数据从dummy-next开始。这样设计的直接好处是删除第一个数据节点也就是1操作和删除中间节点完全一致遍历时判断条件统一为current-next ! NULL空表也有一个确定的节点对象不会被各种空指针问题打得措手不及。用哨兵节点会让内存里多一个不存数据的节点但这点开销换来的代码简洁非常划算。我在实际工程里几乎不会写不带头节点的链表操作。2.3 内存生命周期创建、使用、释放链表节点不是语法自动管理的尤其是在 C/C 这类语言里谁分配谁释放必须搞得很清楚。创建节点一般这样写struct Node *node (struct Node *)malloc(sizeof(struct Node)); if (!node) { // 内存分配失败要做异常处理 } node-data value; node-next NULL;这里有个初学者容易忽略的点malloc返回的是一块未初始化的内存里面的内容垃圾值所以你必须立刻给next赋 NULL否则这个节点就成了一个指向未知地址的野节点。后续遍历时一旦走到这个节点就可能访问一个非法地址。删除节点则涉及另一件重要的事先摘链再释放。也就是先把前驱的next改好让节点从链上摘下来然后再free(node)。顺序反了你释放完节点再去改前驱的指针那就是典型的悬垂指针问题运行时不崩溃是运气崩溃是常态。高级语言虽然有自动内存回收不用你手动free但引用是否还被持有这件事你心里要有数。链表节点被摘下来之后如果还有别的变量指向它对象就不会被回收这在长期运行的服务里就是内存泄漏的隐性来源。3. 单链表的增删查改完整实现与边界处理聊完理论直接上代码。这一节我会给一个能编译、能运行的最小单链表实现然后用为什么这样写的方式解释关键步骤。你在实际项目里可以参考这套骨架根据业务类型替换data字段。3.1 从零定义一个单链表我以 C 语言为例因为指针和内存分配一览无余翻译成其他语言也很容易。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 创建一个带哨兵节点的空链表 Node *createList() { Node *head (Node *)malloc(sizeof(Node)); head-next NULL; return head; } // 根据值创建一个新节点 Node *createNode(int value) { Node *node (Node *)malloc(sizeof(Node)); node-data value; node-next NULL; return node; }createList返回的这个哨兵节点next必须是 NULL。之后所有操作可以统一从这个哨兵开始不用再为链表为空写额外分支。3.2 核心操作插入、删除、查找、反转尾部插入是最简单的操作。循环到最后一个节点把尾部节点的next指向新节点void append(Node *head, int value) { Node *cur head; while (cur-next ! NULL) { cur cur-next; } cur-next createNode(value); }这里有一个关键点while 的判断条件是cur-next ! NULL而不是cur ! NULL。如果写成cur ! NULL循环结束后cur已经变成了 NULL你拿 NULL 去赋next就是空指针解引用。要找到最后那个可以挂新节点的节点而不是走到 NULL 里去。指定位置插入假设在第 index 个位置插入void insertAt(Node *head, int index, int value) { Node *cur head; for (int i 0; i index cur ! NULL; i) { cur cur-next; } if (cur NULL) { return; // 越界不做操作 } Node *newNode createNode(value); newNode-next cur-next; cur-next newNode; }核心思想找到要插入位置的前驱节点把新节点接上去。注意两行赋值的顺序newNode-next cur-next先执行然后cur-next newNode。如果后执行cur-next已经被覆盖成新节点原来的后继就丢了这就是经典的指针丢失。删除指定值的节点需要找到前驱void deleteByValue(Node *head, int value) { Node *cur head; while (cur-next ! NULL cur-next-data ! value) { cur cur-next; } if (cur-next NULL) { return; // 没找到 } Node *toDelete cur-next; cur-next toDelete-next; free(toDelete); }这个函数里哨兵节点的作用体现得很直观删除第一个真正数据节点时cur还是头节点实现逻辑和删除中间节点完全一致。反转链表是很多面试的常客也是真正考验指针操作熟练度的地方Node *reverseList(Node *head) { Node *prev NULL; Node *cur head-next; while (cur ! NULL) { Node *next cur-next; // 先把下一个节点记住 cur-next prev; // 当前节点指向前一个 prev cur; // 前一个移到当前 cur next; // 当前移到下一个 } head-next prev; return head; }这段代码的美感在于它原地反转不需要新建任何节点。但初学者几乎一写就错原因在于没有额外变量保存下一个节点。当你执行cur-next prev时原有的cur-next已经丢了后面想继续遍历就断了。那三行赋值少了任何一行都会出问题。3.3 复杂度对比与边界测试清单把链表和数组的核心操作复杂度放一起对比结论会很清楚操作数组单链表随机访问第 k 个元素O(1)O(n)头部插入/删除O(n)O(1)尾部插入/删除O(1)知道长度O(1)有尾指针中间插入/删除O(n)O(n)但只遍历不搬移内存占用少但有预留浪费多一个指针/节点写链表代码时边界测试请一定覆盖这几类空表、只有一个节点、删除第一个节点、删除最后一个节点、插入位置为 0、插入位置越界。我自己的习惯是把这些场景写进一个测试函数每次跑完主流程再跑一遍边界能挡住绝大多数回归问题。4. 写链表时最容易翻车的几个场景一次完整排查链表出问题的套路其实很固定远没有网上传的那么玄。你把下面这几种情况记牢了90% 的坑都能避开。这一节我用自己的排查经历来讲比干巴巴列规则更好记。4.1 指针丢失经典的两句话顺序问题某个新来的同事写了这样一段插入逻辑cur-next newNode; // 先把前驱的 next 指向新节点 newNode-next nextTemp; // 再把新节点的 next 指向原来后面的节点看起来差不多逻辑上却大错特错。第一行执行后原来cur-next指向的那个节点已经不再通过链表可达临时变量nextTemp又没提前保存导致后半段链表整个丢失。这在大型链表里表现非常诡异数据看起来还在但遍历走不到既不是崩溃也不是立刻报错真的是最难排查的那种 Bug。正确顺序我前面强调过了先接后继再接前驱。一句话口诀先让新节点找到它的下一个再让前驱找到新节点。无论插入还是删除时刻保证链在每一步操作后都是完整的。4.2 空表、单节点、尾节点三种最容易崩的位置空表上执行删除head-next就是 NULL如果代码里直接head-next-data立刻空指针崩溃。单节点链表删除唯一节点后没有把链表状态置为合法二次操作就会出问题。删除尾节点时你很容易想当然地认为那个节点肯定是最后一个于是直接free却没把前驱的next置 NULL变成悬垂指针。我在排查这类问题时最常用的做法是写一个很小的调试函数void printList(Node *head) { Node *cur head-next; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); }一次崩溃立刻在可疑操作前后各打一次链表状态看它是从哪里断的。比脑补快得多。我见过太多人卡在链表 Bug 里其实不是不会写而是没有用工具观察中间状态全靠猜。4.3 一次删除节点后程序崩溃的完整排查路径我印象很深的一次是某模块在批量删除后偶发崩溃。当时的现场是删掉一批节点程序跑几轮后才崩崩溃栈又指向一个看似无关的遍历函数。用printList打印发现链表的尾部不是 NULL而是指向了一个已释放的内存地址。进一步查问题出在删除最后一个节点的逻辑里。那版代码是Node *cur head; while (cur-next ! NULL) { if (cur-next-data target) { Node *tmp cur-next; cur-next tmp-next; free(tmp); } cur cur-next; }乍看没问题其实有几个隐患。删除后没有立即退出循环cur仍然在旧位置然后继续cur cur-next如果新接上的节点也需要处理就会出现跳过节点的情况。更严重的是如果待删除节点是最后一个tmp-next是 NULLfree(tmp)后链表尾部指针没问题但是循环里cur cur-next会让cur走到 NULL下一次 while 判断时cur-next直接解引用空指针必崩。这类问题的通病是删除后继续遍历时循环变量没有正确处理。我的结论是删除操作完成时要么立即 return要么把cur保持在原地重新判断。别让已经被摘掉、甚至已经释放的节点影响后续流程。排查链路总结一下先看崩溃栈定位到哪一行再看那行访问了哪个指针然后用打印或调试器确认该指针指向的内存状态最后根据链表是否被破坏反向找破坏点。大概率的根因就这么几类指针丢失、未判空、释放后继续使用、循环变量推进错误。5. 双向链表与环形链表什么时候值得换结构单链表是最基础的形态但工程里单链表往往不够用。真正的问题是它只能单向走删除一个节点时必须知道前驱它还有一个终点 NULL遍历总是停在一个地方。这两种局限分别催生了双向链表和环形链表。5.1 双向链表用一格内存换掉一个 O(n) 操作双向链表的每个节点多了一个prev指针指向它的前一个节点。定义大约是这样的struct DNode { int data; struct DNode *prev; struct DNode *next; };多了这个prev最直接的变化是在已知某个节点的情况下删除它只需要 O(1)。单链表里你想删一个节点必须从头遍历找前驱双向链表里直接从node-prev就知道前驱是谁改两个指针就完成删除void deleteNode(struct DNode *node) { if (node-prev) { node-prev-next node-next; } if (node-next) { node-next-prev node-prev; } free(node); }代价是每个节点多了一个指针的内存占用。节点数量大、指针占用内存不可忽略时这个开销值得认真评估。我一般这样取舍如果业务里给一个节点立刻删掉它的需求频繁出现双向链表值得如果只是顺序遍历加尾部插入单链表完全够用别白白浪费内存。5.2 环形链表没有终点的遍历环形链表就是把尾节点的next指回头节点整个链表连成一个环。好处是你可以从任意位置出发持续不断循环访问所有节点适合轮询、轮转调度这类走到末尾又重新开始的场景。环形链表的一个经典问题是判断是否有环也就是著名的快慢指针方法快指针每次走两步慢指针每次走一步如果链表有环它们迟早会相遇如果无环快指针最终到 NULL。这个算法写起来很简洁bool hasCycle(Node *head) { if (head NULL) return false; Node *slow head; Node *fast head-next; while (fast ! NULL fast-next ! NULL) { if (slow fast) return true; slow slow-next; fast fast-next-next; } return false; }还有一个衍生问题怎么找到环的入口。这需要一点数学推导思路是在快慢指针首次相遇后再让两个指针以相同速度走最终会在入口相遇。这类题目的价值不在于比赛而在于让你真正理解指针移动步长不同会产生什么效果。5.3 怎么根据自己的场景选型选型的核心维度就三个内存占用、操作效率、实现复杂度。内存紧张且只做顺序访问和尾部添加单链表需要频繁按已知位置删除双向链表需要轮转遍历、或者有天然的循环语义环形链表并发环境下共享链表还需要考虑加锁粒度这一般会把问题复杂化建议先用标准库的并发容器不要自己造轮子。我在实际项目里见过不少人上来就双向链表理由是以后可能用得上。我不太认同这种预优化——内存成本和代码复杂度都是可见的负债而以后大多数时候并不会来。按当前确定的业务需求选比按想象的不确定性选靠谱得多。6. 链表在真实系统里的几个应用不只是面试题很多开发者觉得链表就是面试题面试完就再也用不到了。这个看法真的不对。它只是被封装在标准库的容器里你没有直接看到而已。链表的形态在真实系统里到处都是而且扮演的角色相当核心。6.1 哈希表的链地址法最常见的场景之一就是哈希表。两个不同的键算出来同一个哈希桶位置发生冲突了怎么办很多实现是每个桶挂一个链表相同哈希地址的元素全放到那个桶对应的链表里。你可以理解成一个数组但数组的每个格子不是直接存元素而是指向一条链表的头部。查找时先算哈希定位到桶再顺着链表逐个比较。元素少的时候链短查找很快元素多到链表过长才会触发扩容或转成树结构。链表的插入删除优势在这里发挥得淋漓尽致——桶内增删元素不需要搬移同桶的其他元素。6.2 LRU 缓存里的淘汰队列LRULeast Recently Used缓存淘汰策略背后的数据结构通常就是双向链表加哈希表。哈希表负责 O(1) 找到缓存项双向链表负责记录每个缓存项的访问顺序最新访问过的挪到头部最久没访问的留在尾部缓存满时淘汰尾部即可。这套组合很值得玩味。它同时用到了链表的两个特性插入删除快以及相对顺序可以动态调整。每次访问一个缓存项把它从链表中间摘下来再插到头部只需要改指针不需要搬移其他数据。如果是数组实现这个顺序调整每次都得移动一串元素。LRU 的高效靠的就是链表这个底层结构。我在实际业务里实现过一个规模不小的 LRU 缓存最初想省事用数组加标志位访问命中后要挪位置性能差强人意。后来老老实实换上哈希表双向链表一次命中挪动从 O(n) 变成 O(1)整体的吞吐量提升非常明显。6.3 内存池与空闲链表操作系统和底层中间件里内存池的空闲块管理也大量依赖链表。空闲内存块会被串成一个链表称为空闲链表。你需要分配内存的时候从链上摘下合适大小的块回收的时候再把块挂回去。这里链表的好处是空闲块本身不需要额外存储空间来保存指针因为块本身就是未被使用的指针可以直接存在块头。这种借用空闲空间存数据的手法体现了链表设计里很底层的一面。嵌入式领域尤其常见有时候根本不用标准malloc直接操作自己维护的空闲链表。6.4 链表的经验心得如果你问我链表练到什么程度才算真正掌握我的标准很简单不带参考资料写一个带头节点的单链表覆盖插入、删除、反转、查找然后跑一遍边界测试全程不出错也不犹豫。能做到这一点的开发者写业务代码时对数据结构的感知力通常都不差。练的时候建议多做一件事每一段链表操作代码都画出它在内存里的连接变化。链表所有 Bug 的根源几乎都可以归结为内存里的连接状态和自己脑补的不一致。把你的脑补逼到和真实状态一样链表这道坎就真正过去了。后面不管学树、图还是跳表你都会发现它们的底层逻辑跟链表一脉相承。