先问个问题你平时用的是数组还是链表如果只是存几个数据、按下标访问数组确实香。可一旦碰到“在中间插一个元素”这种操作数组的短板就会暴露——后面的数据全要往后挪量一大立刻卡顿。链表在此时就是替代方案元素分散存放不用整体移动靠指针把节点一个个串起来。这一篇我会从节点定义讲起把单链表、循环链表、逆置、集合差集和嵌入式场景一次说清楚适合刚学数据结构的学生、准备机试的选手以及需要在嵌入式环境里手写链表的朋友。1. 从数组痛点引出链表先想清楚为什么用它1.1 连续内存的代价数组的核心特征是“连续内存”这带来两个硬伤。第一插入和删除的代价高在数组头部插入一个元素所有已有元素都要往后退一位平均时间复杂度 O(n)删除同理需要前移。第二扩容成本高数组空间不足时要重新申请一块更大的连续内存再把旧数据整体拷贝过去这一步在实时性要求高的场景里很要命。链表正好绕开这两点。它的节点不需要挤在一起每个节点存数据再存一个指向下一个节点的指针节点之间靠指针串联。想插入一个新节点只需要改前后两个指针的指向其他节点完全不动插入和删除操作的时间复杂度是 O(1)前提是你已经站在了目标位置附近。1.2 链表的构成节点和指针链表的“零件”是节点每个节点通常包含两部分数据域存放实际数据可以是整数、字符、结构体也可以是任意自定义类型。指针域存放下一个节点的地址C/C 里就是指针Java/Python 里就是引用。整条链还要有头指针指向第一个节点。头指针没了整条链表就找不到了所以它是一切操作的前提。为了简化边界情况很多人还会引入一个头节点哨兵节点它不存业务数据只作为链表的固定起点。这样即使链表是空的头指针也有值插入、删除的代码能少写不少分支判断。1.3 什么时候该用什么时候不该用选链表之前先想清楚访问模式。读操作多、按下标随机访问多用数组或向量写操作多、频繁在中间增删用链表更合适。链表最吃亏的是随机访问——要拿第 k 个节点只能从头一个个数过去时间复杂度 O(n)。数组按下标访问是 O(1)这点差距很明显。实际项目中链表常见的去处包括缓冲区队列、LRU 缓存、操作系统的进程管理队列、内存池的空闲块管理以及嵌入式设备里需要动态增删的设备列表。这些场景共同点是元素数量不固定、增删频繁、很少依赖下标访问。2. C/C 结构体链表从定义到五种核心操作2.1 结构体节点定义C/C 里链表最经典的定义方式就是结构体。定义一个节点的结构包含数据域和指针域struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };构造函数的写法是 C 风格创建节点时会自动把 next 初始化为空指针。如果是纯 C 环境用 typedef 写法typedef struct ListNode { int val; struct ListNode* next; } ListNode;这里的next保存的是下一个节点的地址最后一个节点的next必须是 NULL这是遍历时判断链表是否结束的依据。这个 NULL 既是约定也是保护忘记初始化会让指针变成野指针调试时非常痛苦。2.2 创建链表头插法与尾插法创建链表有两个思路头插法、尾插法两者效果和用途完全不同。头插法新节点总是插在链表头部代码短但创建出来的链表顺序和输入顺序相反。ListNode* head nullptr; for (int i 1; i 5; i) { ListNode* node new ListNode(i); node-next head; head node; }这个过程可以理解为每次新来的节点站在队伍最前面指着原队首然后自己当新的队首。如果按 1 到 5 输入结果链表是 5-4-3-2-1。头插法常用于逆置场景后面会用到。尾插法新节点接在链表末尾保持输入顺序。需要额外维护一个尾指针插入时让尾指针指向新节点ListNode* head nullptr; ListNode* tail nullptr; for (int i 1; i 5; i) { ListNode* node new ListNode(i); if (!head) { head node; tail node; } else { tail-next node; tail node; } }尾插法的核心逻辑就是tail 永远指向最后一个节点来了新节点就tail-next接上去然后 tail 向前移动。2.3 遍历与查找遍历链表是其他所有操作的基础。用一个临时指针从头开始每步输出当前节点值然后移动到下一个直到遇到 NULLfor (ListNode* cur head; cur ! nullptr; cur cur-next) { std::cout cur-val ; }注意遍历时不要直接用头指针 head 移动否则头指针丢了整条链表无法恢复。查找某个值的节点也是同理边遍历边比较即可ListNode* cur head; while (cur cur-val ! target) { cur cur-next; } return cur; // 可能为 nullptr表示没找到这段代码里cur 是为了防止遍历到尾后继续访问空指针。先判断当前节点是否存在再访问 val顺序不能反过来。2.4 指定位置插入与删除指针修改的“先接后断”在单向链表的 p 节点后插入新节点核心就两行新节点先指向 p 的下一个节点再把 p 指向新节点。// 在 p 节点后面插入值为 value 的新节点 ListNode* node new ListNode(value); node-next p-next; p-next node;顺序不能反。如果先把p-next node那么原来 p 后面的节点就找不到了node 指向哪里变成未知。这是链表操作最常见的翻车点。删除 p 后面的节点ListNode* del p-next; p-next del-next; delete del;先把要删除的节点记下来然后让 p 跳过它最后释放内存。如果 p 后面没有节点p-next是 NULL这时代码会崩溃所以要先判断p-next ! nullptr。体会一下链表删除不是真正的“移除”而是绕过去让前面的节点不再指向它再把它占用的内存释放掉。理解这个思路写任何链表操作都不会乱。2.5 逆置链表迭代与递归两种解法逆置是链表的高频操作热词里“单链表逆序”“逆置链表”都指向它。迭代法最直观核心是三个指针的轮转ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; // 先保存下一个节点 cur-next prev; // 当前节点指向前一个 prev cur; // prev 前进 cur nxt; // cur 前进 } return prev; // 遍历结束后 prev 就是新头 }关键在nxt这个临时变量cur 的 next 一旦被改写原本的下一个节点就丢了必须先存下来。少了这一步循环根本走不下去程序要么死循环要么直接访问空指针。递归法写法简洁但理解门槛高一些ListNode* reverseList(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }思路是先递归逆置后面整条子链然后让当前节点的下一个节点反过来指向自己。递归的问题是调用栈深度等于链表长度链表很长的时候有栈溢出风险工程上迭代法更稳妥面试里两种最好都能写出来。2.6 别忘了释放内存C/C 里 new 出来的节点一定要 delete否则就是内存泄漏。释放整条链表用遍历void freeList(ListNode* head) { while (head) { ListNode* tmp head; head head-next; delete tmp; } }先保存下一个节点再删除当前节点顺序和逆置里保存 nxt 是一个道理。删除时千万不要先 delete 再取 head-next那等于访问一块已经归还的内存属于未定义行为。3. Java 和 Python 里的链表实现3.1 Java 引用即指针类节点写法Java 没有指针语法但引用本质上就是一个对象地址操作方式类似。定义节点类和链表创建如下class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } } ListNode head null; ListNode tail null; for (int i 1; i 5; i) { ListNode node new ListNode(i); if (head null) { head node; tail node; } else { tail.next node; tail node; } }遍历同样用临时引用for (ListNode cur head; cur ! null; cur cur.next) { System.out.print(cur.val ); }和 C 最大的区别是内存管理。Java 有垃圾回收机制不需要手动 delete。但这也带来一个问题如果删除了一个节点但还有变量引用它这个对象不会被回收链表里同步维护时要注意引用关系。3.2 Python 单链表逆序简洁但不简单Python 实现链表最接近 Java 风格类就是节点属性保存引用class ListNode: def __init__(self, val0, nextNone): self.val val self.next next逆序的迭代代码非常短def reverse_list(head: ListNode) - ListNode: prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev递归版本更短def reverse_list(head: ListNode) - ListNode: if not head or not head.next: return head new_head reverse_list(head.next) head.next.next head head.next None return new_headPython 写链表最大的便利是调试起来不操心内存最大的坑是语法糖太多很多人把列表 list 当成链表用导致对“节点”“引用”的理解始终停在表面。链表核心是节点对象之间的引用关系不是 list 的下标。3.3 内置类还是手写节点Java 里可以用LinkedListPython 里有collections.deque日常开发直接拿来用没问题底层就是链表或双向链表的封装。但刷题、面试、理解原理时我强烈建议手写节点。原因很简单内置容器把“指针怎么指”这个环节藏住了你只看到 API看不到引用变化。手写一个节点再写一遍插入、删除、逆置对链表理解完全是两个层次。等真正需要在嵌入式环境里写链表时你会感激当年手动写过的那几百行代码。4. 进阶应用三连循环单链表、集合差集、嵌入式链表4.1 循环单链表的构建与遍历终止条件循环单链表是单链表的变种最后一个节点的 next 不再指向 NULL而是指回头节点形成闭环。头插法创建 n 个节点的循环链表ListNode* createCircle(int n) { ListNode* head new ListNode(1); head-next head; // 第一个节点先自己指自己 ListNode* tail head; for (int i 2; i n; i) { ListNode* node new ListNode(i); node-next head; // 新节点指向头 tail-next node; // 尾接头 tail node; } return head; }遍历循环链表的终止条件从cur nullptr变成cur head或者先从头开始转一圈回来时停止。写循环链表最怕漏掉终止条件一旦条件写错程序会在循环里出不来CPU 占满整机卡死。约瑟夫问题就是循环链表最经典的实战应用n 个人围成一圈从某个位置开始报数报数到 k 的人出圈再从下一个重新报数直到只剩一人。用循环链表模拟这个过程非常自然每轮删除一个节点指针绕圈移动代码量不大但能把循环链表、删除、终止条件的细节全练到。4.2 基于链表的两个集合做差集“基于链表的两个集合的差集”是数据结构课的经典实验题。假设两个集合已经用有序单链表存储求 A - B即属于 A 但不属于 B 的元素组成的新集合。因为链表有序可以像归并一样双指针遍历ListNode* difference(ListNode* A, ListNode* B) { ListNode dummy; // 哨兵节点 ListNode* tail dummy; while (A B) { if (A-val B-val) { tail-next A; tail A; A A-next; } else if (A-val B-val) { B B-next; } else { ListNode* tmp A; // 相等说明是交集A 中该元素不该保留 A A-next; delete tmp; } } tail-next A; // B 已走完A 剩余全部属于差集 return dummy.next; }这里的哨兵节点是一个栈上的虚拟头节点它本身不存业务数据只让 tail 指针有一个统一的操作起点避免单独处理“第一个节点是什么”的分支。返回值是dummy.next也就是真实的新链表头。思路和归并排序的合并阶段很像区别在于差集要删除相同元素而不是收集它们。4.3 嵌入式场景的链表写法嵌入式环境里标准库的容器往往不能用动态内存也很紧张链表大多手写。最简单的嵌入式单向链表就是裸结构体struct message { int id; char data[64]; struct message* next; };每次需要存一个消息时分配一个 message 结构体把它挂到链表尾部。空闲时遍历链表找到对应 id删除并释放。这种写法直白缺点是链表逻辑和业务数据混在一个结构体里想管理不同类型的对象就得各自维护一套链表。更进一层的内核风格是把链表节点单独抽出来嵌入到业务结构体里struct list_head { struct list_head* next; struct list_head* prev; }; struct message { int id; char data[64]; struct list_head node; };这样链表操作函数只关心node这个字段业务数据靠container_of之类的宏从节点指针反推出宿主结构体地址。好处是同一套链表操作可以通用到任意类型上坏处是宏和指针运算的复杂度明显提升初学者容易看晕。我的建议是先写明白裸结构体版本再去研究内核链表的抽象层顺序不能反。嵌入式环境下还有个容易忽略的点必须自己保证内存管理可靠。分配失败要处理释放后要置空中断上下文里插入链表要考虑原子性这些问题平时写应用层代码根本碰不到但在嵌入式里都是实实在在的坑。5. 常见问题与调试心得5.1 空指针和野指针链表相关的崩溃十有八九是访问了空指针或野指针。常见写法while (cur-next) cur cur-next;如果 cur 本身就是 NULLcur-next直接崩溃。安全的写法是先判断 curwhile (cur cur-next) cur cur-next;另一种情况是野指针节点刚被 delete但其他指针还指向它。解决办法很简单被删除节点的指针立即置空不要让任何指针在 delete 后继续使用。5.2 指针修改顺序的经典翻车很多人第一次写“在 p 后插入节点”时会写成p-next node; node-next p-next; // 永远指向自己链表断裂这就是顺序错。正确逻辑是新节点先指向 p 原来的下一个p 再指向新节点。我教人时总说一句话先把新节点的“后路”接好再断 p 的“旧路”。所有的链表插入操作本质都是这个原则。5.3 内存泄漏与使用野指针C/C 里忘记 delete 节点程序跑得久了内存只增不减。内存泄漏在跑一次就结束的小程序里感觉不到在嵌入式设备或服务端进程里就是致命问题。释放链表就整链释放删除节点就只删目标节点两种场景的口诀是先保存 next再 delete 当前。5.4 调试套路打印链表 画指针指向图我调试链表有一套固定流程。第一步写一个打印链表的函数每次插入、删除后都打印一次用程序输出验证逻辑。第二步在纸上画出节点和指针的指向变化一步一步模拟代码执行。很多人觉得画图麻烦但链表这种“指针指来指去”的结构光靠脑子里推演很容易错一张图能救你半小时。第三步遇到段错误先用调试器看栈。C 用 gdb 或 VS 的调试器能看到当前访问的是哪个指针、哪个语句崩溃这比瞎猜快得多。5.5 常见错误速查表症状可能原因排查方向访问空指针崩溃循环条件漏判 NULL遍历时先判 cur 再判 cur-next链表遍历出现死循环循环链表未处理终止条件或插入时 next 指向自己检查插入顺序循环链表终止条件改为回到头节点逆置后丢了一半节点没保存 nxtcur-next 被改写逆置循环里必须先用临时变量保存下一个节点删除节点后越界访问删除后指针未置空释放后把相关指针设为 nullptr创建后打印为空头插法顺序和输入相反或头指针没更新检查头指针是否在每一步都赋了新节点值最后分享几个我自己的习惯。写完链表操作先跑空链表和单节点链表这两种边界用例很多问题就藏在这种极端场景里。逆置函数写完会用一个长度 5 的链表演示一遍过程确认头尾节点正确。洛阳的舟山也好洛谷的 B3631 单向链表题也罢这类裸的链表操作题就是用来检验基本功的十分钟内能流畅写完实现才说明真的上手了。链表的核心其实就一句话理解“节点”和“指向”。数据结构书里那一堆术语最后落到代码上无非是谁指着谁、什么时候改指向、改了之后还有没有人能找回原来的节点。把这层关系想透单链表、循环链表、逆置、差集甚至内核链表都是同一套思路在不同场景里的变形。希望这篇能帮你少走弯路。