我每次带新人或者面试只要问链表看到的反应基本就两种。一种人觉得这是数据结构课本里最老实的章节随手就能写出插入删除另一种人一上手就踩边界空链表删节点直接崩。说实话C里的单链表和双链表实现难度不在于算法有多绕而在于指针的每一步都要求你清楚知道它指向哪。这篇内容围绕C实现单链表和双链表展开从节点定义、基本操作、边界条件到循环链表的扩展和工程选型适合刚学完指针准备动手写链表的人也适合面试前系统性自查一遍。1. 为什么还要自己写链表从内存布局到工程落地1.1 数组的短板与链表的诞生逻辑数组是一种“连续内存”结构随机访问是O(1)这件事是它的最大优点同时也是它最大的束缚。你想在数组中间插入一个元素需要把后面所有元素整体后移想删除一个元素又得把后面所有元素整体前移。平均复杂度O(n)数据量一大就顶不住。链表解决的是“不连续也能按顺序访问”的问题。它把数据本身和“下一个元素在哪里”的信息打包成一个节点每个节点通过指针连接下一个节点。如果你只需要遍历访问不在乎随机访问那在插入删除频繁的场景里链表比数组直观很多。我习惯用一个类比数组像电影院里连排的座位你想在中间塞一个人整排人都得站起来挪链表像一列火车每节车厢里除了乘客还写着下一节车厢的编号你可以随时在两节车厢之间挂一节新的只需要改前后两节车厢的门牌号。但这里的代价也很明显每个节点除了存数据还要额外存一个指针。64位系统上指针占8字节如果你存的只是int那内存开销几乎翻倍。所以链表不是万能银弹它的适用场景是“插入删除多、随机访问少、对内存开销有心理预期”的地方。搞清楚这个前提后面再看实现细节思路就顺了。1.2 自研链表与std::list的真实分工C标准库里已经有std::list双向链表和std::forward_list单向链表为什么还要自己写这问题我常被问到。首先学习阶段自己写一遍是必要的。很多事情“用起来会”和“实现过”是两码事。链表是理解指针语义、动态内存分配和复杂边界条件的最佳载体之一。不用std::list你永远不会知道它内部为什么要带一个哨兵节点也体会不到为什么erase一个迭代器是O(1)。其次确实存在不适合用STL的环境。嵌入式开发里可能关掉了异常支持竞赛里可能要求手写稳定又迷你的容器还有一些对性能要求极端的项目需要自定义内存池或者无锁结构。这些场景下标准库容器反而成了束缚。最后面试手写题也是现实需求。字节、阿里这类公司考察手写链表不单是考察你是否背过反转链表而是想看你能否处理好空表、单节点、头节点删除这些边界情况以及写出来的代码是否有内存泄漏风险。所以这篇文章的主线不是“让你以后都别用std::list了”而是“先把单链表、双链表自己实现一遍再回头看标准库怎么优化这些痛点”。通了之后你会更容易读懂STL源码也更容易在实际工程里做出恰当选择。2. 节点与链表骨架struct裸指针的取舍以及一个容易漏的资源问题2.1 节点类设计struct 裸指针为什么是主流教学选择定义链表的第一步是节点。几乎所有教材都使用这种写法struct Node { int val; Node* next; Node(int v, Node* n nullptr) : val(v), next(n) {} };这里用struct而不是class因为节点本身就是一个简单的数据聚合不需要封装私有成员和接口。用裸指针Node*而不是std::shared_ptrNode则是一个经过权衡的选择。很多初学者会问用shared_ptr不是能自动释放内存吗我不能说这个思路完全错误但在链表场景里它问题很多。第一如果链表里有环比如循环链表shared_ptr的引用计数无法归零会出现循环引用内存照样泄漏。第二shared_ptr的引用计数是原子操作每次指针赋值都要加锁解锁性能损耗明显。链表本身就是靠频繁改指针维持效率的数据结构引入智能指针等于给关键路径额外套上了枷锁。第三标准库的std::list内部实现用的也是裸指针加分配器不是shared_ptr这说明裸指针在链表场景下依然是工程上的主流选择。所以学习阶段我建议老老实实用裸指针自己管理生命周期。等你真正理解了释放时机再去考虑用智能指针做局部优化也不迟。节点类加上构造函数之后创建节点就方便了new Node(5, head)可以直接完成赋值和指定后继两步操作。2.2 析构函数与递归释放的隐患链表的资源管理是最大的坑之一尤其是析构。很多人第一次写链表类析构函数会写成这样~LinkedList() { if (head) delete head; // 危险写法 }如果Node的析构函数是默认的那delete head只会释放第一个节点后面的节点全部泄漏。更糟糕的一种写法是给Node加一个递归析构~Node() { if (next) delete next; }表面上看挺“聪明”释放当前节点时自动往后递归释放。但链表一旦很长比如五万个节点递归调用深度就会很恐怖直接爆栈。正确做法是迭代释放每次先把下一个节点地址存下来再删除当前节点~LinkedList() { Node* cur head; while (cur) { Node* next cur-next; delete cur; cur next; } }这里有个细节必须强调delete cur之后cur-next已经是未定义行为因为那块内存已经被释放了。所以一定要在delete之前先把next存下来。我在代码审查里见过无数次这种顺序错误不是释放错而是释放之后还去读旧内存导致程序偶发崩溃。这个资源管理的问题在双链表里同样存在而且因为多了个prev指针很多人会想“用prev从尾巴往前释放”但实际没必要记住一条准则释放链表时只认next不要想着反向遍历逻辑越简单越不容易出错。3. 单链表核心操作边界条件比算法本身更重要3.1 头插与尾插的实现细节单链表的插入操作分头插和尾插两种两者难度完全不同。头插的实现非常简单因为新节点直接成为新的头void push_front(int v) { head new Node(v, head); }这行代码的妙处在于new Node(v, head)先把旧的头节点指针作为新节点的next然后用新节点覆盖head。顺序如果反过来比如先改head再new旧链表就找不到了。尾插稍微麻烦一点因为要先走到链表的最后一个节点然后把新节点挂在它的next上void push_back(int v) { if (!head) { head new Node(v); return; } Node* cur head; while (cur-next) { cur cur-next; } cur-next new Node(v); }尾插最容易犯的错误就是忘记判空。如果head是空指针直接执行head-next就会解引用空指针崩溃。这个判断藏在代码最前面看起来不起眼却是所有链表算法里最常见的崩溃原因。我自己的习惯是任何涉及“找最后一个节点”的操作写完后先拿空表测一遍再拿单节点表测一遍跑通再继续。另外在工程里尾插有个优化空间如果尾插频繁可以额外维护一个tail指针让尾插变成O(1)。代价是删除节点或者反转链表时需要同步更新tail。这个取舍在实现LRU缓存这类场景里经常遇到。3.2 删除节点时前驱指针为什么是命根子单链表删除的难点不在于找到要删的节点而在于如何跨越它。因为单链表的节点只有向后的指针想删除某个节点必须知道它的前驱是谁让前驱的next直接指向被删节点的后继。如果找不到前驱被删节点就断链了。bool erase(int v) { Node* prev nullptr; Node* cur head; while (cur cur-val ! v) { prev cur; cur cur-next; } if (!cur) return false; if (prev) { prev-next cur-next; } else { head cur-next; } delete cur; return true; }这里有两个边界情况很容易被忽视。第一删除头节点时prev是nullptr这时候必须直接修改head如果不判断执行prev-next就会崩溃。第二被删节点是最后一个节点时cur-next是nullptr把它赋给prev-next是没有问题的因为这正好表示链表结束。我在面试里见过不少人能写出“找到待删节点”的循环却总在最后一步犹豫。其实关键就一句话删除节点的本质是“绕过它”而不是“清空它”。你只需要让前驱的next指向它的后继然后释放它本身。这条逻辑想清楚所有删除场景都通用。3.3 反转链表的三指针法反转链表是手写题里出现频率最高的一个甚至可以算“链表试金石”。迭代版的三指针写法如下Node* reverse(Node* head) { Node* prev nullptr; Node* cur head; while (cur) { Node* next cur-next; cur-next prev; prev cur; cur next; } return prev; }新手最容易卡住的地方是不理解为什么需要一个额外的next指针。原因很简单cur-next prev这一步会让cur丢掉原来指向后继的指针如果不先把next存起来循环就无法继续。整个过程可以理解为三个指针在链条上“滚动前进”prev是已经逆好的部分cur是当前正在处理的节点next是还没处理的部分。我一般不建议死背代码而是建议自己在纸上画三个方框模拟一遍“取头、换向、平移”的过程。画个五六遍之后代码自然就记牢了而且以后改写成递归版本也只是换个写法的事。4. 双链表从单向前驱到双向对称的设计升级4.1 双链表的节点和插入逻辑双链表和单链表的本质区别就是节点多了一个prev指针指向它的前驱节点struct DNode { int val; DNode* prev; DNode* next; DNode(int v) : val(v), prev(nullptr), next(nullptr) {} };别小看这个prev它把很多操作从“需要额外记录前驱”变成“直接拿到前驱”代价是每个节点多花8字节内存且插入和删除时多改两条指针。在双链表中把新节点node插入到p后面逻辑是这样void insertAfter(DNode* p, int v) { DNode* node new DNode(v); node-next p-next; node-prev p; if (p-next) { p-next-prev node; } p-next node; }这里顺序特别关键先让新节点建立和前后邻居的完整连接再改旧邻居的指针。如果你先执行p-next node那么原来的后继节点就找不到了p-next-prev node这步就会操作到新节点自身链就断了。我总结的口诀是“先连新再断旧”。如果插入位置是尾部p-next是nullptr这时候直接跳过p-next-prev node即可。所以这里判空不是可选项是所有场景下的必需品。4.2 删除操作为什么比单链表更“自包含”双链表最漂亮的地方在删除。删除一个节点p你不需要从头遍历找前驱因为p-prev直接就告诉你了void eraseNode(DNode* p) { p-prev-next p-next; if (p-next) { p-next-prev p-prev; } delete p; }这段代码看起来简单但它背后体现了一个核心设计差异单链表删除必须知道前驱删除操作自始至终需要额外指针双链表删除自带全部上下文只要给你一个有效节点指针它就能自己脱离链表。在std::list里erase(iterator)之所以是O(1)就是因为它内部是双向链表迭代器直接持有节点指针删除不需要查找。这也是为什么凡是需要“给定位置快速删除”的场景比如LRU缓存淘汰、有序列表维护工程上几乎都会选择双向链表或带prev指针的结构。单向链表虽然更省内存但在这种需求面前无计可施。我见过一个很典型的错误删除头节点时直接调用eraseNode(head)但如果链表只有一个节点删除之后head依然指向已经被释放的内存。所以双链表的删除接口通常要配合链表对象来管理头指针或者在删除后手动置空头指针。别把“节点自己脱离链表”和“链表头部正确更新”混为一谈。4.3 哨兵节点哑结点能把代码简化到什么程度解决各种边界问题一个非常实用的技巧是引入哨兵节点也叫哑结点。所谓哨兵就是一个不存储业务数据的特殊节点它始终存在作为链表的头节点真正的业务节点都排在它后面。class DoublyList { DNode dummy; public: DoublyList() { dummy.prev dummy; dummy.next dummy; } };这里有个经典设计让dummy.next和dummy.prev都指向自己构成一个环形双向链表。这样一来头插和尾插都变成了“在dummy后面或前面插入”代码逻辑完全对称空表和非空表的差异也消失了。删除任何节点都不需要判断prev是否为nullptr因为dummy永远存在。这个设计不是我的独创很多标准库的实现就是类似思路。我自己在实现LRU缓存时也用过这种结构代码简洁程度确实提升了一个档次。不过要提醒一下哨兵节点在多线程环境下需要考虑并发访问因为它是一个共享的可变状态。如果只是为了学习链表先把它用熟能够大大降低边界条件的排查成本。5. 循环链表与实际调试从约瑟夫问题到内存检测5.1 循环单链表的结构与遍历终止条件循环单链表是在单链表的基础上把尾节点的next指向头节点形成一个环。它的典型应用包括约瑟夫问题、任务轮询、时间片轮转以及需要“转一圈又回到起点”的场景。构造一个循环单链表通常这样操作先按正常方式构建单链表最后把尾节点的next指向head。遍历的时候终止条件就变了Node* cur head; do { process(cur-val); cur cur-next; } while (cur ! head);这里必须用do-while不能用while。如果一开始就判断cur ! head那循环体一次都执行不了。我第一次写循环链表就栽在这里用while跑了半天一个节点都没输出。循环链表删除节点时有一点容易出错删除的是唯一一个节点时指针会把链表变成“头尾相连”的异常状态甚至可能自己指向自己。所以删除后如果链表为空要记得把头指针置空否则后续操作都会陷入死循环。这也是为什么调试循环链表时我第一步总是检查“是否还能回到起点”而不是检查某个节点的值。5.2 交换相邻节点一个检验指针熟练度的场景交换相邻节点是一个非常好的自测题目它的难度比反转链表更接近真实工程因为你既要改这两个节点的连接又不能让前后节点丢失。以带头结点的单链表为例void swapAdjacent(Node* dummy) { Node* p dummy; while (p-next p-next-next) { Node* a p-next; Node* b a-next; a-next b-next; b-next a; p-next b; p a; } }这段代码的核心思路是把交换操作看成“在p后面重新接上两个节点”而不是“把a和b的位置换一下”。a-next b-next让a先连接到原来b的后继b-next a让b指向a最后p-next b把整段重新挂到链表主体上。最容易犯的错误是最后p p-next这样下一轮会从b开始处理破坏了奇偶配对的预期。正确写法是p a因为下一对相邻节点应该从原来的a之后开始。这个细节很多人在白板面试时想不通建议直接在代码里跑一遍打印每次循环后的链表很快就有感觉。5.3 调试链表的实用手段链表出问题时的现象往往非常迷惑程序崩溃、死循环、输出乱序查半天不知道哪里断了。我总结了一套简单有效的手段。第一写一个打印函数。不要只打印当前节点的值还要打印节点地址和next地址比如printf(%p - %p, val%d\n, cur, cur-next, cur-val)。这能直接看出哪个节点的next指向了意外位置。怀疑循环链表死循环时打印超过节点总数的次数就是明显的“转圈”信号。第二使用内存检测工具。Linux下用ValgrindmacOS和Windows下可以用AddressSanitizer。一个简单的编译参数g -fsanitizeaddress -g main.cpp -o mainASan能直接定位到“释放后使用”和“内存泄漏”的具体代码行比肉眼盯代码高效太多。我自己的习惯是一开始就开ASan写链表避免问题积累到最后才发现。第三利用断点检查空指针。很多链表崩溃都是对nullptr解引用在关键的取值操作前加条件断点比如cur nullptr能快速定位到是哪个循环把指针走到了尽头。相比暴力打印用断言assert(cur ! nullptr)更符合工程习惯一崩就知道责任在哪一行。6. 性能实测与工程建议什么时候用自研什么时候直接用STL6.1 自研链表与STL容器的性能对比为了对链表有一个直观认知我把自研单链表、双链表、std::forward_list、std::list放在一起列个对比特性自研单链表自研双链表std::forward_liststd::list每个节点额外内存1个指针8B2个指针16B1个指针 分配器开销2个指针 分配器开销头插复杂度O(1)O(1)O(1)O(1)尾插复杂度无尾指针O(n)O(1)有尾指针则O(1)不支持O(1)删除指定位置需要前驱O(1)需要前驱O(1)随机访问不支持不支持不支持不支持异常安全需自写需自写标准库内置标准库内置代码规模约100行约150行直接使用直接使用这里的差异很有意思自研双链表如果也维护尾指针尾插一样能做到O(1)。而std::list内部一般就是带哨兵节点的循环双向链表所以它的插入删除都是O(1)。如果你需要的只是“顺序容器 频繁在两端插删”其实std::deque反而更合适它支持随机访问两端操作常数级内存连续度高对缓存友好。说到缓存友好性这是链表对比数组时最容易被忽略的一点。数组元素在内存中连续排列遍历时的CPU缓存命中率极高链表的节点分散在堆上每次跳转都可能触发缓存未命中。数据量上万之后链表的遍历性能可能比数组差一个数量级。所以“链表插入快”这个优点在遍历密集型场景里会被缓存劣势抵消。6.2 工程落地的选择建议给不同需求的人一个相对清晰的选择建议如果是为了学习务必手写一遍单链表和双链表包括带头结点和不带头结点两种版本再实现一遍反转和交换相邻节点。这个过程的收获远大于直接调用STL容器。如果是为了生产项目优先使用std::list或std::forward_list。标准库容器经过了严格测试异常安全有保障迭代器设计也完善。自己写的链表在没有专门测试的情况下很难保证所有边界情况不出问题。如果是为了嵌入式或极端性能场景建议先明确你真正需要哪些操作再考虑手写。手写时最好配合内存池避免频繁new/delete带来的性能抖动同时定义好“插入失败、分配失败”时的处理策略而不是依赖全局的new抛异常。我个人在实际操作中的体会是链表这东西写起来容易调试起来磨人。边界情况永远比想象的多空表、单节点、头节点删除、尾节点删除、删除后链表为空每一个都值得单独测试一遍。我现在每次写完链表都会用一组固定用例去验证空链表插入和删除、单节点链表删除、删除头节点、删除尾节点、反转空表、双链表删除最后一个节点。这组不起眼的用例能帮我省下大量排查时间也分享给你。
