提到“数据结构”和“链表”这两个词但凡学过编程的人应该都不会陌生。我记得自己刚接触链表的时候总觉得它比数组绕数组一片连续的内存按顺序摆好想访问哪个下标直接就去了多痛快。链表倒好每个节点里除了数据还得塞一个“指向下一个节点的指针”访问某个节点还得从头一个个摸过去乍一看完全是“自找麻烦”。直到后来自己动手写代码、被各种内存问题折磨过才真正理解链表在解决什么问题。这篇文章是“链表”系列的第一篇打算从头把链表的底层逻辑、基本操作、多语言实现、常见坑点全部梳理一遍。写给正在准备考研数据结构的人、期末复习数据结构的人、以及刚入门算法想弄清楚链表到底怎么回事的人。内容尽量用大白话讲清楚原理再配合可以直接抄的代码和实验思路让你看完就能上手自己写一遍。1. 先搞懂链表到底在解决什么问题在动手写代码之前先把链表为什么存在这件事想明白。很多人学的第一个数据结构是数组但数组有几个天生的短板链表恰恰是为补上这些短板而出现的。1.1 数组的甜与痛数组的优点十分直观内存连续、按下标随机访问是O(1)时间。缺点也藏在这一片连续内存里。第一数组的长度在创建时就固定了想动态扩展得手动申请一块更大的内存再拷贝数据。第二在数组中间插入或删除一个元素需要把后面的元素逐个往后挪或往前挪最坏情况是O(n)的时间成本。举一个“排队”的例子。假设有一排人按顺序站好每人都站在固定的编号上这就是数组。突然有人想插队到第3个人后面后面所有人必须往后挪一步腾位置突然中间有人走了后面的人又得补齐空位。这个挪动过程就是O(n)的操作人少还好几百万条数据就非常难受了。1.2 链式存储的核心思想链表换个思路解决问题不要求所有数据都在连续内存里每个数据元素单独占据一个小块这个小块就是“节点”。节点里分为两部分数据域存放实际的数据指针域存放“下一个节点在哪里”的地址。多个节点通过指针域串起来就像一条铁链所以叫链表。生活化类比是“寻宝游戏”你在第1张纸条上得到一条线索线索告诉你第2张纸条藏在衣柜里从衣柜里找到第2张纸条上面又告诉你第3张纸条藏在抽屉里。你想拿到第5张纸条必须从第1张开始一张张找下去因为纸条之间只有单向线索没有“跳跃”能力。这就是单链表。1.3 头指针、头节点、尾节点术语先分清链表里有几个基本概念如果不搞清楚后面写代码很容易懵头指针指向链表第一个节点的指针变量它本身不是节点只是一个“入口地址”。链表操作基本都要从头指针开始。头节点也不是存储实际数据的节点它是链表第一个节点之前附加的一个“哨兵节点”。带头节点的链表比不带头节点的链表在某些操作上更省心尤其是插入和删除的位置正好在头部时。尾节点最后一个节点它的指针域指向NULL表示“后面没有了”。遍历链表的终止条件就是判断指针是否为NULL。注意很多教材和考试题会区分“带头节点”和“不带头节点”。不带头节点的空链表用头指针NULL表示带头节点的空链表是只有一个头节点头节点的next为NULL。这两种模型写法有差异考试踩坑概率极高建议从一开始就选一种作为默认写法我后面代码统一用带头节点的写法。2. 链表家族几个常见形态得认识全很多同学学到链表觉得只有一种“单链表”其实链表是一个家族不同形态对应不同场景。2.1 单链表最基础、没有回头路单链表的每个节点只有一个next指针指向后继节点。只能从头到尾单向遍历想找前一个节点没有存只能重新从头走一遍。单链表的特点是结构最简单面试笔试、考研数据结构里最常考的就是它核心操作包括遍历、插入、删除、逆序、合并。2.2 双向链表多一个前驱指针双向链表每个节点既有next指针也有prev指针节点之间可以双向走动。代价是多一个指针域每个节点多占用一个指针大小的内存但“找前驱”从O(n)变成O(1)。实际工程中双向链表更常用比如Java的LinkedList底层就是双向链表LRU缓存算法也常用双向链表配合哈希表实现。2.3 循环链表尾尾相连绕一圈循环链表把最后一个节点的next指针指向第一个节点形成一个环。单循环链表和双向循环链表都存在。循环链表的好处是从任意位置出发都能遍历整条链表而且尾节点和头节点之间是“打通”的。典型应用有约瑟夫环问题、操作系统的进程调度轮转队列等。2.4 带头节点与不带头节点怎么选我用一个对比表格把带头节点和不带头节点的差异列出来备考的人可以直接背这个表对比维度带头节点不带头节点空链表表示头节点的next为NULL头指针为NULL在头部插入节点不需要修改头指针只需改头节点next需要修改头指针指向新节点在头部删除节点不需要修改头指针需要修改头指针指向新节点代码统一性插入、删除逻辑统一不用单独判断头部情况头部操作必须特殊处理考试/面试常见程度王道、408真题出现比例很高有些教材默认不带头节点我的建议是初学阶段直接用带头节点的单链表练手能省掉很多边界判空头疼问题。理解了带头节点的写法之后再看不带头节点的写法会发现只是头指针处理方式不同而已。3. 单链表核心操作建、查、插、删这一节是整篇文章的核心代码我统一用C语言写原因很简单考研数据结构、期末数据结构实验绝大多数学校默认C语言而且C语言的指针能把链表的“地址跳转”表达得最直白。写完C版再对比Java/Python你会发现思路完全一致只是换了一层语法包装。3.1 节点结构怎么定义C语言里用结构体定义节点#include stdio.h #include stdlib.h typedef struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个节点 } Node; // 创建一个新节点 Node* createNode(int data) { Node* node (Node*)malloc(sizeof(Node)); node-data data; node-next NULL; return node; }注意这里的写法结构体内部要引用自身类型所以必须写struct Node *next不能省略struct关键字。最后用typedef ... Node把struct Node重命名成Node这样后面写代码少几个字。3.2 创建链表头插法和尾插法创建链表有两种最基础的插入策略这也是考试常考的“头插法”和“尾插法”头插法每次新节点都插入到头节点之后。特点是最终链表的节点顺序和输入顺序正好相反可以用来实现链表逆序。Node* createListByHead(int arr[], int n) { Node* head createNode(0); // 头节点不存数据 for (int i 0; i n; i) { Node* newNode createNode(arr[i]); newNode-next head-next; // 新节点先指向原第一个节点 head-next newNode; // 头节点指向新节点 } return head; }演示一下输入1、2、3最终链表从头到尾是3、2、1。因为每个新节点都被插到了头部后插入的反而排前面。尾插法新节点插到链表末尾需要维护一个尾指针tail每插入一个节点就更新尾指针。最终节点顺序和输入顺序一致。Node* createListByTail(int arr[], int n) { Node* head createNode(0); Node* tail head; // 刚开始尾指针指向头节点 for (int i 0; i n; i) { Node* newNode createNode(arr[i]); tail-next newNode; // 尾节点的next指向新节点 tail newNode; // 新节点成为新尾节点 } return head; }头插法有个很实用的小技巧如果拿到一条不带头节点的单链表想倒序一下很多人会新建一条链表再用头插法重新插入一遍空间复杂度O(n)。其实原地逆序法只需要三个指针就能完成后面第4节会详细讲。3.3 遍历链表打印每个节点的数据链表的遍历逻辑是所有操作的基础。代码很短但考察点很细void printList(Node* head) { Node* p head-next; // 跳过不存数据的头节点 while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }这里有两个关键点。第一遍历的起点如果带头节点必须从head-next开始否则头节点的数据会被打印出来。第二循环条件用p ! NULL时最后一个节点被处理完以后p变成NULL才退出。如果你写的是p-next ! NULL那么最后一个节点不会进入循环体等于漏处理一个节点。这个差异就是期末考试填空题和面试手写代码最爱挖的坑。3.4 插入节点核心原则是“先连后断”单链表插入有三种情况头节点后插入、中间插入、尾节点后插入。其实核心套路一模一样我先给出通用代码// 在节点pos之后插入新节点newNode void insertAfter(Node* pos, Node* newNode) { newNode-next pos-next; // 第一步新节点先指向pos的后继 pos-next newNode; // 第二步pos的next指向新节点 }这个两行代码的fun顺序极其重要很多人第一次写会写成pos-next newNode; newNode-next pos-next;那就有意思了先让pos的next指向newNode结果newNode-next pos-next就等于newNode-next newNode自己指向自己链表就断了。记住口诀“先连后断”先把新节点和后面的节点连上再把前驱节点的指针改过来。这和生活中换链条是一个道理你得先把新链环扣好再接上旧链环不能先把旧链环卸下来再装新的那样链条就散了。3.5 删除节点必须先找到前驱单链表删除节点没有太聪明的办法因为要知道被删节点的前驱是谁才能把前驱的next指向被删节点的后继。但单链表节点没存前驱信息所以只能从头遍历找到待删除节点的前驱节点。删除节点的通用步骤从head开始遍历找到满足p-next target的节点pp就是要删除节点的前驱。让p-next target-next跳过target。释放target节点的内存。对应代码void deleteNode(Node* head, int value) { Node* p head; while (p-next ! NULL p-next-data ! value) { p p-next; } if (p-next NULL) { printf(没有找到值为%d的节点\n, value); return; } Node* target p-next; p-next target-next; // 跳过待删除节点 free(target); // 释放内存 }如果删除的是不带头节点的链表的第一个节点情况就特殊了必须直接修改头指针head head-next。带头节点的写法能避免这种特殊分支判断这也是我坚持带头节点写法的原因。3.6 删除链表释放全部节点防内存泄漏很多同学创建了链表却忘了最后释放C语言下后果就是内存泄漏。完整的释放函数是void destroyList(Node* head) { Node* p head; while (p ! NULL) { Node* next p-next; // 先记下下一个节点 free(p); // 再释放当前节点 p next; } }注意必须先保存p-next再free(p)因为free之后当前节点的内存已经被回收再访问p-next是非法读取。4. 进阶操作逆序、合并有序链表、快慢指针掌握了基本操作以后接着往下走这部分是考研数据结构、算法面试里的高频考点也是“链表1”里最能体现思维深度的内容。4.1 单链表逆序三指针迭代法单链表逆序的基本思路是“原地反转箭头方向”。用三个指针prev指向当前节点的前驱current指向当前节点next保存当前节点的后继。每走一步就把current-next从后继改成前驱。Node* reverseList(Node* head) { Node* prev NULL; Node* current head; while (current ! NULL) { Node* next current-next; // 先保存后继 current-next prev; // 箭头反转 prev current; // 前驱后移 current next; // 当前节点后移 } return prev; // prev最终指向原链表的尾节点也就是新链表头 }这个代码是对不带头节点链表操作的如果传入的是带头节点链表返回的是新的第一个真实节点使用时要注意。我建议考试时直接画一个三个节点的小链表在纸上手动模拟每轮循环中三个指针的变化比背代码可靠得多。逆序操作的时间复杂度O(n)空间复杂度O(1)不需要申请额外空间这也是面试官爱考它的原因。4.2 合并两个有序的单链表“合并两个有序的单链表”也是高频考题热度词列表里专门有它。两条链表都是升序排列要求合并后依然有序。思路是双指针逐一比较谁小接谁Node* mergeTwoLists(Node* head1, Node* head2) { Node dummy; // 栈上哨兵节点避免处理头指针 Node* tail dummy; Node* p1 head1; Node* p2 head2; while (p1 ! NULL p2 ! NULL) { if (p1-data p2-data) { tail-next p1; p1 p1-next; } else { tail-next p2; p2 p2-next; } tail tail-next; } // 剩下没遍历完的部分直接接上 tail-next (p1 ! NULL) ? p1 : p2; return dummy.next; }合并的时间复杂度O(nm)空间复杂度O(1)只用常数个指针就完成了。除了迭代法也可以用递归递归代码更短但理解门槛更高面试时迭代法往往更稳妥。4.3 快慢指针找中间节点、倒数第k个节点链表不能随机访问想找中间节点如果“先数长度再走一半”需要两次遍历。快慢指针只需要一次快指针每次走两步慢指针每次走一步。快指针到末尾时慢指针正好到中间。找中间节点的代码Node* findMiddle(Node* head) { Node* slow head; Node* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }找倒数第k个节点同理快指针先走k步然后快慢指针一起走快指针走到空时慢指针就是倒数第k个节点。快慢指针在链表类算法题里的出镜率极高值得好好掌握。5. 多语言实现对比C、C、Java、Python链表的思路是同一套但不同语言写出来的代码风格差异很大。我把自己写过的各语言版本心得整理了一下方便不同技术栈的人参考。5.1 C语言结构体指针的经典组合C语言里链表是最原汁原味的因为指针就是地址next指针直观地保存了下一个节点的地址调试器里你能直接看到地址值。但C语言的问题是没有内存自动回收创建节点的malloc和删除节点的free必须自己配对管理漏一个free就是内存泄漏多free一次就是非法操作。5.2 C用new和delete管理还能玩引用C写链表和C很像节点通常用struct定义但构造方式更简洁struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; Node* head new Node(0); Node* newNode new Node(42);区别在于C可以用构造函数初始化节点创建操作一行搞定。另外C结构体默认访问权限是public直接访问成员没问题。C里链表还可以用std::list直接用现成容器但在考研手写题里必须能手写实现。5.3 Java引用传递模拟指针Java没有指针概念但对象引用本质上就是一个“安全的指针”。Java写链表节点class Node { int data; Node next; Node(int data) { this.data data; this.next null; } }Java不用手动管理内存new出来的节点没引用后由垃圾回收器自动处理。但这也意味着链表删除节点时只需要断开引用并不需要也不能手动释放内存。Java的LinkedList底层就是双向链表面试题却常让你自己手写单向链表实现。5.4 Python最简洁但底层是对象引用Python写链表表面看最简单因为不用写结构体和指针语法class Node: def __init__(self, data): self.data data self.next None但Python的每个变量都是对象引用next保存的是“对下一个Node对象的引用”。Python里创建节点不需要手动分配/释放内存语言层面全部代劳了但代价是链表节点的内存开销比C大很多——每个Node对象都有完整对象头。Python单链表逆序的写法很简洁def reverse_list(head): prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev5.5 各语言对比速查表语言节点定义方式内存管理代码复杂度适用场景Cstruct 指针malloc/free手动管理高但最贴近底层考研笔试、嵌入式、操作系统内核Cstruct 指针/引用new/delete管理中等算法竞赛、工程开发Javaclass 对象引用自动垃圾回收中低面试算法题、Java开发Pythonclass 对象引用自动垃圾回收低快速原型、学习概念顺带提一句网上经常有人把“Pandas里的DataFrame/Series”也叫“数据结构”这和计算机里的“链表”完全是两回事。当时我看到有很多人在搜“pandas数据结构创建”那是数据分析领域的DataFrame和Series属于另一个方向的知识。学链表时如果混淆了这两类概念思路会乱这里说清楚。6. 实战应用与避坑总结学了链表很多人第一反应是“这有什么用”。其实链表在工程里无处不在尤其在嵌入式领域和基础软件领域是绕不开的核心技能。6.1 嵌入式里链表怎么用嵌入式系统中链表最常见的用途包括任务队列管理、按键扫描缓冲、内存池管理等。嵌入式链表和桌面程序的链表有个重要区别不能频繁使用动态内存分配因为嵌入式环境内存小、分配不稳定会引发系统风险。所以嵌入式里常常预先创建一个静态节点池再手动管理节点分配和回收。一个嵌入式链表代码示例的典型结构是typedef struct os_node { struct os_node *next; void *data; } os_node_t; os_node_t node_pool[64]; // 固定大小的节点池 os_node_t *free_list; // 空闲链表每次需要节点时从free_list取一个用完还回去而不是调用malloc/free。这种静态分配方式在实时系统中非常常见时间成本可确定内存碎片也可控。如果在项目里见过这种写法就明白为什么链表绝不是“纸上谈兵”。6.2 考研和期末复习链表的正确姿势考研数据结构里链表是必考内容408统考经常把链表操作和动态规划、排序结合出综合题。期末考试的实验报告也总少不了“单链表的基本操作实验”。结合我自己的备考经验复习建议如下必须能徒手写创建头插法、尾插法、遍历、插入、删除、逆序、合并有序链表这六种操作应当形成肌肉记忆。必须理解复杂度单链表的查找、插入、删除在已知位置和未知位置时时间复杂度不同这个细节考试很喜欢考。必须会画图遇到指针操作的题先在草稿纸上画链表标出prev、current、next再看代码逻辑效率远高于空想。重视做题练手洛谷B3631单向链表是很经典的练手题能帮你把链表的插入、删除、查询操作落实到真实场景里。另外《大话数据结构》和《数据结构与算法分析:Java语言描述》这两本书也适合对照阅读前者轻松入门后者Java版适合代码级理解。6.3 常见问题与排查技巧速查表链表代码的调试往往是新手最头疼的部分。把常见的报错和问题整理成表可以直接对照排查问题现象可能原因排查与修复访问空指针导致程序崩溃对NULL节点继续访问-data或-next遍历循环里加判空删除节点后不要继续用旧指针打印链表时死循环、程序卡死链表成环尾节点next没有置NULL检查创建和插入时新节点next是否初始化为NULL打印出来少一个节点循环条件写成了p-next ! NULL改为p ! NULL插入后链表顺序乱了插入两行代码顺序写反先连新节点与后继再改前驱next删除头节点后链表找不到没有更新头指针不带头节点的链表删除头部节点时必须headhead-next程序跑完内存没释放创建链表后忘记调用销毁函数写完创建代码马上写destroyList养成配对习惯释放内存后崩溃free后继续访问已释放节点释放后立即把指针置为NULL即“悬空指针”或“悬挂指针”6.4 调试链表的两个核心技巧最后分享两个我实际调试链表时觉得最好用的方法。第一个是“打印大法”。在关键步骤打印当前节点的地址和数据比如遍历时打印p的值和p-data插入后打印整条链表能非常直观地看出指针指向是否出了问题。不要觉得打印低级它在调试链表时效率真的高。第二个是“画小样例”。想不清指针变化时拿纸笔把3个节点的链表画出来节点画成方框指针画成箭头一步一步模拟代码执行。我面试手撕链表题之前也是先在草稿纸上画好图再写代码错误率低很多。链表这个主题想一次讲完内容太多这篇以基础为主——从数组的痛点讲起梳理了链表的核心定义、链表家族的主要形态、单链表的基本操作、逆序和合并等进阶操作以及多语言实现差异和常见问题排查。掌握了这些链表的基础才算真正打牢。我个人实际操作中的体会是学链表最大的障碍不是代码语法而是“心里没有图”。只要脑子里始终有“节点方框加箭头”的画面任何链表操作都不难。下一篇可以再深入聊一聊双向链表的实战、循环链表实现约瑟夫环、以及链表排序等内容不过先把这篇里的代码亲手敲一遍比看多少遍教程都管用。