上个月整理代码仓库翻出一个命名草率的文件里面摞着三版链表实现从“单链表v1”一路改到“/////链表”。不少人问过我同一个问题都什么年代了还有必要研究链表我的答案一直没变——太有必要了。链表不光是面试题里的常客更是理解指针、内存布局、算法复杂度的最佳训练场。这篇文章打算把手写链表的完整思路摊开讲从C结构体链表基本语法到链表遍历、链表插入、逆置链表再到循环单链表、嵌入式链表代码示例最后聊聊基于链表的两个集合差集怎么做。适合正在补数据结构基础、准备面试或者要在嵌入式环境里手工管理动态内存的读者。内容不绕弯子全部按可复现代码来。1. 为什么说链表是“老古董”里最不过时的数据结构1.1 数组和链表差的不是一星半点很多人学链表之前已经熟练使用数组觉得链表不过就是“不能随机访问的数组”这是一个很大的误解。数组和链表解决的是完全不同的内存组织问题。数组在内存里是一整块连续空间声明一个int arr[100]系统就给你划出400字节连着的位置。访问arr[i]只需要用arr i * sizeof(int)做一次地址计算这就是O(1)随机访问的来源。但它的代价也在这里想在第10个位置插入一个新元素后面的90个元素全部要往后挪想删除第10个元素后面的元素又得往前补。最坏情况下一次插入要搬动整个数组。链表则完全不同。它的每个节点都是独立分配的内存靠指针把彼此“串”起来。节点在物理内存里可以东一个西一个上一个节点的next指向下一个节点的地址。这样插入和删除只需要修改相邻节点的指针不需要搬动任何数据。代价是访问某个位置的元素必须从头开始一个一个往后走随机访问是O(n)。打个比方数组像一栋楼里连续编号的房间靠门牌号直接找链表像一条铁链子每节车厢都知道下一节是谁想找第100节车厢只能从车头一节节数过去。这两种结构没有谁绝对取代谁而是各自擅长不同场景。链表在处理频繁增删、数据量不可预估的场景下有天然优势这也是操作系统和嵌入式系统至今大量使用链表的原因。1.2 真实系统里链表无处不在链表不是只在教科书和面试题里出现它在我们每天用的系统里到处都是。操作系统的进程管理Linux内核里task_struct通过链表把所有进程串起来新增、退出进程时只需要做指针操作。内存管理很多系统用空闲链表free list记录可分配的内存块分配和释放时就是链表节点的摘除和挂入。LRU缓存CPU的Cache替换策略、Redis的LRU淘汰算法核心都是一个双向链表加哈希表。文件系统目录项缓存、空闲块管理经常用到链表。嵌入式消息队列中断处理程序和主循环之间传递数据最常见的数据结构就是循环单链表实现的环形队列。一句话链表不是一个“过时的玩具”而是一种底层的、系统级的组织思想。把链表写熟练意味着你能理解指针怎么工作、内存怎么布局、边界条件为什么会出事。下面开始动真格的——从零手写一个单链表。2. 单链表从零实现C结构体链表基本语法与插入删除全流程2.1 节点结构带头节点和不带头的差别先定义最基础的节点结构。一个节点保存一个数据域和一个指向下一个节点的指针在C里最简单就是结构体struct Node { int data; Node* next; };这个next就是“铁链”上的连接环。创建三个节点并串起来代码长这样Node* head new Node{1, nullptr}; head-next new Node{2, nullptr}; head-next-next new Node{3, nullptr};这种写法的特点是head指针直接指向第一个数据节点。好处是代码直观坏处是涉及删除第一个节点、或者在头部插入节点时必须修改head指针本身稍不留神就会丢头。另一种常见的做法是加一个“头节点”dummy node。头节点不存数据它的next才指向真正的第一个数据节点Node* dummy new Node{0, nullptr}; dummy-next new Node{1, nullptr};有头节点的好处在于无论操作哪个数据节点都不需要动dummy这个头指针代码的边界判断会少很多。很多工程的链表实现都会带头节点比如Linux内核链表的各种操作宏本质上就是围绕一个固定的头节点转。我自己在实际项目里更推荐带头节点尤其是新手阶段能少踩一堆空指针的坑。2.2 插入操作头插、尾插、中间插三种场景插入是链表最核心的操作理解了插入差不多就理解了链表一半的指针逻辑。三种插入场景分别说。头插。新节点成为新的第一个节点所以要先把新节点的next指向原来的头再更新head。注意顺序不能反反了就把原有链表弄丢了void insertAtHead(Node* head, int val) { Node* newNode new Node{val, nullptr}; newNode-next head; head newNode; }这里有个非常重要的细节head参数类型是Node*也就是指针的引用。如果写成Node* head函数内部修改head只是改了形参副本调用结束后原来的head根本不会变——这就是经典的“值传递丢头”问题后面踩坑章节我会专门展开。尾插。需要先找到当前链表的最后一个节点让它的next指向新节点void insertAtTail(Node* head, int val) { Node* newNode new Node{val, nullptr}; if (head nullptr) { head newNode; return; } Node* cur head; while (cur-next ! nullptr) { cur cur-next; } cur-next newNode; }尾插的时间复杂度是O(n)因为无论如何都要遍历到链表末尾。如果频繁做尾插工程上会让表头表尾各存一个指针。中间插。最常用的是在某个已知节点后面插入这个操作时间复杂度是O(1)也是链表对比数组最漂亮的地方void insertAfter(Node* prev, int val) { if (prev nullptr) return; Node* newNode new Node{val, nullptr}; newNode-next prev-next; prev-next newNode; }注意newNode-next prev-next这一步必须先做再把prev-next指向新节点。顺序一旦写反原来的后继节点就找不到了。2.3 删除操作最怕丢头丢尾删除相比插入稍微绕一点。删除的核心问题是单向链表只知道当前节点的后继不知道前驱所以要删除某个节点必须找到它的前驱节点让前驱的next跳过被删节点指向被删节点的下一个节点。按值删除的完整代码void deleteNode(Node* head, int val) { if (head nullptr) return; if (head-data val) { Node* tmp head; head head-next; delete tmp; return; } Node* cur head; while (cur-next ! nullptr cur-next-data ! val) { cur cur-next; } if (cur-next ! nullptr) { Node* tmp cur-next; cur-next tmp-next; delete tmp; } }这里有两个边界条件要重点盯一是删除的是头节点。这时必须直接更新head否则头指针会指向一块被释放的内存后续遍历直接崩溃。二是空链表和找不到目标值。空链表时cur-next存在的前提是head ! nullptr上面的代码用if (head nullptr) return;做了保护找不到目标值时循环退出条件是cur-next nullptr自然什么也不做不会误删。一个常见的设计误区是“删除节点时直接把传入的节点指针delete掉完事”。真正工程上要删哪个节点往往是按值、按下标或者按条件找到的而找到之后必须是在“前驱节点”层面操作而不是在当前节点层面。很多新手写delete cur之后继续用cur这就是悬垂指针的典型来源。3. 遍历和逆序把最常见的三个操作吃透3.1 遍历一切操作的基础遍历是链表所有操作的基石插入要遍历找位置删除要遍历找前驱逆置要遍历改指针打印要遍历输出。单链表的遍历非常简单void printList(Node* head) { for (Node* cur head; cur ! nullptr; cur cur-next) { std::cout cur-data ; } std::cout std::endl; }循环的终止条件是cur ! nullptr意思是走到链表最后一个节点的next也就是nullptr就停。这个循环里最关键的思维转变是不要想着“当前位置是第几个”而要想着“当前指针指向谁它的next是谁”。链表里没有任何下标概念所有的操作都是顺着next往下“走”。遍历时最容易犯的错是循环里更新了cur-next却忘了更新cur本身或者在循环体内部修改了cur-next导致跳过了节点。写链表遍历心里要时刻清楚“cur现在指向哪、cur下一步指向哪”。3.2 逆置链表的三种写法头插法、三指针、Python版逆置链表是链表操作里最经典、也最能检验指针基本功的题目。一个链表1 - 2 - 3 - 4 - NULL逆置后要变成4 - 3 - 2 - 1 - NULL。头插法逆置。思路很朴素把原链表从头到尾摘下来每个节点都往一个新链表的头部插入最后新链表就是逆序的。Node* reverseByHeadInsert(Node* head) { Node* newHead nullptr; Node* cur head; while (cur ! nullptr) { Node* next cur-next; // 先保存后继否则断了找不回来 cur-next newHead; // 当前节点指向新链表头部 newHead cur; // 新链表头更新为当前节点 cur next; // 继续处理原链表的下一个节点 } return newHead; }三指针逆置。思路是在原链表上原地改指针方向用三个指针prev、cur、next分别记录前驱、当前、后继Node* reverseByThreePointers(Node* head) { Node* prev nullptr; Node* cur head; while (cur ! nullptr) { Node* next cur-next; cur-next prev; prev cur; cur next; } return prev; }每次循环做一件事把cur-next从指向后面的next改成指向前面的prev。改完之后prev和cur整体往后挪一格。循环结束时cur为nullptrprev停在原链表的最后一个节点也就是新链表的头。头插法需要额外的newHead指针三指针法不需要额外链表但本质都是“边走边改方向”。我个人建议把三指针法练到闭着眼睛能写因为它在空间上最省也是面试时最加分的写法。Python单链表逆序。Python没有指针语法但思路完全一致。定义节点类然后同样用三个游标完成class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverse_list(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev递归版本也值得一提它能让代码更短但递归深度受栈限制长链表下有爆栈风险def reverse_recursive(node): if node is None or node.next is None: return node new_head reverse_recursive(node.next) node.next.next node node.next None return new_head递归的思路是先假设后续链表已经逆置完成再把当前节点接到尾部。理解递归逆置的关键是node.next.next node这行——它让当前节点的后继节点反过来指向当前节点相当于把箭头掉了个方向。3.3 写完逆置后如何自测逆置代码写出来不代表对一定要自测。我的习惯是测这么几个用例空链表输入nullptr期望返回nullptr。单节点链表只有一个节点逆置后还是它自己。两个节点1 - 2逆置后2 - 1重点看头指针是否正确。三个及以上的节点反转后打印确认首尾正确、中间顺序没乱。很多bug在三个节点以上的用例里才会暴露尤其是指针顺序写反时链表不是变成循环就是丢掉中间节点。如果手边没有调试器打印遍历是最快的手段。逆置后打印链表看到4 3 2 1就是对的看到4或者死循环就是哪里出了问题。4. 循环单链表实战约瑟夫问题与环形队列4.1 循环单链表尾节点又指回了头节点循环单链表和普通单链表唯一的区别是最后一个节点的next不再指向nullptr而是指向头节点形成一个环。这个看似微小的变化带来两个直接影响第一遍历的终止条件从cur ! nullptr变成了cur ! head。因为环里没有nullptr不能再用“走到空就停”的方式判断了。第二整个链表没有天然的“头”和“尾”任何节点都可以作为入口开始遍历。这在需要循环轮转的场景下特别自然。创建循环链表的典型过程是先构建好普通单链表再把尾节点的next指向头Node* head new Node{1, nullptr}; Node* tail head; for (int i 2; i 5; i) { Node* node new Node{i, nullptr}; tail-next node; tail node; } tail-next head; // 关键一步形成循环遍历循环链表要用do...while确保至少执行一次再判断是否回到起点Node* cur head; do { std::cout cur-data ; cur cur-next; } while (cur ! head);4.2 约瑟夫问题循环链表的经典应用约瑟夫问题是个流传很广的故事n个人围成一圈从第一个人开始报数报到m的人出列然后下一个人重新从1开始报数直到只剩最后一个人求最后幸存者的编号。这个问题几乎所有讲循环链表的地方都会提到原因很简单它天然就是一个“围成一圈不断数数”的问题。用循环单链表实现非常直观int josephus(int n, int m) { Node* head nullptr; Node* tail nullptr; for (int i 1; i n; i) { Node* node new Node{i, nullptr}; if (head nullptr) { head node; tail node; } else { tail-next node; tail node; } } tail-next head; Node* cur head; Node* prev tail; int count 1; while (prev ! cur) { if (count m) { Node* tmp cur; prev-next cur-next; cur cur-next; delete tmp; count 1; } else { prev cur; cur cur-next; count; } } return cur-data; }核心逻辑就一句话数到m就把当前节点从环里摘掉。摘的时候要借助prev记录前驱因为单链表无法回头找前驱。循环终止条件是prev ! cur意思是当前还剩下最后一个节点时它自己指向自己就该停下来了。这个实现里我特别想强调一个细节删除节点后cur直接移到prev-next也就是被删节点的后继。这样下一个报数的人正好是原链表里被删节点的下一位符合“下一个人重新从1开始报数”的规则。4.3 循环单链表在嵌入式消息队列中的应用抛开面试题循环单链表在嵌入式领域有个非常实际的应用——环形缓冲区。单片机或者RTOS环境下中断服务程序往里写数据主循环里往外取数据这中间需要一个缓冲区。如果直接用数组要额外维护读写索引、处理索引回绕用循环单链表天然就是一个环形结构写的一端只需要往尾节点后面追加或者干脆固定一个“写指针”在环上不断前进读的一端跟着“读指针”追。这比数组实现更灵动也比线性链表实现更省心——不用担心队列空了还往外取、队列满了还往里写导致指针越界。我见过不少嵌入式项目里消息队列就是用固定大小的循环链表加两个游标实现的。固定大小的原因后面章节会讲嵌入式环境不能随便malloc节点要么静态分配要么从内存池里取。5. 嵌入式环境下的链表从内存布局到代码示例5.1 嵌入式环境的内存约束直接决定链表的写法嵌入式环境写链表和PC上写链表有个很大的区别内存既小又碎。PC上可以放心地new、delete操作系统帮忙管理堆偶尔碎个片也没什么感觉。嵌入式环境里RAM可能只有几十KB堆很小甚至根本没有频繁动态分配内存会导致内存碎片时间长了碎片多到连小块内存都分配不出来。更要命的是如果中断和主循环同时访问链表不加保护还会出现数据竞争。所以嵌入式链表代码示例跟我上面写的PC版有个根本差异节点内存不动态分配而是用静态数组或者内存池。这样地址固定、分配时间确定、不会碎片化中途中断不会因为分配内存引入不确定性。5.2 静态内存池里的链表代码示例一个简单的思路是预先定义一个节点池数组再用一个空闲链表来管理哪些节点可用。节点被使用时挂到业务链表上释放时归还到空闲链表。#define POOL_SIZE 32 typedef struct Node { int data; struct Node* next; } Node; static Node pool[POOL_SIZE]; // 节点池 static Node* freeList; // 空闲链表的头 void poolInit(void) { freeList pool[0]; for (int i 0; i POOL_SIZE - 1; i) { pool[i].next pool[i 1]; } pool[POOL_SIZE - 1].next NULL; } Node* allocNode(int data) { if (freeList NULL) return NULL; // 池已耗尽 Node* node freeList; freeList freeList-next; node-data data; node-next NULL; return node; } void freeNode(Node* node) { node-next freeList; freeList node; }有了这个池子业务代码里创建和销毁节点的时间都是固定的不会被堆管理器的复杂逻辑拖慢。这个模式我在多个MCU项目里实测过稳定可靠。另外嵌入式里还有一种更彻底的“侵入式链表”代表性就是Linux内核的list_head结构。它的特点是节点自己不存数据而是挂在宿主结构体里通过指针找到宿主。好处是一个链表操作代码可以被所有业务复用坏处是理解门槛高一些。对大多数嵌入式项目来说简单直白的节点池方案已经够用。5.3 中断环境下的链表操作三个必须注意的点嵌入式链表真正容易出问题的地方在于中断和主循环共享链表。第一访问必须互斥。主循环在用链表时来了中断中断里也操作同一个链表两个执行流同时改指针链表很快就断成几截。最简单有效的方法是中断里只做标记链表操作全部放到主循环里做如果必须在中断里操作就用关闭中断或者临界区保护。第二释放节点的时机要小心。中断里释放一个节点到空闲链表主循环正在用的却是另一个链表两个链表互相独立还好如果共用一个空闲池就要保证分配和释放都是原子的。第三不要在主循环里长时间占用临界区。链表操作本身很快但遍历一个长链表就不快了。关中段时间太长中断延迟就会超标。实际做法往往是中断只把数据往环形队列里塞主循环批量处理处理完之后统一归还节点。6. 基于链表的两个集合的差集一个完整算法拆解6.1 集合差集的含义和链表存储的特点集合A和集合B的差集记作A - B意思是“属于A但不属于B”的元素。比如A是{1, 2, 3, 5}B是{2, 4, 5}那么A - B就是{1, 3}。当这两个集合分别用链表存储时问题就变成了在一个链表上做关系运算。先别急着写双层循环想清楚链表和集合各自的约束条件链表没有下标不能O(1)随机访问所以依赖随机访问的算法要重新考虑。集合要求元素不重复所以结果链表里不能出现重复值除非输入本身保证无重复否则要先处理去重。差集不改变原有集合所以不能破坏A、B两个链表本身要么原地操作创造条件要么新开一个链表存结果。6.2 朴素解法双重遍历加标记最容易想到的方法是遍历A中每个元素再到B里完整找一遍找到就不加入结果找不到就加入结果。Node* setDifferenceNaive(Node* A, Node* B) { Node* dummy new Node{0, nullptr}; Node* tail dummy; for (Node* pa A; pa ! nullptr; pa pa-next) { bool found false; for (Node* pb B; pb ! nullptr; pb pb-next) { if (pa-data pb-data) { found true; break; } } if (!found) { tail-next new Node{pa-data, nullptr}; tail tail-next; } } return dummy-next; }时间复杂度是O(nm)A有n个元素、B有m个元素时最坏要做nm次比较。这个方法代码直白不依赖任何额外空间适合两个链表都很小的场景。但如果A有十万个节点B也有十万个这个算法就跑不动了必须优化。如果B的元素范围很小时还可以用标记数组替代第二层循环——开一个足够大的布尔数组先遍历B把存在的值标记再遍历A查标记。代价是需要一块和取值范围等大的额外内存。这个方案适合值域紧凑的场景比如数值都是0到10000以内的整数时非常香。6.3 排序加双指针把差集复杂度降下来更通用的优化是排序加双指针。先把A、B两个链表各自排成升序然后同时从头扫描比较过程中两个指针各走各的Node* sortedInsert(Node* head, int val) { Node* node new Node{val, nullptr}; if (head nullptr || head-data val) { node-next head; return node; } Node* cur head; while (cur-next ! nullptr cur-next-data val) { cur cur-next; } node-next cur-next; cur-next node; return head; } Node* setDifferenceSorted(Node* A, Node* B) { Node* sortedA nullptr; for (Node* p A; p ! nullptr; p p-next) { sortedA sortedInsert(sortedA, p-data); } Node* sortedB nullptr; for (Node* p B; p ! nullptr; p p-next) { sortedB sortedInsert(sortedB, p-data); } Node* dummy new Node{0, nullptr}; Node* tail dummy; while (sortedA ! nullptr sortedB ! nullptr) { if (sortedA-data sortedB-data) { tail-next new Node{sortedA-data, nullptr}; tail tail-next; sortedA sortedA-next; } else if (sortedA-data sortedB-data) { sortedB sortedB-next; } else { sortedA sortedA-next; sortedB sortedB-next; } } while (sortedA ! nullptr) { tail-next new Node{sortedA-data, nullptr}; tail tail-next; sortedA sortedA-next; } return dummy-next; }双指针比较的逻辑不复杂sortedA的值小说明它不可能在B里出现B已经是升序后面的值只会更大直接收进结果sortedB的值小说明A当前的值可能在B后面把B指针往后走两者相等说明A该元素在B里存在直接跳过。这个方案的时间复杂度是排序O(n log n m log m)加上扫描O(n m)在数据量大时比双重循环快好几个量级。代价是需要额外空间存两个排序结果链表以及写一个插入排序。如果不想自己写排序也可以用归并排序的思路对链表排序效果是一样的。实际项目中我还会做一个补充处理如果A里有重复元素排序后相同的值会相邻扫描时加一个判断“当前值等于上一个值时跳过”顺便就把去重做了。这一步看起来小但对结果正确性影响很大。7. 我写链表时真实掉进去过的坑写完那么多代码最后聊点实在的。我在项目里和教学里见过太多链表bug这里挑四个最有代表性的说个个都是真实踩过的坑。7.1 指针指到自己链表原地打转有一次我写的遍历输出死活停不下来终端光标一直跳最后发现原因是构建链表时某个节点的next被误设成了自己。单节点自环还好发现要命的是长链表里某处悄悄形成小环遍历到那里就无限循环。排查方法很简单遍历时加一个计数器超过总节点数N就报错退出。更早预防的方法是每次修改next前用纸笔画一遍“当前指针从哪来、要往哪去”画对了再写代码。7.2 删除节点之后继续访问它delete之后的节点内存已经归还data和next都是无效的继续访问就是悬垂指针。我见过最隐蔽的一种是删除节点时把结果存到局部变量里后面不小心又用了这个局部变量。C不会报错因为它读的是已经释放的内存表现就是“有时候正常有时候崩”。正确做法是删除节点后把它立刻置空并且养成“谁删除谁负责删除后绝不再用”的习惯。7.3 头指针传参丢了头这是新手问得最多的一个问题。void insertAtHead(Node* head, int val)看上去没问题可函数里执行head newNode之后外面打印链表发现什么都没变。原因就是传的是指针的值拷贝——head本身是变量保存一份地址把这个变量传进去函数里改的是副本改不到外部的真实头指针。解决方法是前面代码里那样用Node* head或者在函数里返回新的头指针Node* insertAtHead(Node* head, int val)用返回值覆盖外部变量。两条路都行但要形成固定习惯别混着用。7.4 调试链表最快的方式画图和打印链表代码出bug时不要急着改先把链表画出来。左箭头右箭头一画哪个指针接错了一目了然。打印也很有用尤其是对比插入、删除、逆置前后的输出。我写链表必配一个打印函数这个习惯救过我太多次。最后再分享一个小技巧写链表题先处理空链表和单节点这两个极端情况再处理普通情况。极端情况代码量不大但能挡住一半的崩溃。只要把“空、单、多”三种情况都验证过这段链表代码基本就稳了。链表的代码量不大难在指针逻辑的严谨性手写几遍之后你对内存和指针的理解会上一个台阶这是任何框架和高级语言都替代不了的基本功。