1. 为什么要自己实现一个带头双向链表先看清楚 std::list 的本质很多人学 C 的时候std::list属于那种会用但从来没想过它里面长什么样的容器。调用push_back、insert、erase很方便但面试时被问一句list 的底层数据结构是什么插入删除为什么是 O(1)迭代器为什么不能像 vector 那样直接 5 就卡住了。原因很直接——标准库把细节藏得太好了你根本感知不到它背后发生了什么。这个项目要做的事情就是自己动手实现一个带头的双向循环链表把std::list的核心功能——增、删、查、改——全部模拟出来。不依赖任何 STL 容器全部从零写。先弄清楚带头双向链表里带头是什么意思。这里的头不是第一个有效节点而是一个不存储有效数据的哨兵节点通常叫head或者_pHead。它的next指向链表第一个有效节点prev指向最后一个有效节点。当链表为空时head-next和head-prev都指向head自己。这就是循环的含义——整个链表是一个环从任何节点出发都能走回原地。为什么 STL 要这么设计直接用一个不循环的带头链表不行吗提示如果链表为空时head-next和head-prev都指向head本身那么begin()和end()的判断就极其统一。end()就直接返回指向 head 的迭代器不用额外维护尾指针push_back就是在 head 前面插入push_front就是在 head 后面插入。这个设计让所有边界条件都变成同一种情况代码量直接少掉三分之一。这个项目适合谁正在学 C 数据结构的人、准备面试需要深挖 STL 底层原理的人、以及看完std::list源码觉得太抽象想用更直白的方式复现一遍的人。看完这一篇你能回答上面所有问题而且不是背答案的那种理解是真正手写过一遍的底气。2. 节点设计、整体骨架与哨兵位头节点的三件事2.1 节点的自引用结构链表的最小单元是节点。双向链表的每个节点需要三个成员存储数据的_data、指向前一个节点的_prev、指向后一个节点的_next。在 C 中这正是自引用结构体的经典用法templateclass T struct ListNode { ListNodeT* _prev; ListNodeT* _next; T _data; ListNode(const T data T()) : _prev(nullptr) , _next(nullptr) , _data(data) {} };构造函数里的const T data T()这个默认参数值得说一下。T()是 T 类型的默认构造临时对象如果 T 是int那就是 0如果 T 是std::string那就是空字符串如果 T 是自定义类型那就调用它的默认构造。这样在创建哨兵节点时就不用传任何数据直接new ListNodeT()就能得到一个节点而它内部的_data已经有一个合法的默认值了。2.2 链表类的成员构成List类的骨架如下templateclass T class List { public: typedef ListNodeT Node; List() { _pHead new Node; _pHead-_next _pHead; _pHead-_prev _pHead; } private: Node* _pHead; };这段代码虽然短但哨兵头节点要做的事情已经包含在里面了一共三件分配空间new Node调用默认构造创建一个不存储有效数据的节点。将_next指向自身链表为空时头节点的下一个节点确实是它自己。将_prev指向自身链表为空时头节点的上一个节点也是它自己。这三件事缺一不可。如果构造完没有把_next和_prev指向自身那么后续所有围绕end()的操作全都会踩到空指针上。很多初学者写链表崩溃翻来覆去找不到原因最后发现是构造函数里少写了_pHead-_next _pHead。2.3 为什么是循环 带头而不是更直观的版本很多人刚开始会想我直接定义一个Node* _first指向第一个节点定义一个size_t _size记录长度这样不是更直观吗这种思路没有错但会带来一系列边界判断插入第一个节点时_first要从 nullptr 变成新节点需要单独写一套逻辑。删除最后一个节点时要判断_first _next又得加一个条件分支。遍历时要判断当前节点是否为空尾部条件不统一。尾插时要么遍历到最后一个节点再插入时间复杂度变成 O(n)要么额外维护一个_last尾指针。而带头循环链表把这些场景全部统一成一个姿态永远操作 head 的前面或后面中间节点和头尾节点没有区别。这是 STL 里std::list采用同样结构设计的根本原因不是炫技是工程上最省心的选择。3. 迭代器是这个链表的灵魂不能用裸指针蒙混过关3.1 为什么 Node* 直接拿来用不行最朴素的做法是begin()返回_pHead-_nextend()返回_pHead然后直接操作Node*。这样做最直接的问题是不支持运算符的重载语义扩展。裸指针做p时它的行为是指向下一个内存地址但对于链表节点来说下一个内存地址根本不是下一个节点——链表节点在堆上随机分布节点之间没有内存上的连续性。Node*的operator是内置行为无法重载所以就算你把Node*返回给用户用户拿它做it实际效果是跳到一块完全无关的内存上程序直接崩溃。还有一个语义问题是operator*。我们期望*it拿到的是节点存储的数据T而不是节点本身ListNodeT。但裸指针解引用拿到的永远是它指向的那个对象本身也就是说*it拿到的是ListNodeT想要里面的_data还得手写(*it)._data。这完全违背了迭代器要像指针一样透明地访问容器元素的设计理念。所以迭代器必须封装成一个独立的类把ListNodeT*藏在内部对外提供类似指针的运算符接口。3.2 三个模板参数的经典写法std::list的迭代器实现里常见的一种封装方式是用三个模板参数区分普通迭代器和 const 迭代器templateclass T, class Ref, class Ptr class ListIterator { public: typedef ListNodeT Node; typedef ListIteratorT, Ref, Ptr Self; ListIterator(Node* node nullptr) : _pNode(node) {} Ref operator*() { return _pNode-_data; } Ptr operator-() { return _pNode-_data; } Self operator() { _pNode _pNode-_next; return *this; } Self operator(int) { Self tmp(*this); _pNode _pNode-_next; return tmp; } Self operator--() { _pNode _pNode-_prev; return *this; } bool operator!(const Self it) const { return _pNode ! it._pNode; } bool operator(const Self it) const { return _pNode it._pNode; } Node* _pNode; };当Ref是T时operator*返回可修改的引用这是普通迭代器当Ref是const T时operator*返回只读引用这是 const 迭代器。Ptr同理分别对应T*和const T*。然后在 List 类里定义两个迭代器类型typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; iterator begin() { return iterator(_pHead-_next); } iterator end() { return iterator(_pHead); } const_iterator begin() const { return const_iterator(_pHead-_next); } const_iterator end() const { return const_iterator(_pHead); }begin()返回的是第一个有效节点end()返回的是哨兵节点。因为这是个循环链表所以end()并不是空指针而是最后一个有效节点的下一个节点也就是 head。这个设计让while (it ! end())这类遍历判断不需要区分链表是否为空逻辑统一而简洁。注意代码中演示用了三模板参数版本是为了让你理解 STL 源码里const_iterator是怎么复用的。实际手写完你会感觉到这种用模板参数区分访问权限的技巧在写自己的泛型容器时非常有用。4. 增删查改核心接口逻辑与最容易出错的连接顺序4.1 insert 和 erase 是万能的基石这个项目里我建议把insert和erase作为所有插入删除操作的核心其他接口全部复用它们。insert的语义是在pos迭代器指向的节点之前插入一个新节点。iterator insert(iterator pos, const T val) { Node* cur pos._pNode; Node* prev cur-_prev; Node* newNode new Node(val); prev-_next newNode; newNode-_prev prev; newNode-_next cur; cur-_prev newNode; return iterator(newNode); }这里最关键的点是指针连接顺序。正确顺序是先处理 prev 指向新节点和新节点的前驱再处理新节点指向 cur 和 cur 的前驱。为什么要这个顺序因为一旦把cur-_prev改成newNode之后再想通过cur-_prev拿到原来的 prev 就不行了。所以如果代码顺序写成cur-_prev newNode; newNode-_next cur; prev-_next newNode; newNode-_prev prev;第一句执行完之后cur-_prev已经指向newNode但prev变量是之前保存好的局部变量所以问题不大。真正的坑是如果你在写代码时图省事直接写成cur-_prev-_next newNode而不是先保存prev那么第一句把cur-_prev改掉之后后面再取cur-_prev指向的就不是原来的前驱节点了链表直接断掉。erase的语义是删除pos指向的节点返回被删除节点的下一个节点。iterator erase(iterator pos) { Node* cur pos._pNode; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; return iterator(next); }删除节点之后必须返回下一个有效节点而不能返回传入的pos。因为pos指向的节点已经被 delete 掉了再使用它就是悬空指针。erase 之后原来的迭代器彻底失效这是 C 链表使用中最经典的一个坑下面第 6 节会专门讲一个具体的崩溃案例。4.2 头插尾插核心函数全部复用 insertvoid push_back(const T val) { insert(end(), val); } void push_front(const T val) { insert(begin(), val); }push_back就是在 head 之前插入也就是在end()之前插入push_front就是在 head 之后插入也就是在begin()之前插入。因为end()指向 headinsert(end(), val)就是在 head 前面插入恰好是链表尾部。这比单独的找到尾节点再插入的写法减少了循环遍历也让代码的可维护性高了很多。删除接口对应void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }--end()这个操作很微妙。end()返回的是 head 迭代器--之后就变成了最后一个有效节点的迭代器。所以pop_back实际上就是删除最后一个有效节点。注意这里不能直接erase(end())因为end()指向的是无效节点 head删掉它整个链表骨架就散了。4.3 查找与改值的落地姿势查找操作遍历链表找到返回迭代器找不到返回end()iterator find(const T val) { iterator it begin(); while (it ! end()) { if (*it val) { return it; } it; } return end(); }改值可以借助查找结果直接做Listint::iterator it lt.find(30); if (it ! lt.end()) { *it 300; }这里的*it 300之所以能修改数据靠的是operator*返回了T引用。如果你写迭代器时图省事直接返回了T的值拷贝那么这里改的就只是一个临时变量链表里的数据不会被修改。这也是验证迭代器引用语义是否正确的标准写法。4.4 insert 在查找场景下的一个实战用法insert最有价值的地方是可以搭配find实现在指定元素附近插入。比如在一个升序链表中我想把 25 插入到 20 和 30 之间auto it lt.begin(); while (it ! lt.end() *it 25) { it; } lt.insert(it, 25);因为insert是在pos之前插入这里找到第一个大于等于 25 的节点也就是 30在它之前插入 25 就能保持升序。这段逻辑用push_back是做不到的你无法控制插入位置这就是为什么insert是核心接口。5. 拷贝构造、赋值运算符与析构不写就会崩的三件套很多初学者写链表只写了增删查改就认为完事了结果把 List 对象作为参数传给函数、或者用一个 List 初始化另一个 List 时程序莫名其妙崩溃。原因是没有遵守 C 的三/五法则只要类管理了堆上的资源就必须同时考虑析构函数、拷贝构造函数、拷贝赋值运算符这三个特殊成员函数。5.1 浅拷贝的双重释放问题如果我们不写拷贝构造函数编译器会生成一个默认的——它只做逐成员拷贝。对 List 来说就是_pHead other._pHead;这意味着两个 List 对象共享同一个_pHead以及整条链表的所有节点。当lt1析构时把这条链表的所有节点 delete 掉lt2析构时又把这些已经被删除的节点再 delete 一次。同一块内存被释放两次程序直接崩溃。解决办法是深拷贝为新的 List 创建一条全新的链表节点内容与原来的链表完全相同但节点在堆上是完全独立的。List(const ListT lt) { _pHead new Node; _pHead-_next _pHead; _pHead-_prev _pHead; for (const_iterator it lt.begin(); it ! lt.end(); it) { push_back(*it); } }这段代码先创建哨兵头节点完成空链表的初始化然后遍历传入的链表把每个节点的数据依次push_back到新链表中。整个过程不涉及节点指针的直接复制每个新节点都是在insert里通过new出来的。5.2 赋值运算符的两种写法里我推荐 swap赋值运算符最朴素的写法是ListT operator(const ListT lt) { if (this ! lt) { clear(); for (const_iterator it lt.begin(); it ! lt.end(); it) { push_back(*it); } } return *this; }先判断自赋值避免lt lt时先把数据清掉导致后面遍历出错。这种写法没问题但还有一种更优雅的写法——拷贝并交换void swap(ListT lt) { std::swap(_pHead, lt._pHead); } ListT operator(ListT lt) { swap(lt); return *this; }这段代码的关键在于参数不是const ListT而是按值传参ListT lt。传入时调用拷贝构造函数创建一个临时对象这个临时对象拥有原对象数据的完整深拷贝。然后swap把当前对象和临时对象的_pHead指针交换当前对象从此持有那份深拷贝的数据临时对象则持有旧数据函数结束临时对象析构旧数据被正确释放。5.3 clear 和析构的代码复用先写clear清空所有有效节点但保留哨兵节点。再写析构函数时直接调用clear然后释放头节点void clear() { Node* cur _pHead-_next; while (cur ! _pHead) { Node* next cur-_next; delete cur; cur next; } _pHead-_next _pHead; _pHead-_prev _pHead; } ~List() { clear(); delete _pHead; _pHead nullptr; }clear里保存 next 再 delete 当前节点是必须的。因为 delete 当前节点之后它的_next已经不存在了不先保存就无法遍历到下一个节点。clear之后要把 head 的 next 和 prev 都重新指向自身恢复空链表状态。5.4 析构之后把 _pHead 置空是不是多余的delete _pHead之后_pHead仍然保存着那块已经释放的内存的地址成为一个悬空指针。虽然析构之后这个对象马上就不可用了置空与否看起来没区别但在调试阶段这样做能帮你快速发现在对象析构后还访问它的资源这类 bug。如果后面有人错误地继续调用这个 List 的方法悬空指针可能在某些平台下还能碰巧访问到内存而置空之后会直接触发空指针访问崩溃点更清晰。6. 迭代器失效erase 之后哪些操作会当场崩溃迭代器失效是 C 容器使用中最隐蔽的问题在 list 里主要体现在 erase 操作上。6.1 一个真实的内存错误复现先看这段代码目的是删除链表中所有值为 2 的元素#include iostream using namespace std; int main() { Listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(2); lt.push_back(3); // 错误写法 Listint::iterator it lt.begin(); while (it ! lt.end()) { if (*it 2) { lt.erase(it); } it; } return 0; }这段代码运行时分三种情况全都不正确如果链表里只有一个值为 2 的节点erase(it)之后it 指向的节点已经被 delete变成悬空迭代器再执行itit._pNode _pNode-_next访问的是一片已经被释放的内存程序可能崩溃、可能返回垃圾值、可能陷入死循环。如果链表里有连续两个值为 2 的节点删除第一个后it悬空再it行为未定义大概率跳过第二个值为 2 的节点删除所有值为 2 的元素的目标没有达成。如果恰好删除的是最后一个节点it悬空后it_pNode 指向的位置已经不可预测循环条件都可能判断异常。正确的写法是利用 erase 的返回值让迭代器在被删节点的下一个节点上继续执行Listint::iterator it lt.begin(); while (it ! lt.end()) { if (*it 2) { it lt.erase(it); } else { it; } }核心逻辑是只有不需要删除时才手动it需要删除时it直接更新为 erase 的返回值即被删节点的下一个节点不能再手动。6.2 为什么 vector 和 list 的失效规则不一样同样是 erasevector 是删除位置之后的迭代器全部失效而 list 是只有被删除节点的迭代器失效其他迭代器依然有效。原因是 vector 的元素连续存储删除一个元素后需要把后面的元素整体往前搬移所以后面的迭代器指向的内存位置虽然还在但内容已经变了迭代器语义上失效。而 list 的节点是独立的删除一个节点只需要调整前后两个节点的指针指向其他节点的内存地址没有发生任何变化它们的迭代器依然有效。这个差异意味着在 list 里可以安全地保存一个指向特定节点的迭代器在删除其他节点后继续使用它。在 vector 里完全不能这样做任何插入删除操作后所有迭代器都有失效风险。这个特性也使得删除符合条件的所有元素在 list 里有高效写法就是你刚看到的基于 erase 返回值的方案。6.3 用 --end() 删除最后一个节点时要注意的坑另一种常见的错误是lt.erase(--lt.end()); // 正确删除最后一个有效节点 lt.erase(lt.end()); // 错误删除哨兵节点链表骨架散了如果写的不是--lt.end()链表的行为会变得非常诡异head 被 delete 掉之后所有迭代器指向的内存都已失效程序大概率直接崩溃。排查这种问题时如果你的程序在erase周边莫名崩溃第一件事就是确认传入的迭代器是不是end()。7. 完整测试代码与环境验证空链表、单节点、常规数据分别怎么测写完实现后我建议用以下几组测试用例做验证覆盖边界条件#include iostream using namespace std; // ListNode、ListIterator、List 的完整实现放在这里 // ... void printList(const Listint lt) { Listint::const_iterator it lt.begin(); while (it ! lt.end()) { cout *it ; it; } cout endl; } int main() { // 测试1空链表操作 Listint empty; cout empty begin end ? (empty.begin() empty.end()) endl; empty.push_back(10); empty.pop_back(); cout after push then pop, empty begin end ? (empty.begin() empty.end()) endl; // 测试2头插尾插 Listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_front(0); printList(lt); // 期望输出0 1 2 3 // 测试3find insert Listint::iterator it lt.find(2); if (it ! lt.end()) { lt.insert(it, 99); } printList(lt); // 期望输出0 1 99 2 3 // 测试4find 修改 it lt.find(99); if (it ! lt.end()) { *it 100; } printList(lt); // 期望输出0 1 100 2 3 // 测试5erase 全部等于 1 的元素 it lt.begin(); while (it ! lt.end()) { if (*it 1) { it lt.erase(it); } else { it; } } printList(lt); // 期望输出0 100 2 3 // 测试6深拷贝与赋值 Listint lt2(lt); lt2.push_back(2024); cout lt: ; printList(lt); cout lt2: ; printList(lt2); // 测试7const 迭代器验证 const Listint ref lt; Listint::const_iterator cit ref.begin(); while (cit ! ref.end()) { // *cit 0; // 放开这一行会编译报错证明 const 迭代器只读 cit; } return 0; }这里尤其建议加一组自定义类型的测试struct Person { Person(const string name , int age 0) : _name(name), _age(age) {} string _name; int _age; }; ListPerson persons; persons.push_back(Person(Alice, 25)); persons.push_back(Person(Bob, 30)); persons.push_back(Person(Charlie, 35)); ListPerson copied(persons); copied.push_back(Person(Dave, 40));Person里面有string成员string 自己管理堆上内存所以如果 List 不实现深拷贝persons和copied共享节点会导致 string 对象在析构时二次释放程序直接崩溃实现了深拷贝之后两个链表完全独立运行正常。这一步能把拷贝构造写没写对变成一眼可见的结果。编译时建议打开告警g -g -Wall -Wextra -stdc11 main.cpp -o test_list valgrind ./test_list在支持 Valgrind 的环境上跑一遍重点看definitely lost是否为零。这个项目全部实现完之后内存泄露为 0 是基本要求如果报出丢失优先检查析构和 erase 路径上有没有少 delete。8. 与 std::list 的对比测试同样的逻辑标准库跑出的性能差多少模拟实现和标准库对比测试不是为了证明你写得比 STL 好——大概率不可能——而是为了验证你的实现行为与标准库一致同时理解 STL 为了性能和通用性做过哪些取舍。简单的对比测试#include list #include chrono void testStdList() { std::listint lst; auto start chrono::steady_clock::now(); for (int i 0; i 100000; i) { lst.push_back(i); } auto end chrono::steady_clock::now(); cout std::list push_back 100000 times: chrono::duration_castchrono::microseconds(end - start).count() us endl; } void testMyList() { Listint lst; auto start chrono::steady_clock::now(); for (int i 0; i 100000; i) { lst.push_back(i); } auto end chrono::steady_clock::now(); cout My List push_back 100000 times: chrono::duration_castchrono::microseconds(end - start).count() us endl; }实测下来在 release 模式下标准库比自己实现的快多少取决于编译优化级别和实现细节。从我自己跑的情况看标准库大约快 10% 到 30% 左右。差距主要来自这几个地方标准库的节点分配通常配合了内存池或分配器优化而手写版本直接使用new在频繁插入时会有大量堆分配调用。标准库迭代器在 release 模式下会被大量内联极致优化后几乎和裸指针操作没有区别。标准库的实现可能对缓存局部性做了针对性优化比如节点大小对齐等。这个差距是正常的也是手写容器的核心价值所在——你通过对比真正理解了标准库为什么快快在哪里。如果哪天你给自定义类型实现一个专用链表标准库不能直接用比如你需要节点预分配、对象池化等场景参照 std::list 的设计把这些优化点做进去你的版本也不会差太远。提示如果想进一步优化手写版的性能可以尝试实现一个简单的节点对象池每次插入不再new节点而是从池中复用已经释放的内存减少堆分配次数。这是很多高性能链表的常见优化手段。9. 排查实录一个真实的内存越界问题的完整定位链路最后分享一个我在写这个项目时实际踩过的坑。当时写完核心代码跑增删查改的常规测试全部通过但一旦把 List 对象放进 vector然后对 vector 做扩容程序就在析构时报错而且报错的位置每次都不一样有时在free()里有时在_CrtIsValidHeapPointerWindows 调试器提示里。排查过程如下第一步先确认是不是 List 析构本身有问题。我单独测试连续的 push、pop、clear、析构跑了几万次没崩溃。排除了清空逻辑漏删节点的基本问题。第二步怀疑是拷贝构造没写对。把 List 对象放进 vectorvector 扩容时要拷贝所有元素如果拷贝是浅拷贝元素析构两次就会导致堆错误。这个思路当时觉得最可能于是写了一段专门测试拷贝构造的代码Listint lt1; for (int i 0; i 10; i) lt1.push_back(i); Listint lt2(lt1); lt2.push_back(100);跑完结果完全正常lt1 和 lt2 各自独立。到这里拷贝构造看起来也是对的。第三步把范围缩小到 vector 场景。vector 不止会拷贝还会在扩容时析构旧元素。问题就出在这里——旧元素析构时调用 List 的析构函数析构函数把_pHead置成了nullptr。这本身没问题问题在于我当时写的拷贝构造函数里深拷贝完成之后没有正确修正所有的内部指针有一段代码在拷贝时直接用了一个临时迭代器变量保存当前节点指针但拷贝完成后把这个临时迭代器交给了对象导致析构时遍历到了一块被释放过的内存。具体来说我最初写的是List(const ListT lt) { _pHead new Node; _pHead-_next _pHead; _pHead-_prev _pHead; Node* cur lt._pHead-_next; while (cur ! lt._pHead) { Node* newNode new Node(cur-_data); // ... 这里连接的逻辑有一行写错了把 newNode-_prev 指到了 lt 的节点上 cur cur-_next; } }崩溃的本质就是新链表的节点指到了旧链表的节点上新旧两条链表在中间某处交叉了。新链表析构时删除了旧链表的节点旧链表析构时再删一次双重释放。修复方法也很简单把拷贝构造函数里的插入逻辑全部复用insert(end(), val)因为insert只依赖新链表自己的节点指针完全不碰旧链表的内部结构。这就是为什么我最终建议深拷贝时直接循环push_back(*it)而不要手动逐节点连接——重新实现一遍指针操作虽然看起来更高效但每一行都要小心不要引用到源链表的节点。这次排查花了不少时间但收获非常大。一个很深的体会是链表实现里最危险的操作不是写不出来而是写出一个看起来逻辑正确但节点之间交叉引用的隐藏 bug。这种 bug 的排查手段简单有效的是把所有插入删除统一收口到insert和erase这样出问题的可能性被限制在两三个函数里如果自己手写交接逻辑一旦出错就只能在汇编层面慢慢抠了。 手写C++带头双向循环链表：深入理解std::list底层原理
1. 为什么要自己实现一个带头双向链表先看清楚 std::list 的本质很多人学 C 的时候std::list属于那种会用但从来没想过它里面长什么样的容器。调用push_back、insert、erase很方便但面试时被问一句list 的底层数据结构是什么插入删除为什么是 O(1)迭代器为什么不能像 vector 那样直接 5 就卡住了。原因很直接——标准库把细节藏得太好了你根本感知不到它背后发生了什么。这个项目要做的事情就是自己动手实现一个带头的双向循环链表把std::list的核心功能——增、删、查、改——全部模拟出来。不依赖任何 STL 容器全部从零写。先弄清楚带头双向链表里带头是什么意思。这里的头不是第一个有效节点而是一个不存储有效数据的哨兵节点通常叫head或者_pHead。它的next指向链表第一个有效节点prev指向最后一个有效节点。当链表为空时head-next和head-prev都指向head自己。这就是循环的含义——整个链表是一个环从任何节点出发都能走回原地。为什么 STL 要这么设计直接用一个不循环的带头链表不行吗提示如果链表为空时head-next和head-prev都指向head本身那么begin()和end()的判断就极其统一。end()就直接返回指向 head 的迭代器不用额外维护尾指针push_back就是在 head 前面插入push_front就是在 head 后面插入。这个设计让所有边界条件都变成同一种情况代码量直接少掉三分之一。这个项目适合谁正在学 C 数据结构的人、准备面试需要深挖 STL 底层原理的人、以及看完std::list源码觉得太抽象想用更直白的方式复现一遍的人。看完这一篇你能回答上面所有问题而且不是背答案的那种理解是真正手写过一遍的底气。2. 节点设计、整体骨架与哨兵位头节点的三件事2.1 节点的自引用结构链表的最小单元是节点。双向链表的每个节点需要三个成员存储数据的_data、指向前一个节点的_prev、指向后一个节点的_next。在 C 中这正是自引用结构体的经典用法templateclass T struct ListNode { ListNodeT* _prev; ListNodeT* _next; T _data; ListNode(const T data T()) : _prev(nullptr) , _next(nullptr) , _data(data) {} };构造函数里的const T data T()这个默认参数值得说一下。T()是 T 类型的默认构造临时对象如果 T 是int那就是 0如果 T 是std::string那就是空字符串如果 T 是自定义类型那就调用它的默认构造。这样在创建哨兵节点时就不用传任何数据直接new ListNodeT()就能得到一个节点而它内部的_data已经有一个合法的默认值了。2.2 链表类的成员构成List类的骨架如下templateclass T class List { public: typedef ListNodeT Node; List() { _pHead new Node; _pHead-_next _pHead; _pHead-_prev _pHead; } private: Node* _pHead; };这段代码虽然短但哨兵头节点要做的事情已经包含在里面了一共三件分配空间new Node调用默认构造创建一个不存储有效数据的节点。将_next指向自身链表为空时头节点的下一个节点确实是它自己。将_prev指向自身链表为空时头节点的上一个节点也是它自己。这三件事缺一不可。如果构造完没有把_next和_prev指向自身那么后续所有围绕end()的操作全都会踩到空指针上。很多初学者写链表崩溃翻来覆去找不到原因最后发现是构造函数里少写了_pHead-_next _pHead。2.3 为什么是循环 带头而不是更直观的版本很多人刚开始会想我直接定义一个Node* _first指向第一个节点定义一个size_t _size记录长度这样不是更直观吗这种思路没有错但会带来一系列边界判断插入第一个节点时_first要从 nullptr 变成新节点需要单独写一套逻辑。删除最后一个节点时要判断_first _next又得加一个条件分支。遍历时要判断当前节点是否为空尾部条件不统一。尾插时要么遍历到最后一个节点再插入时间复杂度变成 O(n)要么额外维护一个_last尾指针。而带头循环链表把这些场景全部统一成一个姿态永远操作 head 的前面或后面中间节点和头尾节点没有区别。这是 STL 里std::list采用同样结构设计的根本原因不是炫技是工程上最省心的选择。3. 迭代器是这个链表的灵魂不能用裸指针蒙混过关3.1 为什么 Node* 直接拿来用不行最朴素的做法是begin()返回_pHead-_nextend()返回_pHead然后直接操作Node*。这样做最直接的问题是不支持运算符的重载语义扩展。裸指针做p时它的行为是指向下一个内存地址但对于链表节点来说下一个内存地址根本不是下一个节点——链表节点在堆上随机分布节点之间没有内存上的连续性。Node*的operator是内置行为无法重载所以就算你把Node*返回给用户用户拿它做it实际效果是跳到一块完全无关的内存上程序直接崩溃。还有一个语义问题是operator*。我们期望*it拿到的是节点存储的数据T而不是节点本身ListNodeT。但裸指针解引用拿到的永远是它指向的那个对象本身也就是说*it拿到的是ListNodeT想要里面的_data还得手写(*it)._data。这完全违背了迭代器要像指针一样透明地访问容器元素的设计理念。所以迭代器必须封装成一个独立的类把ListNodeT*藏在内部对外提供类似指针的运算符接口。3.2 三个模板参数的经典写法std::list的迭代器实现里常见的一种封装方式是用三个模板参数区分普通迭代器和 const 迭代器templateclass T, class Ref, class Ptr class ListIterator { public: typedef ListNodeT Node; typedef ListIteratorT, Ref, Ptr Self; ListIterator(Node* node nullptr) : _pNode(node) {} Ref operator*() { return _pNode-_data; } Ptr operator-() { return _pNode-_data; } Self operator() { _pNode _pNode-_next; return *this; } Self operator(int) { Self tmp(*this); _pNode _pNode-_next; return tmp; } Self operator--() { _pNode _pNode-_prev; return *this; } bool operator!(const Self it) const { return _pNode ! it._pNode; } bool operator(const Self it) const { return _pNode it._pNode; } Node* _pNode; };当Ref是T时operator*返回可修改的引用这是普通迭代器当Ref是const T时operator*返回只读引用这是 const 迭代器。Ptr同理分别对应T*和const T*。然后在 List 类里定义两个迭代器类型typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; iterator begin() { return iterator(_pHead-_next); } iterator end() { return iterator(_pHead); } const_iterator begin() const { return const_iterator(_pHead-_next); } const_iterator end() const { return const_iterator(_pHead); }begin()返回的是第一个有效节点end()返回的是哨兵节点。因为这是个循环链表所以end()并不是空指针而是最后一个有效节点的下一个节点也就是 head。这个设计让while (it ! end())这类遍历判断不需要区分链表是否为空逻辑统一而简洁。注意代码中演示用了三模板参数版本是为了让你理解 STL 源码里const_iterator是怎么复用的。实际手写完你会感觉到这种用模板参数区分访问权限的技巧在写自己的泛型容器时非常有用。4. 增删查改核心接口逻辑与最容易出错的连接顺序4.1 insert 和 erase 是万能的基石这个项目里我建议把insert和erase作为所有插入删除操作的核心其他接口全部复用它们。insert的语义是在pos迭代器指向的节点之前插入一个新节点。iterator insert(iterator pos, const T val) { Node* cur pos._pNode; Node* prev cur-_prev; Node* newNode new Node(val); prev-_next newNode; newNode-_prev prev; newNode-_next cur; cur-_prev newNode; return iterator(newNode); }这里最关键的点是指针连接顺序。正确顺序是先处理 prev 指向新节点和新节点的前驱再处理新节点指向 cur 和 cur 的前驱。为什么要这个顺序因为一旦把cur-_prev改成newNode之后再想通过cur-_prev拿到原来的 prev 就不行了。所以如果代码顺序写成cur-_prev newNode; newNode-_next cur; prev-_next newNode; newNode-_prev prev;第一句执行完之后cur-_prev已经指向newNode但prev变量是之前保存好的局部变量所以问题不大。真正的坑是如果你在写代码时图省事直接写成cur-_prev-_next newNode而不是先保存prev那么第一句把cur-_prev改掉之后后面再取cur-_prev指向的就不是原来的前驱节点了链表直接断掉。erase的语义是删除pos指向的节点返回被删除节点的下一个节点。iterator erase(iterator pos) { Node* cur pos._pNode; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; return iterator(next); }删除节点之后必须返回下一个有效节点而不能返回传入的pos。因为pos指向的节点已经被 delete 掉了再使用它就是悬空指针。erase 之后原来的迭代器彻底失效这是 C 链表使用中最经典的一个坑下面第 6 节会专门讲一个具体的崩溃案例。4.2 头插尾插核心函数全部复用 insertvoid push_back(const T val) { insert(end(), val); } void push_front(const T val) { insert(begin(), val); }push_back就是在 head 之前插入也就是在end()之前插入push_front就是在 head 之后插入也就是在begin()之前插入。因为end()指向 headinsert(end(), val)就是在 head 前面插入恰好是链表尾部。这比单独的找到尾节点再插入的写法减少了循环遍历也让代码的可维护性高了很多。删除接口对应void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }--end()这个操作很微妙。end()返回的是 head 迭代器--之后就变成了最后一个有效节点的迭代器。所以pop_back实际上就是删除最后一个有效节点。注意这里不能直接erase(end())因为end()指向的是无效节点 head删掉它整个链表骨架就散了。4.3 查找与改值的落地姿势查找操作遍历链表找到返回迭代器找不到返回end()iterator find(const T val) { iterator it begin(); while (it ! end()) { if (*it val) { return it; } it; } return end(); }改值可以借助查找结果直接做Listint::iterator it lt.find(30); if (it ! lt.end()) { *it 300; }这里的*it 300之所以能修改数据靠的是operator*返回了T引用。如果你写迭代器时图省事直接返回了T的值拷贝那么这里改的就只是一个临时变量链表里的数据不会被修改。这也是验证迭代器引用语义是否正确的标准写法。4.4 insert 在查找场景下的一个实战用法insert最有价值的地方是可以搭配find实现在指定元素附近插入。比如在一个升序链表中我想把 25 插入到 20 和 30 之间auto it lt.begin(); while (it ! lt.end() *it 25) { it; } lt.insert(it, 25);因为insert是在pos之前插入这里找到第一个大于等于 25 的节点也就是 30在它之前插入 25 就能保持升序。这段逻辑用push_back是做不到的你无法控制插入位置这就是为什么insert是核心接口。5. 拷贝构造、赋值运算符与析构不写就会崩的三件套很多初学者写链表只写了增删查改就认为完事了结果把 List 对象作为参数传给函数、或者用一个 List 初始化另一个 List 时程序莫名其妙崩溃。原因是没有遵守 C 的三/五法则只要类管理了堆上的资源就必须同时考虑析构函数、拷贝构造函数、拷贝赋值运算符这三个特殊成员函数。5.1 浅拷贝的双重释放问题如果我们不写拷贝构造函数编译器会生成一个默认的——它只做逐成员拷贝。对 List 来说就是_pHead other._pHead;这意味着两个 List 对象共享同一个_pHead以及整条链表的所有节点。当lt1析构时把这条链表的所有节点 delete 掉lt2析构时又把这些已经被删除的节点再 delete 一次。同一块内存被释放两次程序直接崩溃。解决办法是深拷贝为新的 List 创建一条全新的链表节点内容与原来的链表完全相同但节点在堆上是完全独立的。List(const ListT lt) { _pHead new Node; _pHead-_next _pHead; _pHead-_prev _pHead; for (const_iterator it lt.begin(); it ! lt.end(); it) { push_back(*it); } }这段代码先创建哨兵头节点完成空链表的初始化然后遍历传入的链表把每个节点的数据依次push_back到新链表中。整个过程不涉及节点指针的直接复制每个新节点都是在insert里通过new出来的。5.2 赋值运算符的两种写法里我推荐 swap赋值运算符最朴素的写法是ListT operator(const ListT lt) { if (this ! lt) { clear(); for (const_iterator it lt.begin(); it ! lt.end(); it) { push_back(*it); } } return *this; }先判断自赋值避免lt lt时先把数据清掉导致后面遍历出错。这种写法没问题但还有一种更优雅的写法——拷贝并交换void swap(ListT lt) { std::swap(_pHead, lt._pHead); } ListT operator(ListT lt) { swap(lt); return *this; }这段代码的关键在于参数不是const ListT而是按值传参ListT lt。传入时调用拷贝构造函数创建一个临时对象这个临时对象拥有原对象数据的完整深拷贝。然后swap把当前对象和临时对象的_pHead指针交换当前对象从此持有那份深拷贝的数据临时对象则持有旧数据函数结束临时对象析构旧数据被正确释放。5.3 clear 和析构的代码复用先写clear清空所有有效节点但保留哨兵节点。再写析构函数时直接调用clear然后释放头节点void clear() { Node* cur _pHead-_next; while (cur ! _pHead) { Node* next cur-_next; delete cur; cur next; } _pHead-_next _pHead; _pHead-_prev _pHead; } ~List() { clear(); delete _pHead; _pHead nullptr; }clear里保存 next 再 delete 当前节点是必须的。因为 delete 当前节点之后它的_next已经不存在了不先保存就无法遍历到下一个节点。clear之后要把 head 的 next 和 prev 都重新指向自身恢复空链表状态。5.4 析构之后把 _pHead 置空是不是多余的delete _pHead之后_pHead仍然保存着那块已经释放的内存的地址成为一个悬空指针。虽然析构之后这个对象马上就不可用了置空与否看起来没区别但在调试阶段这样做能帮你快速发现在对象析构后还访问它的资源这类 bug。如果后面有人错误地继续调用这个 List 的方法悬空指针可能在某些平台下还能碰巧访问到内存而置空之后会直接触发空指针访问崩溃点更清晰。6. 迭代器失效erase 之后哪些操作会当场崩溃迭代器失效是 C 容器使用中最隐蔽的问题在 list 里主要体现在 erase 操作上。6.1 一个真实的内存错误复现先看这段代码目的是删除链表中所有值为 2 的元素#include iostream using namespace std; int main() { Listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(2); lt.push_back(3); // 错误写法 Listint::iterator it lt.begin(); while (it ! lt.end()) { if (*it 2) { lt.erase(it); } it; } return 0; }这段代码运行时分三种情况全都不正确如果链表里只有一个值为 2 的节点erase(it)之后it 指向的节点已经被 delete变成悬空迭代器再执行itit._pNode _pNode-_next访问的是一片已经被释放的内存程序可能崩溃、可能返回垃圾值、可能陷入死循环。如果链表里有连续两个值为 2 的节点删除第一个后it悬空再it行为未定义大概率跳过第二个值为 2 的节点删除所有值为 2 的元素的目标没有达成。如果恰好删除的是最后一个节点it悬空后it_pNode 指向的位置已经不可预测循环条件都可能判断异常。正确的写法是利用 erase 的返回值让迭代器在被删节点的下一个节点上继续执行Listint::iterator it lt.begin(); while (it ! lt.end()) { if (*it 2) { it lt.erase(it); } else { it; } }核心逻辑是只有不需要删除时才手动it需要删除时it直接更新为 erase 的返回值即被删节点的下一个节点不能再手动。6.2 为什么 vector 和 list 的失效规则不一样同样是 erasevector 是删除位置之后的迭代器全部失效而 list 是只有被删除节点的迭代器失效其他迭代器依然有效。原因是 vector 的元素连续存储删除一个元素后需要把后面的元素整体往前搬移所以后面的迭代器指向的内存位置虽然还在但内容已经变了迭代器语义上失效。而 list 的节点是独立的删除一个节点只需要调整前后两个节点的指针指向其他节点的内存地址没有发生任何变化它们的迭代器依然有效。这个差异意味着在 list 里可以安全地保存一个指向特定节点的迭代器在删除其他节点后继续使用它。在 vector 里完全不能这样做任何插入删除操作后所有迭代器都有失效风险。这个特性也使得删除符合条件的所有元素在 list 里有高效写法就是你刚看到的基于 erase 返回值的方案。6.3 用 --end() 删除最后一个节点时要注意的坑另一种常见的错误是lt.erase(--lt.end()); // 正确删除最后一个有效节点 lt.erase(lt.end()); // 错误删除哨兵节点链表骨架散了如果写的不是--lt.end()链表的行为会变得非常诡异head 被 delete 掉之后所有迭代器指向的内存都已失效程序大概率直接崩溃。排查这种问题时如果你的程序在erase周边莫名崩溃第一件事就是确认传入的迭代器是不是end()。7. 完整测试代码与环境验证空链表、单节点、常规数据分别怎么测写完实现后我建议用以下几组测试用例做验证覆盖边界条件#include iostream using namespace std; // ListNode、ListIterator、List 的完整实现放在这里 // ... void printList(const Listint lt) { Listint::const_iterator it lt.begin(); while (it ! lt.end()) { cout *it ; it; } cout endl; } int main() { // 测试1空链表操作 Listint empty; cout empty begin end ? (empty.begin() empty.end()) endl; empty.push_back(10); empty.pop_back(); cout after push then pop, empty begin end ? (empty.begin() empty.end()) endl; // 测试2头插尾插 Listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_front(0); printList(lt); // 期望输出0 1 2 3 // 测试3find insert Listint::iterator it lt.find(2); if (it ! lt.end()) { lt.insert(it, 99); } printList(lt); // 期望输出0 1 99 2 3 // 测试4find 修改 it lt.find(99); if (it ! lt.end()) { *it 100; } printList(lt); // 期望输出0 1 100 2 3 // 测试5erase 全部等于 1 的元素 it lt.begin(); while (it ! lt.end()) { if (*it 1) { it lt.erase(it); } else { it; } } printList(lt); // 期望输出0 100 2 3 // 测试6深拷贝与赋值 Listint lt2(lt); lt2.push_back(2024); cout lt: ; printList(lt); cout lt2: ; printList(lt2); // 测试7const 迭代器验证 const Listint ref lt; Listint::const_iterator cit ref.begin(); while (cit ! ref.end()) { // *cit 0; // 放开这一行会编译报错证明 const 迭代器只读 cit; } return 0; }这里尤其建议加一组自定义类型的测试struct Person { Person(const string name , int age 0) : _name(name), _age(age) {} string _name; int _age; }; ListPerson persons; persons.push_back(Person(Alice, 25)); persons.push_back(Person(Bob, 30)); persons.push_back(Person(Charlie, 35)); ListPerson copied(persons); copied.push_back(Person(Dave, 40));Person里面有string成员string 自己管理堆上内存所以如果 List 不实现深拷贝persons和copied共享节点会导致 string 对象在析构时二次释放程序直接崩溃实现了深拷贝之后两个链表完全独立运行正常。这一步能把拷贝构造写没写对变成一眼可见的结果。编译时建议打开告警g -g -Wall -Wextra -stdc11 main.cpp -o test_list valgrind ./test_list在支持 Valgrind 的环境上跑一遍重点看definitely lost是否为零。这个项目全部实现完之后内存泄露为 0 是基本要求如果报出丢失优先检查析构和 erase 路径上有没有少 delete。8. 与 std::list 的对比测试同样的逻辑标准库跑出的性能差多少模拟实现和标准库对比测试不是为了证明你写得比 STL 好——大概率不可能——而是为了验证你的实现行为与标准库一致同时理解 STL 为了性能和通用性做过哪些取舍。简单的对比测试#include list #include chrono void testStdList() { std::listint lst; auto start chrono::steady_clock::now(); for (int i 0; i 100000; i) { lst.push_back(i); } auto end chrono::steady_clock::now(); cout std::list push_back 100000 times: chrono::duration_castchrono::microseconds(end - start).count() us endl; } void testMyList() { Listint lst; auto start chrono::steady_clock::now(); for (int i 0; i 100000; i) { lst.push_back(i); } auto end chrono::steady_clock::now(); cout My List push_back 100000 times: chrono::duration_castchrono::microseconds(end - start).count() us endl; }实测下来在 release 模式下标准库比自己实现的快多少取决于编译优化级别和实现细节。从我自己跑的情况看标准库大约快 10% 到 30% 左右。差距主要来自这几个地方标准库的节点分配通常配合了内存池或分配器优化而手写版本直接使用new在频繁插入时会有大量堆分配调用。标准库迭代器在 release 模式下会被大量内联极致优化后几乎和裸指针操作没有区别。标准库的实现可能对缓存局部性做了针对性优化比如节点大小对齐等。这个差距是正常的也是手写容器的核心价值所在——你通过对比真正理解了标准库为什么快快在哪里。如果哪天你给自定义类型实现一个专用链表标准库不能直接用比如你需要节点预分配、对象池化等场景参照 std::list 的设计把这些优化点做进去你的版本也不会差太远。提示如果想进一步优化手写版的性能可以尝试实现一个简单的节点对象池每次插入不再new节点而是从池中复用已经释放的内存减少堆分配次数。这是很多高性能链表的常见优化手段。9. 排查实录一个真实的内存越界问题的完整定位链路最后分享一个我在写这个项目时实际踩过的坑。当时写完核心代码跑增删查改的常规测试全部通过但一旦把 List 对象放进 vector然后对 vector 做扩容程序就在析构时报错而且报错的位置每次都不一样有时在free()里有时在_CrtIsValidHeapPointerWindows 调试器提示里。排查过程如下第一步先确认是不是 List 析构本身有问题。我单独测试连续的 push、pop、clear、析构跑了几万次没崩溃。排除了清空逻辑漏删节点的基本问题。第二步怀疑是拷贝构造没写对。把 List 对象放进 vectorvector 扩容时要拷贝所有元素如果拷贝是浅拷贝元素析构两次就会导致堆错误。这个思路当时觉得最可能于是写了一段专门测试拷贝构造的代码Listint lt1; for (int i 0; i 10; i) lt1.push_back(i); Listint lt2(lt1); lt2.push_back(100);跑完结果完全正常lt1 和 lt2 各自独立。到这里拷贝构造看起来也是对的。第三步把范围缩小到 vector 场景。vector 不止会拷贝还会在扩容时析构旧元素。问题就出在这里——旧元素析构时调用 List 的析构函数析构函数把_pHead置成了nullptr。这本身没问题问题在于我当时写的拷贝构造函数里深拷贝完成之后没有正确修正所有的内部指针有一段代码在拷贝时直接用了一个临时迭代器变量保存当前节点指针但拷贝完成后把这个临时迭代器交给了对象导致析构时遍历到了一块被释放过的内存。具体来说我最初写的是List(const ListT lt) { _pHead new Node; _pHead-_next _pHead; _pHead-_prev _pHead; Node* cur lt._pHead-_next; while (cur ! lt._pHead) { Node* newNode new Node(cur-_data); // ... 这里连接的逻辑有一行写错了把 newNode-_prev 指到了 lt 的节点上 cur cur-_next; } }崩溃的本质就是新链表的节点指到了旧链表的节点上新旧两条链表在中间某处交叉了。新链表析构时删除了旧链表的节点旧链表析构时再删一次双重释放。修复方法也很简单把拷贝构造函数里的插入逻辑全部复用insert(end(), val)因为insert只依赖新链表自己的节点指针完全不碰旧链表的内部结构。这就是为什么我最终建议深拷贝时直接循环push_back(*it)而不要手动逐节点连接——重新实现一遍指针操作虽然看起来更高效但每一行都要小心不要引用到源链表的节点。这次排查花了不少时间但收获非常大。一个很深的体会是链表实现里最危险的操作不是写不出来而是写出一个看起来逻辑正确但节点之间交叉引用的隐藏 bug。这种 bug 的排查手段简单有效的是把所有插入删除统一收口到insert和erase这样出问题的可能性被限制在两三个函数里如果自己手写交接逻辑一旦出错就只能在汇编层面慢慢抠了。