单链表和双链表应该是C数据结构里最容易被低估的两个东西。拿“C实现单链表和双链表”这个题目来说表面看就是定义一个Node结构体、new几个对象、把next指针来回拨弄两下可真等你拿起键盘段错误、double free、链表断成两截这些问题会轮番教你做人。我从学生时代写链表作业到工作后在编辑器插件里手写LRU缓存踩过的坑足够再写一篇长文。这篇文章就把单链表、双链表从原理、完整代码到常见崩溃场景一次讲透适合正在学数据结构的新手也适合准备手写链表面试的开发者。1. 动手前先想清楚链表解决什么问题单链和双链差在哪1.1 先聊价值数组做不到的事链表凭什么做到链表解决的问题本质上就一句话在内存不连续的情况下仍然能让数据有序地串起来。数组是连续的内存优点是随机访问O(1)缺点是中间插入或删除一个元素需要整体搬移平均O(n)。链表不同它靠每个节点里的指针找到下一个节点插入删除时只要改相邻节点的指针指向不需要搬动其他数据。这就像小朋友手拉手排队老师要把一个人从队伍中间抽走只需要让他左右两个小朋友重新牵手就行后面的人不需要挪位置。但链表也不是免费的午餐。最大的劣势是访问第k个节点必须从头遍历O(n)起步而且指针跟着地址到处跳CPU缓存命中率远不如数组。所以实际项目里链表从来都不是为了“看起来高级”而是为了具体场景频繁在中间插入删除、数据量不确定、需要把散落在堆上的内存组织起来。像哈希表解决冲突的链地址法底层就是链表内存分配器管理空闲块、任务调度器的就绪队列也经常是链表结构。换句话说选择链表不是因为数组不好是因为你的操作模式决定了随机访问不是刚需而插入删除不能忍受O(n)的搬移成本。1.2 单链表、双链表、循环链表到底差在哪三者可以放一张表对比类型节点结构遍历方式删除已知节点内存开销实现复杂度单链表data next只能从头往后需要从头找前驱O(n)每个节点1个指针最低双链表data prev next可双向遍历直接通过prevO(1)每个节点2个指针中等循环单链表data next尾节点连回头部可绕圈遍历同上注意终止条件1个指针略高判断依据很简单如果业务里经常需要从任意节点倒回去或者要频繁删除当前已知节点双链表就是对的如果主线是单向推进单链表少一个指针就少一份出错概率。循环链表不是第三种独立实现它是在单链表或双链表基础上把尾部接回头部主要解决“绕圈处理”的场景比如约瑟夫环、播放列表循环、时间片轮转调度。后面我会专门讲怎么改。1.3 为什么用C练链表内存管理才是重头戏用C语言写链表重点全在指针上谁分配谁释放全凭自觉。用C写链表除了指针操作还会逼着你面对另外三个问题模板、析构、拷贝与移动语义。模板让链表可以存任意类型不用为int写一遍、为string再写一遍析构函数负责自动清空所有节点这是RAII思想在数据结构里最直接的体现拷贝构造必须做深拷贝移动构造要转移所有权这正好把C的“五法则”练透。很多初学者跟着网上代码抄一遍能跑但换个类型、加个拷贝就崩根本原因就是只记住了next怎么指没理解C对象的生命周期。这也是为什么“为什么我用C实现单链表”比“用C实现单链表”更容易翻车——语言给你的自动机制越多你越需要知道它在背后帮你做了什么。2. 单链表的C实现核心操作拆解开来看2.1 节点与类骨架一个模板类搞定任意类型单链表的核心单位是节点我习惯把节点结构体嵌套在链表类内部这样外部完全不需要关心Node长什么样只需要操作链表对象。template typename T class SingleLinkedList { private: struct Node { T data; Node* next; explicit Node(const T val) : data(val), next(nullptr) {} }; Node* head_ nullptr; // 不带头节点的写法空链表就是 nullptr size_t size_ 0; public: SingleLinkedList() default; ~SingleLinkedList() { clear(); } void push_front(const T val); void push_back(const T val); bool insert(size_t index, const T val); bool erase(size_t index); bool remove(const T val); Node* find(const T val) const; void clear(); void reverse(); size_t size() const { return size_; } bool empty() const { return size_ 0; } void print() const; };这里有两个值得注意的点。第一Node的构造函数里必须把next初始化为nullptr否则就是个野指针后续操作会在你根本想不到的地方崩溃。第二模板类的成员函数实现最好和类定义放在同一个头文件里或者放到一个.impl.h文件再在头文件末尾include进来不要像普通类那样把实现丢到.cpp里否则链接阶段会报undefined reference。这是C模板实例化机制决定的不算冷门但确实很多人第一轮编译就被卡在这。2.2 头插、尾插与按位置插入指针连接的顺序是生命线头插是最简单的操作新节点先指向当前头节点然后更新head_三步完成template typename T void SingleLinkedListT::push_front(const T val) { Node* newNode new Node(val); newNode-next head_; head_ newNode; size_; }尾插就要先找到最后一个节点。如果链表为空直接让head_指向新节点如果不为空就从头遍历到next为nullptr的那个节点再让它指向新节点template typename T void SingleLinkedListT::push_back(const T val) { Node* newNode new Node(val); if (!head_) { head_ newNode; size_; return; } Node* cur head_; while (cur-next) { cur cur-next; } cur-next newNode; size_; }按位置插入稍有门槛重点是先找前驱节点。我提供两个版本先看常规写法template typename T bool SingleLinkedListT::insert(size_t index, const T val) { if (index size_) return false; if (index 0) { push_front(val); return true; } Node* prevNode head_; for (size_t i 0; i index - 1; i) { prevNode prevNode-next; } Node* newNode new Node(val); newNode-next prevNode-next; prevNode-next newNode; size_; return true; }注意连接顺序先把新节点的next指向prevNode原来的后继再把prevNode的next指向新节点。顺序一旦反过来prevNode-next会被先覆盖后面的节点就全丢了。这是我见过写链表最容易犯的错误没有之一。再给一个基于二级指针的版本很多开源代码里会看到这种写法template typename T bool SingleLinkedListT::insert2(size_t index, const T val) { if (index size_) return false; Node** pp head_; for (size_t i 0; i index; i) { pp (*pp)-next; } Node* newNode new Node(val); newNode-next *pp; *pp newNode; size_; return true; }二级指针的好处是不用区分头插还是中间插也不用维护prevNode这个变量。pp始终指向“下一个节点指针的地址”循环结束后*pp就是要插入位置的原节点统一处理。这种技巧第一次看可能觉得绕但理解了以后写删除、反转都可以用属于值得花时间吃透的C指针应用。2.3 查找、删除与清空先保存再释放永远不要倒着来查找很简单从头遍历比对template typename T typename SingleLinkedListT::Node* SingleLinkedListT::find(const T val) const { Node* cur head_; while (cur) { if (cur-data val) return cur; cur cur-next; } return nullptr; }删除指定位置的节点核心还是找前驱。删除首节点时因为head_本身要更新需要单独判断。这里我直接用二级指针版本你会发现比普通写法清爽很多template typename T bool SingleLinkedListT::remove(const T val) { Node** pp head_; while (*pp (*pp)-data ! val) { pp (*pp)-next; } if (!*pp) return false; Node* toDelete *pp; *pp toDelete-next; // 先把链表结构改好 delete toDelete; // 再释放节点 --size_; return true; }二级指针版本里循环退出时*pp就是待删除节点pp是“指向前一个节点next成员”的地址。改链表和释放的顺序同样重要先把前驱的next指向待删节点的后继再delete节点本身。很多人习惯先delete再想着把链表接回去结果访问到已释放的内存轻则脏数据重则段错误。clear清理整个链表同样必须先把next保存下来再deletetemplate typename T void SingleLinkedListT::clear() { Node* cur head_; while (cur) { Node* next cur-next; delete cur; cur next; } head_ nullptr; size_ 0; }所以链表操作的黄金法则其实就一条任何需要释放节点的操作都是先改连接再释放释放之后绝对不要再碰节点的任何成员。反复背这句话能省下一大半调试时间。2.4 反转链表面试高频题三种思路任选反转单链表几乎是面试必考也是理解指针操作最好的练习题。最经典的是迭代三指针法template typename T void SingleLinkedListT::reverse() { Node* prev nullptr; Node* cur head_; while (cur) { Node* next cur-next; // 先保存后继 cur-next prev; // 当前节点指向前一个 prev cur; // 前驱前移 cur next; // 当前节点后移 } head_ prev; // 原尾节点变成新头节点 }核心就一句话每次都要先把cur-next保存到临时变量再改cur-next。改完之后再往后走。如果顺序反了cur-next一改原来的后继就找不回来了链表当场断掉。递归版核心思路是把后面子链先反转再把当前节点接上去template typename T typename SingleLinkedListT::Node* reverseRecursive(Node* node) { if (!node || !node-next) return node; Node* newHead reverseRecursive(node-next); node-next-next node; node-next nullptr; return newHead; }这套递归理解起来稍微烧脑但画一下调用栈就能明白递归走到尾节点后开始回溯每次让当前节点的后继反过来指向自己。链表很长时递归会占调用栈工程里优先用迭代版。还有一种头插法思路遍历原链表把每个节点拆下来头插到新链表里效果等效于反转。思考方向不同实现上需要额外维护一条新链面试时提一嘴作为对比会显得你理解更全面。3. 双链表的C实现双向遍历与指针连接的坑3.1 双链表节点结构多一个prev解决的不只是回退双链表比单链表就多了一个prev指针但这一多很多操作的性质就变了。节点结构变成template typename T class DoublyLinkedList { private: struct Node { T data; Node* prev; Node* next; explicit Node(const T val) : data(val), prev(nullptr), next(nullptr) {} }; Node* head_ nullptr; Node* tail_ nullptr; // 尾指针让尾插变成 O(1) size_t size_ 0; public: DoublyLinkedList() default; ~DoublyLinkedList() { clear(); } void push_front(const T val); void push_back(const T val); bool insert(size_t index, const T val); bool erase(size_t index); void clear(); void print_forward() const; void print_backward() const; };单链表像单向通道只能往前走双链表像双向通道随时可以回头。但它的价值不只是“能倒着走”。当你知道某个节点的地址、却要删除它时单链表必须从头找到它的前驱O(n)双链表通过prev直接拿到前驱O(1)。这个差异直接决定了LRU缓存为什么要用双链表而不是单链表。代价也很实在每个节点多8字节指针64位系统插入删除需要维护的指针从2个变成4个出错概率指数上升。所以没有回退需求、没有O(1)删除已知节点需求的情况下硬上双链表纯属给自己加戏。3.2 尾指针的作用让尾插从O(n)降到O(1)我对这个感受太深了。最早我实现双链表不带tail_push_back还是要从头遍历到尾跟单链表没区别等于白瞎了两个指针。加了tail_之后尾插直接O(1)template typename T void DoublyLinkedListT::push_back(const T val) { Node* newNode new Node(val); if (!head_) { head_ tail_ newNode; size_; return; } newNode-prev tail_; tail_-next newNode; tail_ newNode; size_; }空链表时head_和tail_同时指向新节点非空时先让新节点的prev指向原tail再让原tail的next指向新节点最后更新tail_。顺序同样重要新节点的prev要先用tail_赋值如果先改tail_-next再拿tail_赋值逻辑没错但代码可读性会差。保持“先接新节点再改老节点最后更新边界”的顺序最不容易出bug。push_front对称处理template typename T void DoublyLinkedListT::push_front(const T val) { Node* newNode new Node(val); if (!head_) { head_ tail_ newNode; size_; return; } newNode-next head_; head_-prev newNode; head_ newNode; size_; }3.3 插入与删除四指针的连接顺序与边界条件双链表的核心操作是插入和删除比单链表多了一倍指针要维护。我最常跟人强调的一句话是先把newNode自己的两个指针设好再去改前后邻居的指针。看插入实现template typename T bool DoublyLinkedListT::insert(size_t index, const T val) { if (index size_) return false; if (index 0) { push_front(val); return true; } if (index size_) { push_back(val); return true; } // 找到原 index 位置的节点新节点要插在它前面 Node* cur head_; for (size_t i 0; i index; i) { cur cur-next; } Node* prevNode cur-prev; Node* newNode new Node(val); // 先接新节点 newNode-prev prevNode; newNode-next cur; // 再改邻居 prevNode-next newNode; cur-prev newNode; size_; return true; }为什么“先接新节点”的顺序重要因为改newNode的指针使用的是prevNode和cur的当前值不依赖邻居已被修改反过来操作先改prevNode-next会导致原来的cur节点仍然能从next访问到也没坏但思考复杂度会上升。养成固定顺序的习惯删节点才能少踩坑。删除要处理三种情况删除头节点、删除尾节点、删除中间节点。我一律先定位到目标节点cur再统一处理template typename T bool DoublyLinkedListT::erase(size_t index) { if (index size_) return false; Node* cur head_; for (size_t i 0; i index; i) { cur cur-next; } if (cur-prev) { cur-prev-next cur-next; } else { head_ cur-next; // 删除的是头节点 } if (cur-next) { cur-next-prev cur-prev; } else { tail_ cur-prev; // 删除的是尾节点 } delete cur; --size_; return true; }这里最容易被忽略的是边界。删除头节点时cur-prev为nullptr你不能再访问cur-prev-next必须单独把head_更新为cur-next。删除尾节点同理要单独更新tail_。两条if分支正好处理这两件事。很多新手写删除只记得中间节点一旦删头删尾就崩原因就是没把这种“边界特判”当第一优先级。3.4 正向反向遍历与LRU缓存的实际价值双链表打印有两种方向正向靠next反向靠prev从tail_一路往回template typename T void DoublyLinkedListT::print_forward() const { const Node* cur head_; while (cur) { std::cout cur-data ; cur cur-next; } std::cout \n; } template typename T void DoublyLinkedListT::print_backward() const { const Node* cur tail_; while (cur) { std::cout cur-data ; cur cur-prev; } std::cout \n; }反向遍历看起来只是绕路但它在真实工程里解决过一个非常关键的问题LRU缓存淘汰。LRU的核心操作是“最近被访问过的数据挪到链表头部缓存满时淘汰尾部”。当某个key被访问时需要把对应节点从链表中间摘下来再头插。摘除中间节点时单链表必须从头找到它的前驱O(n)双链表通过node-prev一步就能拿到前驱O(1)。这也是为什么std::list在设计上要保留双向指针很多分布式缓存的淘汰策略也都是双链表 哈希表的组合。讲到这里你应该明白双链表的价值不是“能倒着遍历”这个表面能力而是“在任意位置做O(1)插入删除”的底层能力。4. 内存与安全链表在C里最容易翻车的三座大山4.1 析构与清空内存泄漏都藏在delete的动作里手写链表的每个节点都是用new在堆上创建的谁负责释放答案是链表类自己。析构函数里调一次clear()就是RAII的体现链表的生命周期由栈上的对象决定对象销毁时自动释放它占用的所有内存。但这里有个很隐蔽的问题很多人以为写了clear()就安全了其实析构只是最后一道防线。你在程序运行过程中每调一次insert而忘记相应的删除节点就泄漏一次。频繁增删再伴随频繁new内存碎片和泄漏会一起出现。另一个低级错误是new[]和delete混用。链表节点是单个new出来的释放必须用delete不能用delete[]。这个知识点看起来基础但在多人协作的代码里确实发生过。还有一点C的new失败时会抛bad_alloc异常所以不要写if (!newNode)这类检查。需要重点保证的是构造顺序的异常安全如果插入节点时new抛异常链表还未被修改状态保持原样这其实已经比很多“先改链表再new”的写法安全得多。4.2 深拷贝与移动语义浅拷贝崩溃实录默认的拷贝构造是逐成员复制。对链表来说逐成员复制意味着两个对象的head_指向同一串节点。当我写SingleLinkedListint a; a.push_back(1); a.push_back(2); SingleLinkedListint b(a); // 默认拷贝b 和 a 共享同一串节点作用域结束时a先析构把这串节点全部deleteb再析构对这串已经释放的内存再delete一遍直接double free崩溃。这个bug在真实项目里非常常见而且不是每次都崩属于隔三差五随机发作的类型。解决方法是自定义深拷贝构造逐节点复制template typename T SingleLinkedListT::SingleLinkedList(const SingleLinkedList other) : head_(nullptr), size_(0) { Node* cur other.head_; Node** tailLink head_; while (cur) { *tailLink new Node(cur-data); cur cur-next; tailLink (*tailLink)-next; } size_ other.size_; }这里二级指针又立功了tailLink始终指向链表末尾节点的next指针新节点直接挂到末尾不需要单独维护尾节点。移动构造则要转移所有权template typename T SingleLinkedListT::SingleLinkedList(SingleLinkedList other) noexcept : head_(other.head_), size_(other.size_) { other.head_ nullptr; other.size_ 0; }移动语义的关键是把对方的资源偷过来再让对方处于可析构的空状态。如果不把other.head_置空other析构时会把我们刚偷过来的节点全删掉。C里所谓“把资源从一个对象转移给另一个对象”本质上就是指针所有权的交接谁持有指针谁负责释放。4.3 智能指针改造unique_ptr适合单链表双链表要三思现代C里裸指针管理节点确实容易出错。一个常见思路是单链表用std::unique_ptr管理next指针template typename T class UniqueLinkedList { private: struct Node { T data; std::unique_ptrNode next; explicit Node(const T val) : data(val), next(nullptr) {} }; std::unique_ptrNode head_; public: void push_front(const T val) { auto newNode std::make_uniqueNode(val); newNode-next std::move(head_); head_ std::move(newNode); } // 所有节点会随着 unique_ptr 链自动释放析构函数都可以不写 };unique_ptr代表“独占所有权”单链表里每个节点只被前一个节点的next独占持有所有权关系非常清晰这个方案几乎零成本地消灭了手动delete。但要注意一个隐藏坑链表很长时unique_ptr链式析构会递归释放可能导致栈溢出。几个百万级节点的链表就足以触发这时候反而需要手动用循环来析构。双链表用unique_ptr就没那么顺利了。一个节点同时被前一个节点的next和后一个节点的prev引用两个拥有者明显违背unique_ptr的独占模型。用shared_ptr又要处理节点之间互相引用导致的循环引用必须引入weak_ptr破解。绕了一圈复杂度比裸指针还高。所以在实际工程里标准库的std::list和std::forward_list仍然是用精心管理的裸指针实现的。手写双链表时裸指针 类内封装 五法则反而是最清晰可靠的做法。这也印证了一件事智能指针不是万能圣杯它解决所有权问题但数据结构内部的双向引用用智能指针比裸指针更拧巴。4.4 哨兵节点与循环链表让代码更简洁的两个改造前面实现的单链表和双链表都没有头节点哨兵节点。这种设计在插入删除时都要特判head_代码里充斥着if (!head_)。更优雅的做法是引入哑节点链表类里固定存在一个不存数据的哨兵节点真正的头节点从哨兵的next开始。哨兵节点的核心价值是让操作头节点和操作中间节点一样不再需要特判。删除节点时不管删的是第几个逻辑都一样前驱的next指向后继。插入时同样统一。代价是多一个空节点遍历时要跳过它。循环链表则是另一条路单链表的尾节点不指向nullptr而是指向头节点。遍历终止条件从cur nullptr变成cur head_。一起步就容易碰到死循环如果你从中间进入永远绕不回nullptr。所以循环链表必须用“回到起点”而不是“遇到空”来作为终止判断。把哨兵节点和循环链表结合起来就是很多开源库实现循环双向链表的方式。一个dummy节点让它自己形成一个环整个链表的头尾操作全部统一代码极其简洁。这可以作为练习先写熟裸指针版单链表、双链表再把其中一个改成哨兵版再把哨兵版改成循环版。每改一步你对“边界到底难在哪里”的理解都会上一个台阶。5. 实战经验与调试指南5.1 经典崩溃场景与排查表手写链表的崩溃场景翻来覆去就那么几类我用一张表总结现象根因排查思路打印链表时陷入死循环尾节点next没置空或者某个节点next指向了自己遍历时记下已访问的节点地址发现重复就是成环删除节点后接着遍历就崩delete节点后才去访问其成员成了悬空指针先改链表连接再delete顺序不可反程序报double free浅拷贝导致两个对象共享同一串节点析构两次检查是否自定义了拷贝构造和拷贝赋值析构时栈溢出或崩溃长链表用unique_ptr链式析构递归过深改为循环删除或限制链表规模Windows下提示缺少VCRUNTIME140.dll本机没有Visual C运行库去微软官网下载安装对应版本的RedistributableVS Code里变量无法正常查看编译命令没加调试信息g加-g选项检查launch.json配置最值得养成习惯的是用AddressSanitizer跑链表测试。编译时加一行g -stdc17 -g -fsanitizeaddress -Wall -Wextra main.cpp -o list一旦有越界访问、释放后使用、double free程序会直接告诉你具体是哪一行出问题比肉眼排查快得多。我在本地练习链表时几乎必开这个选项等代码通过再关掉这个习惯帮我省下了大量深夜debug时间。5.2 链表在标准库与工程中的选型别为做题而做题聊到链表就不得不提标准库。C里的std::list就是双链表std::forward_list就是单链表。那自己手写的意义是什么我觉得有三个学习原理、应对面试、实现标准库没提供但你需要定制的结构。先看标准容器的对比容器随机访问中间插入/删除额外内存缓存友好度std::vectorO(1)O(n)少高std::listO(n)O(1)每节点2个指针低std::forward_listO(n)O(1)每节点1个指针低std::dequeO(1)两端O(1)中间O(n)中等中工程选型的原则很简单需要随机访问就选vector需要频繁在中间插入删除再考虑list需要快速头尾操作就用deque。但如果只是想要一个“省内存的链表”单链表反而是最省的选择这也是std::forward_list存在的理由。大多数生产项目里手写链表唯一合理的理由是你要定制它比如给节点分配对齐内存、记录访问次数、做成侵入式链表直接嵌入对象。否则直接用标准库就好。会手写是基本功不滥用是职业素养。5.3 面试手写链表几个能救命的细节现在很多算法题和认证考试比如GESP三级左右的链表题都爱考链表基础操作面试更是直接手写反转、找环、合并有序链表。我总结几个实战细节第一下笔之前先画图。把链表画出来标清楚每一步操作后的指针状态再写代码。真正写的时候你会发现画图能拦住一半的指针逻辑错误。第二写完代码立刻过一遍边界空链表插入、删除头节点、删除尾节点、只剩一个节点的链表。这四类边界过完代码基本就稳了。第三把复杂度说清楚。单链表删除给定节点为什么是O(n)因为拿不到前驱。双链表为什么是O(1)因为有prev。面试官就是想听你把这个差异讲明白。第四主动提内存管理。用裸指针就说明析构和拷贝策略不想背锅就提一句可以用unique_ptr。主动讲这些会给面试官留下“这个人懂生命周期”的强烈印象。工程与面试还有个非常大的区别面试的白板代码是单线程、临时数据的release不 release都行工程代码则要考虑多线程并发、异常安全、内存池复用、自定义分配器。所以不要拿工程标准去要求白板也不要拿白板水平去写工程。两者是同一门手艺在不同场景下的不同姿态。最后说点个人体会。链表这个东西看着简单实际上每次手写都是一次很好的“内存审计”。我不止一次在写过链表后重构自己的其他代码因为链表把“谁拥有这块内存”“什么时候释放”“指针之间怎么传递所有权”这些问题全部摆到了明面上。如果你也在练习我建议先写出能跑的裸指针版再改成unique_ptr版然后用哨兵节点重写一遍双链表最后去读一遍std::list源码的开头部分。每多写一遍你对C内存模型的理解就会深一层这比背任何模板都管用。