学数据结构几乎每个人都会在“线性表的链式表示和实现”这一章卡一段时间。顺序表数组那部分理解起来轻松无非是连续内存、下标访问、插入删除要移动元素。但链表一登场头结点、尾指针、二级指针、断链、内存泄漏这些概念一股脑涌过来不亲手写代码是真的消化不了。这篇文章就把链表这一章摊开讲清楚它在解决什么问题单链表的核心操作怎么一步步实现有哪些反直觉的坑以及上机调试时最常见的报错怎么处理。适合正在学数据结构的学生、准备考研408的读者、或者工作后回来补基础的朋友。我不会堆理论知识全部按实际写代码时会遇到的情况来讲C语言为主后面也简单提一下其它语言怎么对应。看完之后你可以照着思路把单链表、双链表、循环链表都写一遍。1. 线性表与链式存储先搞清楚我们到底在解决什么问题1.1 顺序表的两个痛点移动元素与连续空间线性表是数据结构里最基础的结构之一逻辑上就是一组数据元素排成一条线。实现线性表有两种方式顺序存储和链式存储。顺序存储就是我们熟悉的数组逻辑相邻的元素在物理内存里也是紧挨着的。这种紧挨着的存储方式带来一个问题插入或删除元素时为了保持“紧挨着”这个特性后面的元素全部得跟着移动。比如一个数组里有1000个元素要在第2个位置插入一个新元素那么从第2个到第1000个整整999个元素都要向后挪一位。删除也是同理后面的元素要往前补位。这一挪时间复杂度就是O(n)。更让人头疼的是数组需要一块连续的内存空间。不管是用静态数组还是动态扩容的方式你都得提前规划好“这一整块连续空间在哪”。如果内存碎片化严重明明总剩余空间够大却找不到一块足够大的连续区域来存放数组就创建不出来。这两大痛点就是链表登场的最直接理由。1.2 链表的核心思想用指针把离散内存串起来链表采用了另一种思路每个元素不需要挨在一起了每个节点单独存放在任意位置节点里额外存一个指针指向下一个节点的地址。逻辑上相邻的元素物理上可能隔着十万八千里但通过指针一层一层指过去依然能维持一条完整的线性关系。打个比方顺序表就像电影院里连排的座位先买了票大家都按号坐在一起中途有人要换进来整排人都得挪一挪。链表就像朋友之间互相介绍认识你认识一个朋友他再把他认识的朋友介绍给你以此类推——每个人都不需要住在一起但通过社交关系就能把一整条链串起来。这个设计带来的直接好处有两个第一插入和删除节点时只需要修改指针的指向不需要移动其它任何数据时间复杂度降为O(1)第二节点可以分散存储在内存的任意位置不存在“必须找到一整块连续空间”的限制。代价则是失去了随机访问能力。想找第i个元素必须从头结点开始一个节点一个节点往后走时间复杂度O(n)每个节点还额外多出一个指针域的内存开销。把顺序表和链表的核心差异整理成一张表会更直观对比维度顺序表数组链表内存空间需要连续空间离散空间靠指针连接插入/删除平均O(n)需移动元素O(1)只需修改指针随机访问O(1)下标直达O(n)需遍历空间开销只有数据本身每个节点多存一个指针扩容方式需要搬迁扩容动态分配节点天然可扩展所以选哪种结构核心取决于你的业务更看重什么频繁按位置访问顺序表更香频繁插入删除链表更合适。这也是面试里经常被问到的“数组和链表有什么区别”的标准答案。1.3 带头结点与不带头结点一个节点引发的差异链表刚上手时最容易绕晕的问题就是到底要不要头结点很多教材默认带头结点但也有的题目明确说“不带头结点的单链表”两者实现起来差别不小。头结点是在链表第一个元素节点也叫首元结点之前附加的一个节点它的数据域可以什么都不存或者存链表长度等信息指针域指向首元结点。头结点本身不是数据元素引入它纯粹是为了操作方便。为什么要多此一举因为如果不带头结点插入删除第一个元素时链表的头指针本身要发生改变。比如在空链表里插入第一个节点或者在头部插入节点你需要修改头指针指向新节点。于是函数里不得不传二级指针或者用返回值把新头指针传出去逻辑上要分“空表”、“非空表头部操作”、“中间操作”三种情况讨论代码写起来非常啰嗦。带头结点之后所有情况都变得统一了头结点永远存在头指针永远指向头结点不会变插入删除操作永远在某个节点之后进行处理逻辑完全一致。这相当于用一个小小的空节点换取了代码逻辑的大幅度简化。严蔚敏版数据结构教材和考研408的链表题目基本都是带头结点的写法。不带结点的情况常见于一些自定义的简化题目里考查你对边界条件的理解有多深后面第3章我会专门讲差异。2. 单链表基本操作解析从定义到创建的核心代码2.1 结构体定义数据类型与指针类型的设计用C语言实现链表第一步就是定义节点结构体。每个节点需要两部分数据域存实际数据指针域存下一个节点的地址。typedef int ElemType; // 数据域类型这里以int为例可换成结构体等 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList;这段代码里有几个细节值得展开。struct LNode后面带了一个*next为什么这里不能直接写LNode *next因为typedef是在结构体定义完之后才生效的在结构体内部引用自身指针时结构体还没定义完编译器还不认识LNode这个类型名所以必须用完整的struct LNode *。这是很多初学者第一次编译报错的高发点。关于LNode和*LinkList这两个名字我建议这样理解LNode表示“这是一个节点”主要用于定义节点变量LinkList表示“这是一个链表”本质是节点指针用于代表整条链表的头。习惯上声明单个节点用LNode *p声明链表用LinkList L。两者其实是同一个类型但语义不同写代码时能帮助自己和读代码的人区分角色这也是教材里约定俗成的风格。2.2 初始化链表为什么这里要二级指针带头结点的链表初始化操作很明确造一个头结点让头指针指向它头结点的next先置空。bool InitList(LinkList *L) { *L (LinkList)malloc(sizeof(LNode)); if (*L NULL) { return false; // 内存分配失败 } (*L)-next NULL; return true; }注意我用的是LinkList *L也就是二级指针。在C语言里想在一个函数内改外部变量的值就必须传外部变量的地址。L是外部定义的一个链表头指针如果在函数里直接写L malloc(...)那只是修改了形参的副本函数结束副本销毁外部的L依然是NULL或者原来的垃圾值。这就是C语言经典的值传递陷阱。很多初学者不理解这一步常在初始化链表时写出了“感觉没错但链表一直是空的”的诡异bug。解决办法要么像上面这样传二级指针要么让函数返回新建的头指针LinkList InitList() { ... return L; }。大学作业里两个写法都能过但工程上更推荐前者因为C语言函数只能有一个返回值以后你还需要用它返回其它结果。初始化之后别忘了链表的基本美德用完释放内存。销毁链表时要从头遍历依次free每个节点的内存最后把头指针置空避免野指针。这部分代码放在本章稍后讲遍历时一起给。2.3 头插法与尾插法两种建表思路与逆序陷阱建立链表有两种最常见的方式头插法和尾插法。两种方法在考试里都是高频题但它们的产物完全不同。头插法顾名思义每次新节点都插入到头结点之后成为第一个元素节点。逻辑是新节点的next指向当前首元结点然后头结点的next指向新节点。void CreateListHead(LinkList L, ElemType arr[], int n) { // L已初始化带头结点 LNode *s; for (int i 0; i n; i) { s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; s-next L-next; // 新节点指向原来的首元结点 L-next s; // 头结点指向新节点 } }这份代码有个很容易忽略的事实如果依次将arr[0]到arr[n-1]插入最终链表的顺序是arr[n-1]到arr[0]完全颠倒。因为后来者总是插到最前面。所以面试题“给你一个链表如何逆序”最简单的一种答案就是遍历原链表用头插法建一个新链表输出即可。头插法本身的机制天然实现了逆序。尾插法就不会逆序但需要多维护一个尾指针每插入一个新节点都需要把它接在尾部更新尾指针。void CreateListTail(LinkList L, ElemType arr[], int n) { LNode *s, *tail L; // tail始终指向尾节点 for (int i 0; i n; i) { s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; tail-next s; // 接在尾部 tail s; // 更新尾部指针 } }用哪个方法取决于需求日常构建一条“保持原始输入顺序”的链表用尾插法如果题目让你逆序构建或者你需要翻转链表且不希望额外开空间考虑头插法。头插法还有一个隐藏的坑新节点分配后如果忘记把s-next赋值就接上链表链表会直接乱套后面遍历时表现为打印出随机地址甚至崩溃。所以malloc后第一件事就是把next置好。2.4 遍历链表与求表长循环条件的选择遍历几乎是最基础的操作但遍历的条件写法往往暴露你对链表结构的理解深度。bool GetLength(LinkList L, int *len) { if (L NULL) { return false; } int count 0; LNode *p L-next; // 指向首元结点 while (p ! NULL) { count; p p-next; } *len count; return true; } void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }关键在于p L-next是让p指向第一个真正的数据节点而头结点本身不参与遍历。如果犯糊涂直接让p L那么链表的长度会比正确值多1打印时还会多输出一个垃圾数据头结点的data是没有初始化的随机值。循环条件的p ! NULL表示“p指向的节点存在”一旦遍历到尾节点它的next为NULL下一个循环自然退出。有人喜欢写while (p-next ! NULL)这会导致最后一个节点没有被处理到两个条件差一个节点写代码时一定要想清楚自己是想在“当前节点”还是“当前节点的下一个节点”做操作。3. 插入与删除的实操细节指针操作的顺序与边界检查3.1 按位置插入为什么循环到i-1而不是i按位插入是最经典的操作要求在第i个位置从1开始计数插入新节点。实现的关键是找到第i-1个节点。道理很直接链表的插入本质上就是“在某个已有节点之后链接一个新节点”你必须先找到这个“前驱节点”。bool InsertList(LinkList L, int i, ElemType e) { if (i 1) { return false; // 位置非法 } LNode *p L; // p从头结点开始走 int j 0; // p当前在第几个节点头结点记为第0个 while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { return false; // i超过了链表长度1 } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next p-next; // 1. 新节点先连向原后继 p-next s; // 2. 前驱节点再指向新节点 return true; }这里的两个步骤顺序绝不能反。必须先让s-next指向p的后继再让p-next指向s。一旦先执行p-next s原后继节点的地址就被覆盖丢失了s就再也接不上后面的节点链表从此断成两截。一句话先接上新节点的后路再动前驱的指针。循环条件p ! NULL是边界检查的关键。假设链表有5个节点想插到第7个位置p在向后移动的过程中会走到NULL循环必须终止并返回失败。如果省略这个条件代码会在p等于NULL时仍然执行p-next s直接对空指针解引用程序崩溃。所有涉及遍历的链表操作都有这个共性访问p-next之前必须先保证p不是NULL。3.2 按位置删除释放内存与置空next删除操作同样需要找到前驱节点然后让前驱跨过被删除节点直接指向它的后继。找到被删除节点后需要释放它的内存。bool DeleteList(LinkList L, int i, ElemType *e) { if (i 1) { return false; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL || p-next NULL) { return false; // p已经到尾后面没有可删节点 } LNode *q p-next; // q是要删除的节点 p-next q-next; // 前驱直接连向后继 *e q-data; // 把删除节点的值带回给调用者 q-next NULL; // 断开防止置垃圾数据 free(q); // 释放内存 return true; }我这里比课本稍多了一步在free之前把q-next置为NULL。虽然free之后这块内存就不能再访问但置空是一个好习惯能避免调试器中看到一个指向已释放内存的野指针排查问题时会省很多时间。删除最后一个节点时q-next本来就是NULL无妨逻辑统一。释放后很多人会忘记用返回值把删除的数据带出来。教材里DELETE函数的参数带了一个ElemType *e就是用来返回被删元素的。面试中如果题目要求“删除链表中值为x的所有节点”返回值还常用来统计删除了几个。3.3 按值查找与按位置访问循环边界差异按值查找和按值定位是链表最常用的查询操作。按值查找的逻辑很直白从头结点后面的首元结点开始依次比较每个节点的数据域找到就返回该节点的指针找不到返回NULL。LNode *LocateElem(LinkList L, ElemType e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; // 找到返回node指针找不到返回NULL }这里有两种写法一种像我这样把“p不为空且data不等于目标”作为循环条件退出时p要么是目标节点要么是NULL另一种写法是先判断p是否为空再判断data。两种都对但第二种种法的代码会多一层嵌套可读性差一些。我习惯前者因为退出循环时语义非常清晰。按位置访问取第i个元素则需要注意循环从第1个节点开始走i-1步才能到第i个。一种常见的思路是把j初始化为0、p指向头结点然后循环j i让p从头往下走i次。但这样有个细节如果i大于链表长度最后一次循环p已经是NULL再访问p-data又会崩溃所以要先判断。核心要点是定位某位置时永远要问自己“循环结束时p到底停在哪”考场上你画个链表图把p的走向一步步画出来比空想靠谱得多。3.4 不带头结点的链表插入删除需要改变头指针前面说带头结点的好处是简化操作那如果不带头结点会怎样在“指定位置建立单链表”这类题目里不带头结点的写法同样会出现。bool InsertWithoutHead(LNode **L, int i, ElemType e) { if (i 1) { return false; } if (i 1) { // 在头部插入头指针本身要变 LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; s-next *L; *L s; return true; } LNode *p *L; int j 1; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { return false; } LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; s-next p-next; p-next s; return true; }可以看到关键区别插入第1个位置时头指针必须更新所以整个函数不得不接收二级指针LNode **L。操作时不带头结点还有一个隐患如果链表为空p *L后p就是NULL走到删除或插入分支前要做好空表判断。不带头结点的代码在头部操作这个分支上比带头结点多了将近一半的判断这也是为什么实际工程普遍带头结点的原因。但如果考试或作业里明确要求不带头结点你就得老老实实把i1这个边界独立处理任何想靠统一逻辑蒙混过关的写法都会在头部出问题。4. 双链表与循环链表结构升级与代码差异分析4.1 双链表结构多一个指针多一倍的指针修改量单链表只能从前往后走找前驱节点必须从头开始重新遍历。双链表就是在节点里多存一个prior指针指向前驱节点这样既能往后走也能往前走。适用场景很清晰频繁需要“回退”或“删除指定节点的前驱”的操作用双链表可以避免O(n)的重新查找。typedef struct DNode { ElemType data; struct DNode *prior, *next; } DNode, *DLinkList;双链表插入时要修改四个指针顺序非常讲究。以在节点p之后插入新节点s为例s-next p-next; // 1. 新节点连向p的后继 s-prior p; // 2. 新节点的前驱指向p if (p-next ! NULL) { p-next-prior s; // 3. 原后继的前驱改为s要判空 } p-next s; // 4. p的后继改为s注意第3步的判空如果p本来就是尾节点p-next为NULL此时p-next-prior s就是对空指针解引用直接崩溃。单链表插入没有这个问题因为它的修改方向是单向的。这个区别就是“多一个指针多一倍的边界检查”。双链表删除节点s本身的操作比单链表更干净因为可以通过s-prior找到前驱不需要遍历s-prior-next s-next; if (s-next ! NULL) { s-next-prior s-prior; } free(s);同样是边界检查删的是尾节点时s-next为NULL就不用处理后继的prior。总之双链表操作的代码框架跟单链表很像但每一个指针操作都要问一句“这个指针如果是NULL怎么办”4.2 循环链表终止条件从NULL变为头指针循环链表让尾节点的next不再指向NULL而是指向头结点或链表第一个节点整条链首尾相接。循环链表的核心区别在于遍历终止条件单链表判断p ! NULL循环链表判断p ! L。以带头结点的循环单链表为例遍历终止条件变为LNode *p L-next; while (p ! L) { // p回到头结点说明走完一圈 printf(%d , p-data); p p-next; }循环链表的好处之一是某些场景更自然比如约瑟夫环问题中每轮删除一个人后要继续从下一个人开始数数如果链不是循环的数完之后要跳回开头逻辑很不自然。另一个好处是带尾指针的循环链表在尾部插入节点的复杂度降为O(1)不需要从头遍历找尾节点。空表判断也要跟着变带头结点的循环链表判空条件是L-next L。有的教材把尾指针作为整个链表的入口这种情况下判空条件变成L NULL插入第一个节点时还要特殊处理。这些细节在考试中很容易混淆用一个办法就能彻底理清拿到任何链表题先画图把空表、单节点表、正常表三种形态都画出来判空条件一目了然。4.3 链表逆序与排序高频面试题的两种解法逆序链表是面试题中的常客。常见做法有两种三指针法和头插重建法。三指针法维护prev、curr、next三个指针依次把curr-next反向指向prev然后整体后移直到遍历完成。核心代码如下LNode *ReverseList(LNode *head) { LNode *prev NULL, *curr head, *next NULL; while (curr ! NULL) { next curr-next; // 先保存后继防止断链 curr-next prev; // 反转当前节点指针 prev curr; // 整体推进 curr next; } return prev; // 新头就是原链表的尾节点 }注意这里函数返回的是新的头指针。因为你翻转整条链表后原来的头结点变成了尾节点新的头必须是原来的尾节点所以必须把新头返回给调用者。不带头结点时这一点格外重要千万不能继续沿用旧的头指针。另一种思路是遍历原链表用头插法重建一条新链表相当于“逆向复制”需要额外空间。两种方法各有优点三指针法原地完成空间O(1)最优头插重建法代码短好理解但需要新链表空间。链表排序在考研和笔试题里也很常见尤其是“对链表进行插入排序”和“合并两条有序链表”。链表不能随机访问快排的partition不好做冒泡排序虽然能实现但O(n²)不划算最适合链表的是归并排序因为归并只需要修改指针而不需要移动元素。核心思路就是递归地把链表从中间分成两部分分别排序后合并。找中间节点的方法也很经典快慢指针快指针每次走两步慢指针每次走一步快指针到尾部时慢指针正好在中点。5. 常见问题与调试经验上机最容易踩的坑5.1 高频Bug速查表现象、原因与解法链表代码的调试很多时候比的不是你逻辑有多强而是你能多快地把常见错误“认出来”。我整理了一份高频Bug速查表基本覆盖了刚学链表时会遇到的大部分问题。问题现象可能原因排查建议打印链表时出现随机大数字没有对节点数据域初始化就使用检查所有malloc后是否给成员都赋了值打印到中间就Segmentation Fault链表断链重点检查插入操作中赋值顺序s-next和p-next是否搞反遍历时少打印最后一个节点循环条件误用p-next ! NULL问自己p指向的当前节点要不要处理插入到第1个位置失败不带头结点时没有更新头指针检查是否用了二级指针头部插入需单独处理删除后再次遍历崩溃被删节点的next没有置NULL或野指针删除后把next置NULL再把指针置NULL链表现在多了一个节点初始化时把p L而不是L-next检查遍历的起点是不是跳过了头结点free之后程序立刻崩溃可能free了栈上的变量或已经free过的指针确认free的对象是malloc返回的堆指针插入位置非常大时不报错缺少循环中的p ! NULL边界判断补上p ! NULL防止p走到NULL后还解引用这张表的核心价值在于把错误和“对应节点图景”联系起来。每遇到一个bug先在纸上画一画当前链表的实际形态再从表里找对应的可能原因通常比盯着代码发呆有效得多。5.2 我调试链表的习惯性动作画图与打印辅助链表调试最有效的工具不是调试器里的变量窗口而是纸和笔。我的习惯是遇到链表逻辑错误先画一个横向的方框链把每个节点的地址、数据、next指向用箭头标出来然后把代码里每一步操作对箭头的修改也标出来跟真实链表对比断链的位置基本一眼就能看出来。单步调试也很管用。在IDE里给核心操作比如插入中的p-next s打断点看每一步执行前和执行后p、s、s-next各自指向什么地址。你很快会发现很多“意料之外”的情况其实是自己脑补错了链表的形态。还有一个朴素的习惯在关键函数里临时加打印语句打印每个节点的data和地址。比如遍历时打印printf(addr%p data%d next%p\n, p, p-data, p-next)一条链表到底长什么样一眼明了。调试完成后把打印删掉或者在代码里加一个#ifdef DEBUG开关平时不输出调试时打开既方便又不影响发布的代码可读性。5.3 不同语言实现链表时的对应关系很多读者学的第一语言不是C在Java、Python、C里写链表感觉有点对不上号。其实核心概念完全一致只是语法表达不同。C语言里用结构体和指针实现链表节点是一个结构体指针保存下一个节点的地址。Java/Python里用类和对象引用实现链表节点是一个类类的成员变量指向下一个节点对象。Java没有“指针”这个概念但对象的引用本质上就是受管控的指针。Python里更直接任何变量都是对象的引用所以定义一个节点类next成员指向另一个节点对象就构成了链表。class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextC里可以用结构体或类也可以用STL的list容器本身就是双向链表但面试手写链表时C的写法和C几乎一样唯一的区别是不再用malloc/free而是用new/delete。C和C混写时最经典的错误就是用malloc分配的内存用delete释放或者用new分配用free释放。这两种不匹配在绝大多数编译器上不会立即报错但会在运行到某个临界点的时候神秘崩溃。还有一个区别要注意C语言需要手动管理内存最后必须freeJava/Python有垃圾回收不手动释放也不会内存泄漏严重。但Java/Python里如果忘了把被删节点的next置空那个节点仍然被自己的next字段引用垃圾回收器就无法判断它是否可回收这同样会造成内存泄漏。所以“释放”在不同语言里的具体动作不一样但“孤儿引用”的危害是一致的。5.4 实用技巧转义字符与编辑器配置小记在调试链表时为了方便打印链表的每个节点我经常在printf里用%p打印指针地址配合\n换行输出一行多个节点信息。比如printf([%p | %d] - , p, p-data);这样输出的内容可以直观地映射成链表形态。调试时建议在编辑器里开启“显示空白字符”的功能能避免某些看不见的空格或制表符导致格式判断失误。虽然这跟链表关系不大但实际调试中很多输出对不上的问题其实来自打印语句本身被环境干扰了。这些技巧听起来很琐碎但真正写链表时就是这些琐碎细节决定了你能不能在半小时内定位到一个隐蔽的断链错误。写链表代码我个人的体会是它不考验智商考验的是你有没有把每一步指针操作对应到脑子里那幅链表的图景。把带头结点、不带头结点、循环链表、双链表都亲手写一遍并且在纸上画出每一步的指向变化这一章就算真正过关了。之后无论是做算法题、准备考研408还是工作中写LRU缓存、管理内存块链表这套思维都会反复出现。如果这篇文章里有任何一个坑让你避开了一次debug的煎熬就算没白读。
数据结构链表详解：头结点、指针操作与C语言实现全解析
学数据结构几乎每个人都会在“线性表的链式表示和实现”这一章卡一段时间。顺序表数组那部分理解起来轻松无非是连续内存、下标访问、插入删除要移动元素。但链表一登场头结点、尾指针、二级指针、断链、内存泄漏这些概念一股脑涌过来不亲手写代码是真的消化不了。这篇文章就把链表这一章摊开讲清楚它在解决什么问题单链表的核心操作怎么一步步实现有哪些反直觉的坑以及上机调试时最常见的报错怎么处理。适合正在学数据结构的学生、准备考研408的读者、或者工作后回来补基础的朋友。我不会堆理论知识全部按实际写代码时会遇到的情况来讲C语言为主后面也简单提一下其它语言怎么对应。看完之后你可以照着思路把单链表、双链表、循环链表都写一遍。1. 线性表与链式存储先搞清楚我们到底在解决什么问题1.1 顺序表的两个痛点移动元素与连续空间线性表是数据结构里最基础的结构之一逻辑上就是一组数据元素排成一条线。实现线性表有两种方式顺序存储和链式存储。顺序存储就是我们熟悉的数组逻辑相邻的元素在物理内存里也是紧挨着的。这种紧挨着的存储方式带来一个问题插入或删除元素时为了保持“紧挨着”这个特性后面的元素全部得跟着移动。比如一个数组里有1000个元素要在第2个位置插入一个新元素那么从第2个到第1000个整整999个元素都要向后挪一位。删除也是同理后面的元素要往前补位。这一挪时间复杂度就是O(n)。更让人头疼的是数组需要一块连续的内存空间。不管是用静态数组还是动态扩容的方式你都得提前规划好“这一整块连续空间在哪”。如果内存碎片化严重明明总剩余空间够大却找不到一块足够大的连续区域来存放数组就创建不出来。这两大痛点就是链表登场的最直接理由。1.2 链表的核心思想用指针把离散内存串起来链表采用了另一种思路每个元素不需要挨在一起了每个节点单独存放在任意位置节点里额外存一个指针指向下一个节点的地址。逻辑上相邻的元素物理上可能隔着十万八千里但通过指针一层一层指过去依然能维持一条完整的线性关系。打个比方顺序表就像电影院里连排的座位先买了票大家都按号坐在一起中途有人要换进来整排人都得挪一挪。链表就像朋友之间互相介绍认识你认识一个朋友他再把他认识的朋友介绍给你以此类推——每个人都不需要住在一起但通过社交关系就能把一整条链串起来。这个设计带来的直接好处有两个第一插入和删除节点时只需要修改指针的指向不需要移动其它任何数据时间复杂度降为O(1)第二节点可以分散存储在内存的任意位置不存在“必须找到一整块连续空间”的限制。代价则是失去了随机访问能力。想找第i个元素必须从头结点开始一个节点一个节点往后走时间复杂度O(n)每个节点还额外多出一个指针域的内存开销。把顺序表和链表的核心差异整理成一张表会更直观对比维度顺序表数组链表内存空间需要连续空间离散空间靠指针连接插入/删除平均O(n)需移动元素O(1)只需修改指针随机访问O(1)下标直达O(n)需遍历空间开销只有数据本身每个节点多存一个指针扩容方式需要搬迁扩容动态分配节点天然可扩展所以选哪种结构核心取决于你的业务更看重什么频繁按位置访问顺序表更香频繁插入删除链表更合适。这也是面试里经常被问到的“数组和链表有什么区别”的标准答案。1.3 带头结点与不带头结点一个节点引发的差异链表刚上手时最容易绕晕的问题就是到底要不要头结点很多教材默认带头结点但也有的题目明确说“不带头结点的单链表”两者实现起来差别不小。头结点是在链表第一个元素节点也叫首元结点之前附加的一个节点它的数据域可以什么都不存或者存链表长度等信息指针域指向首元结点。头结点本身不是数据元素引入它纯粹是为了操作方便。为什么要多此一举因为如果不带头结点插入删除第一个元素时链表的头指针本身要发生改变。比如在空链表里插入第一个节点或者在头部插入节点你需要修改头指针指向新节点。于是函数里不得不传二级指针或者用返回值把新头指针传出去逻辑上要分“空表”、“非空表头部操作”、“中间操作”三种情况讨论代码写起来非常啰嗦。带头结点之后所有情况都变得统一了头结点永远存在头指针永远指向头结点不会变插入删除操作永远在某个节点之后进行处理逻辑完全一致。这相当于用一个小小的空节点换取了代码逻辑的大幅度简化。严蔚敏版数据结构教材和考研408的链表题目基本都是带头结点的写法。不带结点的情况常见于一些自定义的简化题目里考查你对边界条件的理解有多深后面第3章我会专门讲差异。2. 单链表基本操作解析从定义到创建的核心代码2.1 结构体定义数据类型与指针类型的设计用C语言实现链表第一步就是定义节点结构体。每个节点需要两部分数据域存实际数据指针域存下一个节点的地址。typedef int ElemType; // 数据域类型这里以int为例可换成结构体等 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList;这段代码里有几个细节值得展开。struct LNode后面带了一个*next为什么这里不能直接写LNode *next因为typedef是在结构体定义完之后才生效的在结构体内部引用自身指针时结构体还没定义完编译器还不认识LNode这个类型名所以必须用完整的struct LNode *。这是很多初学者第一次编译报错的高发点。关于LNode和*LinkList这两个名字我建议这样理解LNode表示“这是一个节点”主要用于定义节点变量LinkList表示“这是一个链表”本质是节点指针用于代表整条链表的头。习惯上声明单个节点用LNode *p声明链表用LinkList L。两者其实是同一个类型但语义不同写代码时能帮助自己和读代码的人区分角色这也是教材里约定俗成的风格。2.2 初始化链表为什么这里要二级指针带头结点的链表初始化操作很明确造一个头结点让头指针指向它头结点的next先置空。bool InitList(LinkList *L) { *L (LinkList)malloc(sizeof(LNode)); if (*L NULL) { return false; // 内存分配失败 } (*L)-next NULL; return true; }注意我用的是LinkList *L也就是二级指针。在C语言里想在一个函数内改外部变量的值就必须传外部变量的地址。L是外部定义的一个链表头指针如果在函数里直接写L malloc(...)那只是修改了形参的副本函数结束副本销毁外部的L依然是NULL或者原来的垃圾值。这就是C语言经典的值传递陷阱。很多初学者不理解这一步常在初始化链表时写出了“感觉没错但链表一直是空的”的诡异bug。解决办法要么像上面这样传二级指针要么让函数返回新建的头指针LinkList InitList() { ... return L; }。大学作业里两个写法都能过但工程上更推荐前者因为C语言函数只能有一个返回值以后你还需要用它返回其它结果。初始化之后别忘了链表的基本美德用完释放内存。销毁链表时要从头遍历依次free每个节点的内存最后把头指针置空避免野指针。这部分代码放在本章稍后讲遍历时一起给。2.3 头插法与尾插法两种建表思路与逆序陷阱建立链表有两种最常见的方式头插法和尾插法。两种方法在考试里都是高频题但它们的产物完全不同。头插法顾名思义每次新节点都插入到头结点之后成为第一个元素节点。逻辑是新节点的next指向当前首元结点然后头结点的next指向新节点。void CreateListHead(LinkList L, ElemType arr[], int n) { // L已初始化带头结点 LNode *s; for (int i 0; i n; i) { s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; s-next L-next; // 新节点指向原来的首元结点 L-next s; // 头结点指向新节点 } }这份代码有个很容易忽略的事实如果依次将arr[0]到arr[n-1]插入最终链表的顺序是arr[n-1]到arr[0]完全颠倒。因为后来者总是插到最前面。所以面试题“给你一个链表如何逆序”最简单的一种答案就是遍历原链表用头插法建一个新链表输出即可。头插法本身的机制天然实现了逆序。尾插法就不会逆序但需要多维护一个尾指针每插入一个新节点都需要把它接在尾部更新尾指针。void CreateListTail(LinkList L, ElemType arr[], int n) { LNode *s, *tail L; // tail始终指向尾节点 for (int i 0; i n; i) { s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; tail-next s; // 接在尾部 tail s; // 更新尾部指针 } }用哪个方法取决于需求日常构建一条“保持原始输入顺序”的链表用尾插法如果题目让你逆序构建或者你需要翻转链表且不希望额外开空间考虑头插法。头插法还有一个隐藏的坑新节点分配后如果忘记把s-next赋值就接上链表链表会直接乱套后面遍历时表现为打印出随机地址甚至崩溃。所以malloc后第一件事就是把next置好。2.4 遍历链表与求表长循环条件的选择遍历几乎是最基础的操作但遍历的条件写法往往暴露你对链表结构的理解深度。bool GetLength(LinkList L, int *len) { if (L NULL) { return false; } int count 0; LNode *p L-next; // 指向首元结点 while (p ! NULL) { count; p p-next; } *len count; return true; } void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }关键在于p L-next是让p指向第一个真正的数据节点而头结点本身不参与遍历。如果犯糊涂直接让p L那么链表的长度会比正确值多1打印时还会多输出一个垃圾数据头结点的data是没有初始化的随机值。循环条件的p ! NULL表示“p指向的节点存在”一旦遍历到尾节点它的next为NULL下一个循环自然退出。有人喜欢写while (p-next ! NULL)这会导致最后一个节点没有被处理到两个条件差一个节点写代码时一定要想清楚自己是想在“当前节点”还是“当前节点的下一个节点”做操作。3. 插入与删除的实操细节指针操作的顺序与边界检查3.1 按位置插入为什么循环到i-1而不是i按位插入是最经典的操作要求在第i个位置从1开始计数插入新节点。实现的关键是找到第i-1个节点。道理很直接链表的插入本质上就是“在某个已有节点之后链接一个新节点”你必须先找到这个“前驱节点”。bool InsertList(LinkList L, int i, ElemType e) { if (i 1) { return false; // 位置非法 } LNode *p L; // p从头结点开始走 int j 0; // p当前在第几个节点头结点记为第0个 while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { return false; // i超过了链表长度1 } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next p-next; // 1. 新节点先连向原后继 p-next s; // 2. 前驱节点再指向新节点 return true; }这里的两个步骤顺序绝不能反。必须先让s-next指向p的后继再让p-next指向s。一旦先执行p-next s原后继节点的地址就被覆盖丢失了s就再也接不上后面的节点链表从此断成两截。一句话先接上新节点的后路再动前驱的指针。循环条件p ! NULL是边界检查的关键。假设链表有5个节点想插到第7个位置p在向后移动的过程中会走到NULL循环必须终止并返回失败。如果省略这个条件代码会在p等于NULL时仍然执行p-next s直接对空指针解引用程序崩溃。所有涉及遍历的链表操作都有这个共性访问p-next之前必须先保证p不是NULL。3.2 按位置删除释放内存与置空next删除操作同样需要找到前驱节点然后让前驱跨过被删除节点直接指向它的后继。找到被删除节点后需要释放它的内存。bool DeleteList(LinkList L, int i, ElemType *e) { if (i 1) { return false; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL || p-next NULL) { return false; // p已经到尾后面没有可删节点 } LNode *q p-next; // q是要删除的节点 p-next q-next; // 前驱直接连向后继 *e q-data; // 把删除节点的值带回给调用者 q-next NULL; // 断开防止置垃圾数据 free(q); // 释放内存 return true; }我这里比课本稍多了一步在free之前把q-next置为NULL。虽然free之后这块内存就不能再访问但置空是一个好习惯能避免调试器中看到一个指向已释放内存的野指针排查问题时会省很多时间。删除最后一个节点时q-next本来就是NULL无妨逻辑统一。释放后很多人会忘记用返回值把删除的数据带出来。教材里DELETE函数的参数带了一个ElemType *e就是用来返回被删元素的。面试中如果题目要求“删除链表中值为x的所有节点”返回值还常用来统计删除了几个。3.3 按值查找与按位置访问循环边界差异按值查找和按值定位是链表最常用的查询操作。按值查找的逻辑很直白从头结点后面的首元结点开始依次比较每个节点的数据域找到就返回该节点的指针找不到返回NULL。LNode *LocateElem(LinkList L, ElemType e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; // 找到返回node指针找不到返回NULL }这里有两种写法一种像我这样把“p不为空且data不等于目标”作为循环条件退出时p要么是目标节点要么是NULL另一种写法是先判断p是否为空再判断data。两种都对但第二种种法的代码会多一层嵌套可读性差一些。我习惯前者因为退出循环时语义非常清晰。按位置访问取第i个元素则需要注意循环从第1个节点开始走i-1步才能到第i个。一种常见的思路是把j初始化为0、p指向头结点然后循环j i让p从头往下走i次。但这样有个细节如果i大于链表长度最后一次循环p已经是NULL再访问p-data又会崩溃所以要先判断。核心要点是定位某位置时永远要问自己“循环结束时p到底停在哪”考场上你画个链表图把p的走向一步步画出来比空想靠谱得多。3.4 不带头结点的链表插入删除需要改变头指针前面说带头结点的好处是简化操作那如果不带头结点会怎样在“指定位置建立单链表”这类题目里不带头结点的写法同样会出现。bool InsertWithoutHead(LNode **L, int i, ElemType e) { if (i 1) { return false; } if (i 1) { // 在头部插入头指针本身要变 LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; s-next *L; *L s; return true; } LNode *p *L; int j 1; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { return false; } LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; s-next p-next; p-next s; return true; }可以看到关键区别插入第1个位置时头指针必须更新所以整个函数不得不接收二级指针LNode **L。操作时不带头结点还有一个隐患如果链表为空p *L后p就是NULL走到删除或插入分支前要做好空表判断。不带头结点的代码在头部操作这个分支上比带头结点多了将近一半的判断这也是为什么实际工程普遍带头结点的原因。但如果考试或作业里明确要求不带头结点你就得老老实实把i1这个边界独立处理任何想靠统一逻辑蒙混过关的写法都会在头部出问题。4. 双链表与循环链表结构升级与代码差异分析4.1 双链表结构多一个指针多一倍的指针修改量单链表只能从前往后走找前驱节点必须从头开始重新遍历。双链表就是在节点里多存一个prior指针指向前驱节点这样既能往后走也能往前走。适用场景很清晰频繁需要“回退”或“删除指定节点的前驱”的操作用双链表可以避免O(n)的重新查找。typedef struct DNode { ElemType data; struct DNode *prior, *next; } DNode, *DLinkList;双链表插入时要修改四个指针顺序非常讲究。以在节点p之后插入新节点s为例s-next p-next; // 1. 新节点连向p的后继 s-prior p; // 2. 新节点的前驱指向p if (p-next ! NULL) { p-next-prior s; // 3. 原后继的前驱改为s要判空 } p-next s; // 4. p的后继改为s注意第3步的判空如果p本来就是尾节点p-next为NULL此时p-next-prior s就是对空指针解引用直接崩溃。单链表插入没有这个问题因为它的修改方向是单向的。这个区别就是“多一个指针多一倍的边界检查”。双链表删除节点s本身的操作比单链表更干净因为可以通过s-prior找到前驱不需要遍历s-prior-next s-next; if (s-next ! NULL) { s-next-prior s-prior; } free(s);同样是边界检查删的是尾节点时s-next为NULL就不用处理后继的prior。总之双链表操作的代码框架跟单链表很像但每一个指针操作都要问一句“这个指针如果是NULL怎么办”4.2 循环链表终止条件从NULL变为头指针循环链表让尾节点的next不再指向NULL而是指向头结点或链表第一个节点整条链首尾相接。循环链表的核心区别在于遍历终止条件单链表判断p ! NULL循环链表判断p ! L。以带头结点的循环单链表为例遍历终止条件变为LNode *p L-next; while (p ! L) { // p回到头结点说明走完一圈 printf(%d , p-data); p p-next; }循环链表的好处之一是某些场景更自然比如约瑟夫环问题中每轮删除一个人后要继续从下一个人开始数数如果链不是循环的数完之后要跳回开头逻辑很不自然。另一个好处是带尾指针的循环链表在尾部插入节点的复杂度降为O(1)不需要从头遍历找尾节点。空表判断也要跟着变带头结点的循环链表判空条件是L-next L。有的教材把尾指针作为整个链表的入口这种情况下判空条件变成L NULL插入第一个节点时还要特殊处理。这些细节在考试中很容易混淆用一个办法就能彻底理清拿到任何链表题先画图把空表、单节点表、正常表三种形态都画出来判空条件一目了然。4.3 链表逆序与排序高频面试题的两种解法逆序链表是面试题中的常客。常见做法有两种三指针法和头插重建法。三指针法维护prev、curr、next三个指针依次把curr-next反向指向prev然后整体后移直到遍历完成。核心代码如下LNode *ReverseList(LNode *head) { LNode *prev NULL, *curr head, *next NULL; while (curr ! NULL) { next curr-next; // 先保存后继防止断链 curr-next prev; // 反转当前节点指针 prev curr; // 整体推进 curr next; } return prev; // 新头就是原链表的尾节点 }注意这里函数返回的是新的头指针。因为你翻转整条链表后原来的头结点变成了尾节点新的头必须是原来的尾节点所以必须把新头返回给调用者。不带头结点时这一点格外重要千万不能继续沿用旧的头指针。另一种思路是遍历原链表用头插法重建一条新链表相当于“逆向复制”需要额外空间。两种方法各有优点三指针法原地完成空间O(1)最优头插重建法代码短好理解但需要新链表空间。链表排序在考研和笔试题里也很常见尤其是“对链表进行插入排序”和“合并两条有序链表”。链表不能随机访问快排的partition不好做冒泡排序虽然能实现但O(n²)不划算最适合链表的是归并排序因为归并只需要修改指针而不需要移动元素。核心思路就是递归地把链表从中间分成两部分分别排序后合并。找中间节点的方法也很经典快慢指针快指针每次走两步慢指针每次走一步快指针到尾部时慢指针正好在中点。5. 常见问题与调试经验上机最容易踩的坑5.1 高频Bug速查表现象、原因与解法链表代码的调试很多时候比的不是你逻辑有多强而是你能多快地把常见错误“认出来”。我整理了一份高频Bug速查表基本覆盖了刚学链表时会遇到的大部分问题。问题现象可能原因排查建议打印链表时出现随机大数字没有对节点数据域初始化就使用检查所有malloc后是否给成员都赋了值打印到中间就Segmentation Fault链表断链重点检查插入操作中赋值顺序s-next和p-next是否搞反遍历时少打印最后一个节点循环条件误用p-next ! NULL问自己p指向的当前节点要不要处理插入到第1个位置失败不带头结点时没有更新头指针检查是否用了二级指针头部插入需单独处理删除后再次遍历崩溃被删节点的next没有置NULL或野指针删除后把next置NULL再把指针置NULL链表现在多了一个节点初始化时把p L而不是L-next检查遍历的起点是不是跳过了头结点free之后程序立刻崩溃可能free了栈上的变量或已经free过的指针确认free的对象是malloc返回的堆指针插入位置非常大时不报错缺少循环中的p ! NULL边界判断补上p ! NULL防止p走到NULL后还解引用这张表的核心价值在于把错误和“对应节点图景”联系起来。每遇到一个bug先在纸上画一画当前链表的实际形态再从表里找对应的可能原因通常比盯着代码发呆有效得多。5.2 我调试链表的习惯性动作画图与打印辅助链表调试最有效的工具不是调试器里的变量窗口而是纸和笔。我的习惯是遇到链表逻辑错误先画一个横向的方框链把每个节点的地址、数据、next指向用箭头标出来然后把代码里每一步操作对箭头的修改也标出来跟真实链表对比断链的位置基本一眼就能看出来。单步调试也很管用。在IDE里给核心操作比如插入中的p-next s打断点看每一步执行前和执行后p、s、s-next各自指向什么地址。你很快会发现很多“意料之外”的情况其实是自己脑补错了链表的形态。还有一个朴素的习惯在关键函数里临时加打印语句打印每个节点的data和地址。比如遍历时打印printf(addr%p data%d next%p\n, p, p-data, p-next)一条链表到底长什么样一眼明了。调试完成后把打印删掉或者在代码里加一个#ifdef DEBUG开关平时不输出调试时打开既方便又不影响发布的代码可读性。5.3 不同语言实现链表时的对应关系很多读者学的第一语言不是C在Java、Python、C里写链表感觉有点对不上号。其实核心概念完全一致只是语法表达不同。C语言里用结构体和指针实现链表节点是一个结构体指针保存下一个节点的地址。Java/Python里用类和对象引用实现链表节点是一个类类的成员变量指向下一个节点对象。Java没有“指针”这个概念但对象的引用本质上就是受管控的指针。Python里更直接任何变量都是对象的引用所以定义一个节点类next成员指向另一个节点对象就构成了链表。class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextC里可以用结构体或类也可以用STL的list容器本身就是双向链表但面试手写链表时C的写法和C几乎一样唯一的区别是不再用malloc/free而是用new/delete。C和C混写时最经典的错误就是用malloc分配的内存用delete释放或者用new分配用free释放。这两种不匹配在绝大多数编译器上不会立即报错但会在运行到某个临界点的时候神秘崩溃。还有一个区别要注意C语言需要手动管理内存最后必须freeJava/Python有垃圾回收不手动释放也不会内存泄漏严重。但Java/Python里如果忘了把被删节点的next置空那个节点仍然被自己的next字段引用垃圾回收器就无法判断它是否可回收这同样会造成内存泄漏。所以“释放”在不同语言里的具体动作不一样但“孤儿引用”的危害是一致的。5.4 实用技巧转义字符与编辑器配置小记在调试链表时为了方便打印链表的每个节点我经常在printf里用%p打印指针地址配合\n换行输出一行多个节点信息。比如printf([%p | %d] - , p, p-data);这样输出的内容可以直观地映射成链表形态。调试时建议在编辑器里开启“显示空白字符”的功能能避免某些看不见的空格或制表符导致格式判断失误。虽然这跟链表关系不大但实际调试中很多输出对不上的问题其实来自打印语句本身被环境干扰了。这些技巧听起来很琐碎但真正写链表时就是这些琐碎细节决定了你能不能在半小时内定位到一个隐蔽的断链错误。写链表代码我个人的体会是它不考验智商考验的是你有没有把每一步指针操作对应到脑子里那幅链表的图景。把带头结点、不带头结点、循环链表、双链表都亲手写一遍并且在纸上画出每一步的指向变化这一章就算真正过关了。之后无论是做算法题、准备考研408还是工作中写LRU缓存、管理内存块链表这套思维都会反复出现。如果这篇文章里有任何一个坑让你避开了一次debug的煎熬就算没白读。
