★ FEATURED ARTICLE 1. 链表到底解决什么问题1.1 聊聊数组的尴尬处境我不敢说每一个学数据结构的人都会被链表劝退过但至少有一大半人在初学阶段会发出灵魂拷问明明数组用得好好的不管是遍历、查找还是排序都简单直接为什么还要发明链表这种麻烦的东西这个问题问得特别真实因为数组确实是计算机世界里最朴素、最自然的内存模型。你声明一个int arr[10]编译器就在内存里给你划出连续的一段空间下标从 0 到 9通过arr[i]直接算出地址就能访问时间复杂度 O(1)快得让人没有理由挑剔它。但数组真正让你头疼的地方在于两个场景第一个是插入和删除。假设你有一个长度为 100 的有序数组想在中间某个位置插入一个新元素你不得不把从这个位置开始的后面所有元素全部往后挪一格。更糟的是如果空间不够了还得重新申请更大的数组再把旧数据整体搬迁。删除也是同样的问题中间删掉一个元素后面的元素全得往前补位。这种操作的代价是 O(n)当数据量大了以后每一次插入删除都让人心如刀割。第二个是内存碎片的利用问题。你声明数组时必须一次申请一整块连续空间但这块空间的大小要在运行前或者运行中你说了算大了浪费、小了扩容又很痛。就算你有 20MB 的总内存如果它们分散成 100 个 200KB 的小碎片你想申请一个 1MB 的连续数组也照样失败。链表正是冲着这两个痛点来的它不要求连续存储每个节点散落在内存各处通过指针像链条一样串起来。这样插入、删除只需要改指针方向不需要大范围移动元素空间的利用也灵活得多。1.2 链表的本质用指针换灵活性链表的核心思想用一句话说清楚让每个节点记住它下一个邻居在哪。一个节点由数据域和指针域组成数据域存真实的数据指针域存下一个节点的地址。你只要拥有头节点的指针顺着指针一个个走就能遍历整条链。这其实很像现实中的“寻宝游戏”你只知道第一张纸条藏在哪里打开纸条里面写着第二张纸条的位置再按图索骥找到第三张……只要中间不断条你能沿着线索跑完全程。链表就是这么一种“线索式存储”它拿随机访问能力O(1) 按下标取元素换来了更好的插入删除效率O(1) 只要找到前驱节点和更灵活的内存使用方式。理解这一点非常重要。很多人写链表代码出 bug本质上是脑子里没有“每个节点都是独立散布的内存块它们之间的联系只是指针值”这个概念。一旦你把这个图景印在脑子里后面写遍历、插入、删除这些操作的时候思路就清晰多了。我见过很多初学者把链表节点想成数组元素下意识觉得它们在内存里挨着存放于是写代码时常常犯“把节点地址直接赋值给下一个节点”这种逻辑错误。记住一句话链表节点之间存在的是逻辑上的先后关系物理上它在哪完全无所谓主动权全在那根指针上。2. 链表的家族图谱先看清再动手2.1 单链表、双链表、循环链表怎么选链表不是一个单一的数据结构它有一大家子。最核心的是单链表、双向链表和循环链表搞清楚它们的差异你在实际项目里才能选对型号。单链表是最基础的形态每个节点只存一个后继指针。它省内存、结构简单但缺点也明显只能从头往后走想找前驱节点必须从头遍历一遍。我在嵌入式开发里经常用它因为嵌入式环境内存宝贵多一个指针都是成本而且大部分场景只需要顺序处理数据。双向链表每个节点多了一个前驱指针代价是每个节点多占一个指针的内存换来的是可以从两个方向遍历删除节点时不需要费劲找前驱。Java 的LinkedList底层就是双向链表LRU 缓存淘汰策略里也很常见。如果你需要频繁在链表中删除指定节点双向链表基本是最舒服的选择。循环链表则是把最后一节点的 next 指针指向头节点形成一个环。它适合环形缓冲、约瑟夫环这类“绕圈跑”的场景。循环链表还有一种变体叫循环双链表操作上更灵活但代码也更绕。实际写代码时循环链表的遍历终止条件不再是p-next NULL而是p-next head很多初学者在这里翻车因为退出条件变了却仍然按单链表的老思路写。判断自己场景应该选哪种我一般就两个标准要么看内存预算是否紧张紧张先考虑单链表要么看操作是否需要频繁回溯需要就上双向链表。2.2 头节点让边界条件统一起来的魔法链表里有一个特别容易被初学者忽略的设计就是头节点head node。注意我说的是头节点不是头指针。头指针是struct Node *head这种指向第一个节点的指针变量头节点则是额外申请一个不存实际数据的节点把它作为链表的第一个节点。真正的第一个数据节点是头节点的下一个。为什么要这么搞举个例子你就明白了。假设你写一个在 pos 位置插入新节点的函数如果链表为空或者插入位置在表头你是不是要单独处理 head 的更新有了头节点以后链表的第一个数据节点前永远站着一个“哨兵”在它后面插入和在其他节点后面插入的逻辑完全一致不需要写特判分支。代码量减少一半边界条件的出错几率也大幅下降。这种“哨兵设计”在计算机领域到处都是像数组里预留哨兵位、字符串末尾加\0终结符、排序算法里的哨兵牌思想都是一样的用一个额外的占位对象让常规逻辑统一把特殊分支消灭掉。不过头节点会多占一个节点的内存而且遍历时要注意跳过它。我的经验是学习阶段不带头节点的版本至少手写一次让你体会边界条件的烦恼之后做项目或者写考试代码如果允许直接用带头节点的版本省心得多。3. 手把手实现单链表核心操作3.1 C 语言版节点定义与链表创建C 语言是指针操作的“第一现场”链表这东西天生跟 C 的指针绑定在一起。我们定义一个学生成绩节点里面装学号和分数再用指针串起来。#include stdio.h #include stdlib.h typedef struct Student { int id; // 数据域学号 int score; // 数据域分数 struct Student *next; // 指针域指向下一个节点 } Student; // 创建带头节点的空链表 Student *createList() { Student *head (Student *)malloc(sizeof(Student)); if (head NULL) { printf(内存分配失败\n); return NULL; } head-next NULL; // 头节点不存数据next 先置空 return head; } // 头插法新节点插到头节点之后注意这里插序和输出正好相反 void insertAtHead(Student *head, int id, int score) { Student *newNode (Student *)malloc(sizeof(Student)); if (newNode NULL) return; newNode-id id; newNode-score score; newNode-next head-next; head-next newNode; } // 尾插法每次从头部遍历到末尾再挂接 void insertAtTail(Student *head, int id, int score) { Student *newNode (Student *)malloc(sizeof(Student)); if (newNode NULL) return; newNode-id id; newNode-score score; newNode-next NULL; Student *p head; while (p-next ! NULL) { p p-next; } p-next newNode; }这里有两个非常关键的细节。第一malloc之后一定要记得检查有没有返回NULL嵌入式开发里内存紧张经常分配失败你不检查就往下用段错误分分钟找上门。第二头插法插入的顺序和链表最终遍历出来的顺序是反的比如你按 1, 2, 3 依次头插遍历出来是 3, 2, 1。如果你需要保持输入顺序那就用尾插法代价是每次都要 O(n) 走到尾部。如果数据量很大又需要保持顺序更优的做法是额外维护一个尾指针每次直接挂到尾部把插入操作降为 O(1)。3.2 遍历、查找与链表长度统计遍历链表是基本功中的基本功代码不复杂但它的意义在于让你理解指针怎么“走路”。void printList(Student *head) { Student *p head-next; // 跳过不存数据的头节点 while (p ! NULL) { printf(学号: %d 分数: %d - , p-id, p-score); p p-next; // 沿 next 向下走 } printf(NULL\n); } Student *findById(Student *head, int targetId) { Student *p head-next; while (p ! NULL) { if (p-id targetId) { return p; // 找到直接返回节点指针 } p p-next; } return NULL; // 找不到返回 NULL } int listLength(Student *head) { int count 0; Student *p head-next; while (p ! NULL) { count; p p-next; } return count; }遍历的终止条件就一句话当 p 走到 NULL 时说明链表已经走完了。这句话听着简单但和循环链表的p head终止条件千万别搞混。另外请注意查找函数返回的是节点指针不是下标这点和数组返回下标索引很不一样。你在用返回的指针之前一定要判断是否为 NULL否则一旦目标不存在你对空指针取字段就直接崩溃了。链表查找的复杂度是 O(n)这就是链表最大的先天短板。如果业务里查找频率很高那你得认真想想是用哈希表还是跳表别硬扛着链表做查找。链表的主场永远是插入删除多、读取少的场景选型错误比代码写得烂更容易埋坑。3.3 插入操作核心一步是“先接后断”链表插入的代码网上到处都是但很多人照着抄还动不动就“断链”原因就是没理解“先接后断”这个原则。假设我们想在指定节点 p 后面插入一个新节点 newNode直觉上就是三步newNode 的 next 指向 p 的 next然后 p 的 next 指向 newNode。为什么顺序必须是这个void insertAfter(Student *p, int id, int score) { if (p NULL) return; Student *newNode (Student *)malloc(sizeof(Student)); if (newNode NULL) return; newNode-id id; newNode-score score; // 关键先让新节点指向 p 的后继 newNode-next p-next; // 再把 p 指向新节点 p-next newNode; }如果你先执行p-next newNode那么 p 原来的后继节点地址就丢了后面那半条链表跟整个链完全脱离关系这就叫断链。这就像你在一条锁链中间摘开一环去接新环新环的另一头没先挂住后面的链子结果后半条链子全掉地上了。所以口诀牢牢记住先接后断。写插入操作之前先在纸上画一下问自己“改了这行之后还有没有指针能访问到原来那个后继节点”如果答案是没有那顺序就是错了。对于在链表第 i 个位置插入的场景你需要先找到第 i-1 个节点让它作为 p再调用insertAfter。也就是说插入的核心复杂度在找前驱而不在改动指针那几步。很多教材把插入分成“带头节点版”和“不带头节点版”差异就集中在 p 是不是头节点上一旦用了头节点这个哨兵在头部插入也统一成了相同逻辑。3.4 删除操作与内存释放别忘了 free删除比插入更容易犯错误因为它牵扯到内存释放。我见过太多人写删除只把指针绕过去却忘了 free导致内存泄漏也见过 free 完之后又去访问已释放内存产生野指针和悬垂指针。void deleteNode(Student *head, int targetId) { Student *p head; Student *q; // 用于临时保存要删除的节点 // 从头节点开始找前驱注意 p 是前驱节点 while (p-next ! NULL) { if (p-next-id targetId) { q p-next; // 先保存待删节点 p-next q-next; // 让前驱跨过待删节点 free(q); // 释放内存 return; } p p-next; } printf(没找到该节点\n); }来逐行拆解。p从头节点开始检查p-next是不是目标因为要到目标节点的前一个节点才能修改它的 next 指针。找到之后先把待删节点地址存到q里这一步千万别省因为你把p-next改掉之后这个地址就再也拿不回来了。接着p-next q-next像是把这一段从链条上“摘下来”最后free(q)把内存还给系统。一个常见的疑问为什么删除一个节点非要找它的前驱因为单链表只有 next 指针单向行驶拿到某个节点自己你没法知道谁指向它。所以单链表删除的时间复杂度是 O(n)而双向链表删除拿到节点本身可以做到 O(1)因为有前驱指针直接指向前面那个节点。内存释放的问题多说一句在 C 语言里free只是释放内存但指针变量p里的地址值仍然残留着如果不把它置为 NULL下次不小心访问到就是悬垂指针。所以释放完我习惯顺手加上一句q NULL;。而在 Python、Java 这类带自动垃圾回收的语言里你不用担心这个它们帮你管了内存释放这也是很多人先学 Python 再学 C 会觉得 C 对内存要求严苛的原因。3.5 Python 版参考实现逻辑相同语法更轻松很多读者用 Python 学数据结构核心逻辑和 C 完全一样只是把 malloc/free 换成对象和垃圾回收。用类来表示节点是非常自然的映射。class ListNode: def __init__(self, val0, nextNone): self.val val # 数据域 self.next next # 指针域 def create_list(): # 这里直接返回一个头节点跟 C 语言带头节点思路一致 return ListNode() # 头节点不存实际数据val 默认为 0 def insert_at_tail(head, val): new_node ListNode(val) p head while p.next is not None: p p.next p.next new_node def print_list(head): p head.next while p is not None: print(p.val, end - ) p p.next print(None) def reverse_list(head): 单链表逆序经典三指针法 prev None curr head.next while curr is not None: next_node curr.next # 先保存下一个节点防止断链 curr.next prev # 反转当前节点的指针方向 prev curr # prev 移动到当前节点 curr next_node # curr 移动到下一个节点 head.next prev # 最后把头节点指向原链表的最后一个节点 head create_list() insert_at_tail(head, 1) insert_at_tail(head, 2) insert_at_tail(head, 3) print_list(head) # 1 - 2 - 3 - None reverse_list(head) print_list(head) # 3 - 2 - 1 - NonePython 单链表逆序是热词里的高频点也是面试最爱考的一道题。上面的三指针法把顺序说清楚prev指向前一个已反转好的节点curr指向当前要处理节点next_node先存住下一个节点防止断链。每次循环把curr.next指向prev然后三个指针整体向后移动一格。这个过程多画几遍图比死记代码有用得多。Python 这里因为节点是对象引用其实和 C 的指针是同一个概念。你唯一要特别注意的是head.next prev这一步因为不带头节点的版本里这行会直接让原链表的头指向新链表的头而带头节点的版本则必须保持在头节点后面接上反转结果千万别把头节点一起反转进去。我在教学的时候经常看到有人反转完发现遍历出来多了一个 0那就是把带头节点的哨兵也给转进去了。4. 常见坑汇总与调试经验4.1 空指针与野指针链表世界里的事故源头链表代码崩溃大多有一个共同作案人NULL。要么是访问了空指针要么是释放了之后继续用。以 C 语言为例最常见的场景是p-next访问前没有判断 p 本身是不是 NULL。你可以写一个防御性的习惯每次拿到一个外部传入的节点指针进入函数第一行就判断if (p NULL) return ...。养成习惯之后很多低级崩溃会被扼杀在摇篮里。野指针是另一类 P0 事故。我曾经在调试一个嵌入式项目时遇到板子跑一段时间就随机死机的问题。查来查去最后定位到问题出在删除一个节点后忘了把某个全局变量里保存的该节点地址清掉后续有其他模块通过这个残留地址访问已经被释放的内存读到的是被回收或者改写的垃圾数据。从那以后我给自己立了一个规矩free 之后立刻把指针置 NULL哪怕那个指针只是一个临时变量宁可多做一步也不要侥幸。如果你在调试链表程序时遇到莫名的崩溃第一件事就是检查有没有访问已释放内存的行为。用 Valgrind 跑一下能直接告诉你非法访问的堆地址这个工具我用得非常频繁强烈推荐。4.2 断链与死循环两个最隐蔽的敌人还有两个问题特别容易在代码没错表面、但一跑结果就怪的情况下出现。第一个是断链前面讲插入时已经说了“先接后断”的原则但你也要学会自己排查。比如链表中途少了一段数据遍历到某个位置就停住了你就要画图看那一步操作是不是把某个节点的 next 覆盖了导致后面一部分彻底失去入口。断链和内存泄漏不一样它不编译报错不运行崩溃就是你的数据悄悄变少了。第二个是死循环常见于循环链表和带头节点版本写混的时候。你明明建的是循环链表遍历循环条件却用了while (p ! NULL)那它永远走不到 NULLp 沿着环一直转圈子程序就像卡死了一样。排查办法是额外限制一个步数比如最多循环链长加 10 次一旦超出就说明退出条件有问题。我曾经用过一个土办法在 for 循环里加一个计数变量当计数超过 1000 就打印当前指针地址能很快看出是不是在绕圈。另外有些人在合并两个有序链表时也容易进死循环。合并的思路是拿两个指针分别指向两条链每次把值小的那个接过去但如果你忘了在接完之后把对应指针往后移动一位那它每次都会比较同一个节点永远接不完。代码写完一定要在移动指针那几行检查三遍。4.3 内存泄漏跑久了才显现的慢性病内存泄漏不是很激烈的 bug它特别隐蔽程序跑几十分钟都不一定出问题但跑久了内存越吃越多最后系统慢到没法用。在嵌入式环境或者长时间运行的服务器进程里这是致命问题。链表相关的内存泄漏主要来自三处删除节点时漏了 free、链表整个销毁时没有逐个节点释放、以及异常分支里提前 return 忘了释放临时申请的内存。void destroyList(Student *head) { Student *p head; Student *tmp; while (p ! NULL) { tmp p; p p-next; free(tmp); } }注意销毁整条链的时候先用tmp保存当前节点然后让p指向下一个节点最后才 freetmp。这个顺序反过来的话你 free 了当前节点再去访问它的 next就是野指针访问。如果你在用 Python虽然垃圾回收会帮你兜底但循环引用比如循环链表可能让引用计数失效大规模数据时可以考虑用gc模块手动回收。要说我自己的调试方法论核心就一条画图代替脑内推演。链表题不画图纯靠背代码就像看地图不记路还要不迷路一样不现实。我提供一个具体的自查模板每一步操作后问自己三个问题——哪些节点的 next 发生了改变哪些节点的地址现在没人指向了我需要不需要释放它把这三个问题答清楚链表题基本不可能错。4.4 考研、面试和竞赛中的链表经典变形题聊到链表有个绕不开的场景就是考试和面试。数据结构是计算机专业考研的专业课重点链表在里面出镜率极高。我结合一些常见真题和面试题视角整理几个高频变体说说思路和解法。合并两个有序单链表。这是 LeetCode 第 21 题的经典原题也是数据结构教材里必有的实验题。思路是用一个哑节点dummy node相当于我们前面说的头节点的角色作为结果链表的起点然后两个指针分别指向两个链表头部每次比较两个当前节点的值把较小者接到哑节点后面然后移动对应的那个指针。某一方走完以后把另一方剩余的所有节点直接接上。注意这里优选用哑节点而不是直接操作 head因为哑节点能让你不用单独处理第一个节点该由谁当头的问题。判断链表是否有环。经典解法是快慢指针一个指针每次走两步一个指针每次走一步。如果链表有环快指针最终一定会遇到慢指针如果没环快指针会率先遇到 NULL。这个方法的妙处在于它不需要额外空间时间复杂度 O(n)。我第一次见这个做法时觉得很玄学但后来自己证明过一遍就明白了相当于两个人在环形跑道上跑步速度快的那个人迟早会从后面套圈追上速度慢的。链表中倒数第 K 个节点。面试官也爱考。思路是先用一个快指针先走 K 步然后让慢指针从头出发快慢一起走。等快指针走到 NULL 时慢指针正好指向倒数第 K 个节点。它是快慢指针思想的另一个应用比先遍历一遍获得长度再去定位稍微聪明一点也更能体现你对指针操作的理解。反转链表的递归写法。前面我给了迭代版的三指针法但面试里还经常让手写递归版。递归的核心思路是假设reverseList(head.next)已经帮你把后面那条链反转好了现在只需要把 head 这个节点的 next 指向空并让原来 head.next 节点的 next 指向 head。听起来很简单但你一定要想清楚递归的返回值和边界条件否则很容易在终止条件上卡住。每 K 个节点一组反转链表这个是升级版需要分三段思路先遍历 K 个节点确认这组足够长不够就直接返回够的话反转这一小组再递归处理下一组。写这个题时最容易出 bug 的地方是小组内部的边界拼接建议画图把 prev、tail、next_group 这几个指针标清楚再动笔。这些题考的本质都不是你能不能背下代码而是你有没有理解指针修改的语义、边界条件怎么处理、复杂度是多少。面试官真正想从链表题里看到的是你的工程思维——在有限条件下怎么设计最稳定的方案。5. 关于“链表1”这个系列接下来可以怎么走我这次把单链表这个最基础的形态讲透了包括它的结构原理、选型思路、C 与 Python 两种实现、常见 bug 和变形题。其实链表这一块内容是一个完整的地图接下来你可以顺着这条线继续往下走双向链表的插入删除具体怎么写循环链表在约瑟夫环问题里怎么用链表的排序尤其是归并排序为什么比数组更自然LRU 缓存用双向链表加哈希表是怎么组合的还有更进阶的跳表它用链表加多级索引把查找复杂度优化成了 O(log n)这可能是链表最惊艳的进化形态了。我当年学数据结构最深的感受是链表不是靠背代码学会的是靠画图学会的。你每写一个操作先在纸上画出调整前后的节点指向图对着图一行一行核对自己的代码练上五六个操作之后你会发现自己突然能看懂很多以前天书一样的代码了。我个人建议你看完这篇之后动手做两件事第一用 C 语言实现一个带头节点的单链表把增删改查全部写完并跑通第二在 LeetCode 上找链表分类下的简单题刷 10 道左右感受一下实际应用的考法。等这两步走完你在链表这个领域的基本功就真的扎实了咱们再聊后面更复杂的结构也会轻松很多。
阅读完成 · 觉得有帮助？
