开头如果你已经手写过vector再来看list的模拟实现很可能会被它绕晕一下同样是容器vector的迭代器可以干脆用原生指针list的迭代器却偏偏要包装成一个类vector的内存是一块连续的数组list的节点却散落在堆的各个角落靠一串 _next 和 _prev 指针串起来。我这个星期把C初阶阶段最经典的list容器从零手写了一遍从节点结构、迭代器封装到插入删除、深浅拷贝全部敲了一遍代码。这篇就把完整的设计思路、写代码时容易踩的坑、以及对照std::list验证的方法都整理出来。这篇分享适合两类人一类是已经会用STL基本操作、但想看看list底层到底长什么样的人另一类是正在准备面试、需要能现场手写一个简化版list的C学习者。如果你只想在工程里熟练使用std::list那确实没必要重复造轮子。但如果你想搞懂迭代器为什么要封装、const迭代器怎么用一份代码复用、深浅拷贝在链表里怎么体现模拟一遍是最直接的路径没有之一。1. 动手写list之前先搞懂这个容器到底解决什么问题1.1 为什么C初阶阶段要手写一遍list很多人学完vector的模拟实现之后会以为STL容器不过就是动态数组加三个指针。等真正开始写list才发现完全不是一回事。list底层是由节点组成的链表结构每个节点保存数据、前驱指针、后继指针。数据在物理内存上是不连续的因此天然具备任意位置插入删除的高效率——前提是你已经拿到了那个位置的迭代器。C初阶学习list的模拟实现有几个非常现实的原因理解迭代器为什么被设计成类。vector的迭代器可以用T直接表示因为连续内存天然支持偏移加减。list节点散落堆上node1并不指向下一个节点原生指针在这里彻底失灵。为了让list的遍历、操作跟vector保持统一的语法必须把节点指针包进一个类里重载、--、、-让这个对象行为上像一个智能指针。面试高频考点。手写双向链表、解释迭代器失效规则、对比list和vector的适用场景是面试中非常常见的问题。只背答案很容易在追问下露馅亲手写过一遍面对追问时能直接从底层推导。提升指针操作基本功。vector的插入删除主要靠内存搬移list则全靠指针改向。多一个指针没接好就会断链改了一个指针忘了改另一个就会出现循环引用或内存泄漏。这种严密的指针操作训练在C初阶几乎是绕不开的坎。手写一遍之后再去用std::list你看到接口文档就能想象出内部指针是怎么流动的效率差异、迭代器失效规则也都能从底层推导出来而不是死记硬背。1.2 选型思考为什么STL选择带头双向循环链表网上的链表教程大多从单向不带头链表讲起但STL里std::list的标准实现几乎都是带头节点的双向循环链表。别看这三个限定词多每个都是经过工程权衡的。带头节点解决了空表和边界操作的逻辑问题。不带头链表在头插、删除第一个节点时需要额外判断表是否为空、是否要更新头指针。而带头节点的链表哪怕一个有效数据都没有也始终存在一个固定的头节点。这个头节点就像一个岗亭不管有没有车通过岗亭都在那里所有插入删除逻辑都统一成在某个节点和它的前驱/后继之间做指针操作不需要特判空表场景。双向解决了删除任意节点的痛点。单向链表要删除一个节点得先从头遍历找到它的前驱时间复杂度O(n)。双向链表每个节点都持有prev指针删除时直接拿到前驱任意位置删除都是O(1)代价只是每个节点多存一个指针。循环带来了两个立竿见影的好处。第一tail可以直接通过_pHead-_prev拿到尾插尾删都是O(1)第二迭代器的end()可以设计成指向头节点这样遍历时的终止条件统一是迭代器是否等于end()。更妙的是因为链表是循环的insert在end()节点之前插入等价于在尾节点之后插入一个insert函数就同时覆盖了头插和尾插两种场景。注意模拟实现时别把头节点的data当真。头节点里的数据只是占位垃圾值判断空表、找首元素、找尾元素全部依赖头节点的指针成员不依赖它的data。很多初学者在这里想不通以为空表就是没有节点导致遍历判断写错。2. 底层骨架节点结构和迭代器是list的灵魂2.1 节点结构一个数据加两个指针list的每个节点封装成一个独立结构体保存数据加前驱后继指针。初阶实现直接用struct即可成员默认公有方便访问templateclass T struct ListNode { ListNode(const T val T()) : _prev(nullptr) , _next(nullptr) , _val(val) {} ListNodeT* _prev; ListNodeT* _next; T _val; };构造函数里的默认参数T()保证了内置类型也能安全初始化如果是int就变成0如果是string就变成空串。头节点构造时虽然不会用到_val但统一走这个默认构造逻辑最省心。值得说明的是为什么不把这个结构体直接写进List内部。初阶模拟阶段为了代码清晰建议把ListNode单独放在全局作用域或者放在List类的public区域作为嵌套类型。后面写迭代器时经常需要访问Node*嵌套在private里会让迭代器类获取节点类型变得麻烦。我一般把ListNode定义在List内部public区迭代器通过typename ListT::Node访问既控制命名空间又不破坏封装。2.2 迭代器拉链式推进的类指针list迭代器是模拟实现里最核心、也最容易劝退初学者的部分。先看vectorvectorint::iterator本质上就是int*因为数组内存连续ptr1就是下一个元素ptr5可以直接跳到第五个。list完全不行node1在物理内存上没有意义必须通过node-_next一步一步往后走。所以list迭代器必须是一个类内部保存一个Node*把重载成走_next把--重载成走_prev再把*重载成取_val把-重载成取_val的地址。这样用户写起来跟指针语法一致但内部行为是链表式推进templateclass T, class Ref, class Ptr struct ListIterator { typedef ListNodeT Node; typedef ListIteratorT, Ref, Ptr Self; Node* _pNode; ListIterator(Node* pNode nullptr) : _pNode(pNode) {} Ref operator*() { return _pNode-_val; } Ptr operator-() { return (operator*()); } Self operator() { _pNode _pNode-_next; return *this; } Self operator(int) { Self temp(*this); _pNode _pNode-_next; return temp; } Self operator--() { _pNode _pNode-_prev; return *this; } Self operator--(int) { Self temp(*this); _pNode _pNode-_prev; return temp; } bool operator!(const Self s) const { return _pNode ! s._pNode; } bool operator(const Self s) const { return _pNode s._pNode; } };很多初学者会疑惑为什么要写前缀和后缀两个版本因为C语法规定编译器区分it和it靠的就是参数列表里有没有一个哑元int。前缀直接改完返回自己效率高后缀必须拷贝旧状态、改自己、返回旧状态多一次拷贝。list的迭代器拷贝很轻量这个差异不大但养成正确写法很重要。2.3 一份代码两种用途用模板参数复用const迭代器如果每个容器都老老实实写iterator和const_iterator两个类代码量会翻倍。STL的通用做法是利用模板参数复用同一份实现——让同一个ListIterator模板通过不同模板参数实例化成普通迭代器或const迭代器typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator;这里的Ref控制operator*的返回值Ptr控制operator-的返回值。普通迭代器Ref是T因此*it可读可写const迭代器Ref是const T*it只能读不能写。编译器会在你对const迭代器做写操作时直接报错把错误拦截在编译期。operator-是另一个让初学者困惑的点。当it的元素类型是自定义类Date时it-year 2024这行代码实际被编译器翻译成(it.operator-())-year 2024。也就是先调用迭代器的operator-拿到Date*再用原生指针的-访问成员。理解了这个过程就不会再问为什么迭代器里的operator-返回的是指针而不是引用这类问题。3. 核心接口手写实录构造、插入、删除一步到位3.1 构造函数从带头空表开始List的默认构造只需要创建一个头节点并让它的prev和next都指向自己。这样空表在逻辑上也保持循环templateclass T class List { public: typedef ListNodeT Node; typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; private: void CreateHead() { _pHead new Node; _pHead-_next _pHead; _pHead-_prev _pHead; } Node* _pHead; public: List() { CreateHead(); } templateclass Iterator List(Iterator first, Iterator last) { CreateHead(); while (first ! last) { push_back(*first); first; } } // ... };重点是那个迭代器区间构造函数。它让List可以由任意容器的迭代器区间构造比如用vector的begin/end初始化一个list。写成模板函数是因为不限定传入Iterator必须是list自己的迭代器vector的、deque的、数组指针的都能接收。这个设计让容器之间互相转换非常自然。析构函数则分两步先调用clear清掉所有有效节点再delete头节点。千万不要只delete头节点就完事那样所有有效节点全部泄漏也不要直接从头节点开始逐个delete却忘记头节点本身逻辑很容易乱。先清有效再删哨兵顺序是固定的。3.2 insert和erase最考验指针基本功的地方插入删除是链表操作的重头戏。先说insert它的语义是在pos指向的节点之前插入新节点。因为list是双向循环链表拿到pos节点后它的prev就是前驱四句指针改向就能完成插入iterator insert(iterator pos, const T val) { Node* posNode pos._pNode; Node* prevNode posNode-_prev; Node* newnode new Node(val); prevNode-_next newnode; newnode-_prev prevNode; newnode-_next posNode; posNode-_prev newnode; return iterator(newnode); }为什么返回新插入节点的迭代器因为调用方可能需要在插入后继续处理新节点比如连续在同一个位置插入多个值。返回新节点的迭代器调用方才能继续基于新位置操作。push_back和push_front都可以复用insert。push_back就是insert(end(), val)因为end()指向头节点在头节点之前插入实际上是在尾节点之后插入。我建议在初阶版本里就这么实现代码少且逻辑统一。如果担心多一次函数调用开销再单独写tail指针版本的push_back也不迟。erase的实现同样只有三步指针操作iterator erase(iterator pos) { Node* posNode pos._pNode; Node* prevNode posNode-_prev; Node* nextNode posNode-_next; prevNode-_next nextNode; nextNode-_prev prevNode; delete posNode; return iterator(nextNode); }这里最关键的是返回值。被erase的节点在delete之后就成了悬空指针如果调用方继续使用pos迭代器就是访问已经释放的内存属于未定义行为。所以erase返回被删除节点的下一个有效迭代器让调用方可以安全地继续遍历。这个约定对list、vector、deque通用但list的场景尤其典型因为list的erase在整个链表上频繁进行。提示手动操作链表时任何时刻都要想清楚谁还指向这个节点。改prev的_next时新节点的prev是不是已经接好改next的_prev时原prev的_next是否已经指向新节点。四句指针操作少写任何一句链表就会断。3.3 拷贝与赋值深拷贝才能活下来拷贝构造必须做节点级深拷贝。不能直接_pHead l._pHead否则两个List对象共享同一堆节点析构时double free修改一个会连累另一个。初阶模拟最直观的写法是先创建自己的头节点再遍历源链表逐一push_back数据List(const ListT l) { CreateHead(); for (auto it l.begin(); it ! l.end(); it) { push_back(*it); } }注意这里l.begin()调用的是const版本的begin返回const_iterator*it是const T正好可以作为push_back的参数语义正确。赋值运算符我推荐传值swap写法ListT operator(ListT l) { swap(l); return *this; } void swap(ListT l) { std::swap(_pHead, l._pHead); }这个写法的妙处在于参数l按值传入时已经利用拷贝构造函数生成了当前对象的副本拥有独立的节点资源。swap之后当前对象拿到了副本的数据临时对象l则接管了当前对象原来的旧节点。函数结束时l析构旧资源被自动释放不需要显式写delete循环。整个过程天然具备异常安全性——如果拷贝构造抛异常swap还没执行当前对象保持原状。很多初学者会问operator的参数为什么不写成const ListT如果传引用swap之后临时对象不存在旧资源没人释放还得手动写一遍clear。传值虽然多了一次拷贝但换来的是简洁和异常安全是工程上很经典的取舍。3.4 常用接口总览与vector对比表一个完整的初阶List类还需要提供begin/end的重载、clear、size、empty等接口。这些实现都比较直接我把最容易混淆的list和vector行为整理成表格方便对照记忆对比维度listvector内存布局节点分散在堆上零散分配连续内存块缓存友好随机访问不支持无operator[]支持O(1)按下标访问头部插入删除O(1)直接改头节点指针O(n)需要整体搬移元素尾部插入删除O(1)通过头节点的prev拿到tail均摊O(1)扩容时O(n)已知位置插入删除O(1)只需局部指针改向O(n)后续元素全部搬移insert后迭代器原迭代器不失效可能导致全部迭代器失效扩容erase后迭代器仅被删除位置的迭代器失效被删位置及其后全部迭代器失效size接口std::list为O(1)初阶模拟版O(n)O(1)直接维护_size这张表基本覆盖了面试里最常见的list与vector对比题。核心记忆点可以浓缩成一句话list牺牲了随机访问换来了任意位置插入删除的稳定性和迭代器稳定性vector则相反用连续内存换来了随机访问和缓存性能。4. 模拟实现list踩坑实录4.1 坑一以为空链表是没有节点我第一次写clear时循环条件写成while (cur ! nullptr)遍历完最后一个节点后cur变成nullptr但头节点的prev指针并没有被修复后面再调用push_back时整个链表就乱了。正确的边界判断应该是cur回到头节点而不是cur变成空指针void clear() { Node* cur _pHead-_next; while (cur ! _pHead) { Node* next cur-_next; delete cur; cur next; } _pHead-_next _pHead; _pHead-_prev _pHead; }这个坑的本质是循环链表里没有空指针循环终止条件永远是比较是否回到哨兵节点。写惯单链表的人很容易下意识用nullptr判断结果就是在头节点和尾节点之间打出死循环或漏掉修复环。写完clear之后一定要测试清空后再插入的场景很多隐藏bug会在这一步暴露。4.2 坑二erase之后继续使用旧迭代器list的erase只让被删除节点的迭代器失效其他迭代器不受影响。这是list的优点但也容易让人放松警惕。被删除的那个迭代器继续使用本质上就是访问已经delete的堆内存不报错是运气报错是必然。正确的做法是立刻赋值接收erase的返回值auto it lst.begin(); while (it ! lst.end()) { if (条件) { it lst.erase(it); // 循环内erase必须接收返回值 } else { it; // 不删除时才手动递增 } }这个erase后赋值的写法是所有STL容器遍历删除的统一范式。忘掉这一步程序可能在某个数据规模下正常运行换一组输入就随机崩溃非常难排查。4.3 坑三浅拷贝导致double free如果你图省事在拷贝构造里直接让_pHead l._pHead两个对象就共享了同一串链表节点。程序退出时第一个对象析构delete了全部节点第二个对象析构时再delete一遍已经释放的内存直接崩溃。这个问题在调试器里表现得很怪异——崩溃点可能在随机的位置因为堆已经被破坏了。排查方法也很简单构造两个List修改其中一个打印另一个发现数据跟着变或者程序退出时在析构函数处断点看到同一个地址被释放两次。修复方法就是3.3节里的深拷贝。这里还引申出一个道理凡是类内部持有堆资源的三/五法则至少要遵守三件套——析构、拷贝构造、赋值运算符缺一个就是隐患。4.4 坑四迭代器失效规则和vector反着记实际写代码时list和vector的迭代器失效规则经常被人记混。我建议按底层原理推vector的insert如果触发扩容所有迭代器、指针、引用全部失效没触发扩容也只有插入位置之后的迭代器失效因为元素被搬移了。list的insert只是新建一个节点、改四句指针原有节点的内存地址完全不变因此原迭代器一个都不会失效。list的erase只让被删除那一个节点对应的迭代器失效其他全部有效。记住这一条的实惠之处在于在list中你可以放心地先保存某个迭代器在别处插入元素再回来继续使用这个迭代器而vector几乎不建议这么做。有经验的C开发者会专门利用list迭代器稳定的特性在需要长期暴露对象地址的场景里选用list而不是vector。5. 测试验证与std::list对照5.1 功能测试用例模拟实现写完不能只看编译通过就收工。我把测试用例分成几组每一组都有明确的验证目标#include iostream #include MyList.h using namespace std; void Print(const Listint lst) { for (auto it lst.begin(); it ! lst.end(); it) { cout *it ; } cout endl; } int main() { // 测试1尾插与遍历 Listint l; for (int i 1; i 5; i) l.push_back(i); Print(l); // 期望 1 2 3 4 5 // 测试2头插 l.push_front(0); Print(l); // 期望 0 1 2 3 4 5 // 测试3中间位置插入 auto pos l.begin(); pos; pos; l.insert(pos, 99); Print(l); // 期望 0 1 99 2 3 4 5 // 测试4删除指定位置 auto del l.begin(); del; l.erase(del); Print(l); // 期望 0 99 2 3 4 5 // 测试5深拷贝验证 Listint copy(l); for (int x : copy) x * 2; Print(l); // 期望 0 99 2 3 4 5原表不受影响 Print(copy); // 期望 0 198 4 6 8 10 // 测试6clear后复用 l.clear(); l.push_back(7); Print(l); // 期望 7 return 0; }如果上面的测试都能通过说明构造、析构、插入删除、深浅拷贝都没有大问题。尤其测试5范围for能修改copy里的元素说明普通iterator返回的是可写的TPrint函数接收const List 却能正常遍历说明const_iterator的路径也走通了。5.2 与std::list的行为和性能差异初阶模拟版和真实std::list存在几个关键差异知道这些差异能帮你更好地理解STL的工程复杂度size复杂度std::list在C11之后保证size为O(1)因为它维护了一个计数器成员。初阶模拟版没有计数器size需要遍历整个链表是O(n)。自己加一个_size成员并同步更新就可以把这个差异补上。节点内存分配std::list的节点内存默认通过allocator分配而且分配的是节点大小的内存块不是先构造T再套节点。真实实现中节点中存放的是T的存储空间通过placement new构造。初阶模拟版用new Node(val)简单直接教学上完全够用但性能会有差距。专属成员函数std::list还有splice、merge、unique、sort、remove等专属操作。这些操作充分利用了list节点可拆装的特性是工程里非常实用的功能初阶模拟版并没有实现。想深入的话splice是下一个好目标。性能层面也要有正确认知。list的O(1)插入删除是已知位置前提下的理论复杂度实际运行时节点分散缓存命中率远低于vector。真实工程里如果元素数量不大且以遍历为主vector往往反而比list更快。list的优势体现在海量元素、频繁在中间插入删除、需要保持迭代器长期有效。模拟实现一遍list后你会对复杂度低不等于跑得快这句话有更深的体会。6. 个人总结与扩展方向6.1 手写list给我的四个收获写这一版list模拟实现给我带来最直接的四个改变。第一指针操作变得严密很多写完insert/erase的几句指针改向心里会自动过一遍每个被改动节点还有没有被谁引用这个意识在写任何涉及链表、树、图的代码时都受用。第二真正理解了迭代器的边界它既可以封装连续内存也可以封装链式内存用户语法统一底层逻辑却可以截然不同。第三深刻体会到深浅拷贝不是概念题list的double free会在你稍微马虎时立刻找上门。第四对选择容器要看场景这句话有了实感list和vector没有绝对优劣只有匹配不匹配。6.2 想继续深入可以做这些扩展如果你的目标不止于C初阶可以在这一版基础上做几个升级。最推荐的是反向迭代器给ListIterator包一层ReverseIterator适配器把映射成内部的--就能复用现有迭代器逻辑。其次是给List维护_size成员让size变成O(1)同时注意所有插入删除操作都要同步更新计数器。再往深走可以做splice接口实现两个list之间O(1)的节点转移或者研究内存池分配器为节点分配做缓存优化。我写完这个模拟版本之后再回头使用std::list最大的变化是看到它的接口文档脑子里能直接浮现出节点指针的流动路径被问到迭代器失效也能从底层原理推导而不是死记规则。如果你也卡在容器原理这道坎上强烈建议动手抄一遍代码然后自己设计测试用例去跑、去改bug、再跑这个过程比看十篇源码分析都管用。
手写C++ list：迭代器封装与双向循环链表底层实现
开头如果你已经手写过vector再来看list的模拟实现很可能会被它绕晕一下同样是容器vector的迭代器可以干脆用原生指针list的迭代器却偏偏要包装成一个类vector的内存是一块连续的数组list的节点却散落在堆的各个角落靠一串 _next 和 _prev 指针串起来。我这个星期把C初阶阶段最经典的list容器从零手写了一遍从节点结构、迭代器封装到插入删除、深浅拷贝全部敲了一遍代码。这篇就把完整的设计思路、写代码时容易踩的坑、以及对照std::list验证的方法都整理出来。这篇分享适合两类人一类是已经会用STL基本操作、但想看看list底层到底长什么样的人另一类是正在准备面试、需要能现场手写一个简化版list的C学习者。如果你只想在工程里熟练使用std::list那确实没必要重复造轮子。但如果你想搞懂迭代器为什么要封装、const迭代器怎么用一份代码复用、深浅拷贝在链表里怎么体现模拟一遍是最直接的路径没有之一。1. 动手写list之前先搞懂这个容器到底解决什么问题1.1 为什么C初阶阶段要手写一遍list很多人学完vector的模拟实现之后会以为STL容器不过就是动态数组加三个指针。等真正开始写list才发现完全不是一回事。list底层是由节点组成的链表结构每个节点保存数据、前驱指针、后继指针。数据在物理内存上是不连续的因此天然具备任意位置插入删除的高效率——前提是你已经拿到了那个位置的迭代器。C初阶学习list的模拟实现有几个非常现实的原因理解迭代器为什么被设计成类。vector的迭代器可以用T直接表示因为连续内存天然支持偏移加减。list节点散落堆上node1并不指向下一个节点原生指针在这里彻底失灵。为了让list的遍历、操作跟vector保持统一的语法必须把节点指针包进一个类里重载、--、、-让这个对象行为上像一个智能指针。面试高频考点。手写双向链表、解释迭代器失效规则、对比list和vector的适用场景是面试中非常常见的问题。只背答案很容易在追问下露馅亲手写过一遍面对追问时能直接从底层推导。提升指针操作基本功。vector的插入删除主要靠内存搬移list则全靠指针改向。多一个指针没接好就会断链改了一个指针忘了改另一个就会出现循环引用或内存泄漏。这种严密的指针操作训练在C初阶几乎是绕不开的坎。手写一遍之后再去用std::list你看到接口文档就能想象出内部指针是怎么流动的效率差异、迭代器失效规则也都能从底层推导出来而不是死记硬背。1.2 选型思考为什么STL选择带头双向循环链表网上的链表教程大多从单向不带头链表讲起但STL里std::list的标准实现几乎都是带头节点的双向循环链表。别看这三个限定词多每个都是经过工程权衡的。带头节点解决了空表和边界操作的逻辑问题。不带头链表在头插、删除第一个节点时需要额外判断表是否为空、是否要更新头指针。而带头节点的链表哪怕一个有效数据都没有也始终存在一个固定的头节点。这个头节点就像一个岗亭不管有没有车通过岗亭都在那里所有插入删除逻辑都统一成在某个节点和它的前驱/后继之间做指针操作不需要特判空表场景。双向解决了删除任意节点的痛点。单向链表要删除一个节点得先从头遍历找到它的前驱时间复杂度O(n)。双向链表每个节点都持有prev指针删除时直接拿到前驱任意位置删除都是O(1)代价只是每个节点多存一个指针。循环带来了两个立竿见影的好处。第一tail可以直接通过_pHead-_prev拿到尾插尾删都是O(1)第二迭代器的end()可以设计成指向头节点这样遍历时的终止条件统一是迭代器是否等于end()。更妙的是因为链表是循环的insert在end()节点之前插入等价于在尾节点之后插入一个insert函数就同时覆盖了头插和尾插两种场景。注意模拟实现时别把头节点的data当真。头节点里的数据只是占位垃圾值判断空表、找首元素、找尾元素全部依赖头节点的指针成员不依赖它的data。很多初学者在这里想不通以为空表就是没有节点导致遍历判断写错。2. 底层骨架节点结构和迭代器是list的灵魂2.1 节点结构一个数据加两个指针list的每个节点封装成一个独立结构体保存数据加前驱后继指针。初阶实现直接用struct即可成员默认公有方便访问templateclass T struct ListNode { ListNode(const T val T()) : _prev(nullptr) , _next(nullptr) , _val(val) {} ListNodeT* _prev; ListNodeT* _next; T _val; };构造函数里的默认参数T()保证了内置类型也能安全初始化如果是int就变成0如果是string就变成空串。头节点构造时虽然不会用到_val但统一走这个默认构造逻辑最省心。值得说明的是为什么不把这个结构体直接写进List内部。初阶模拟阶段为了代码清晰建议把ListNode单独放在全局作用域或者放在List类的public区域作为嵌套类型。后面写迭代器时经常需要访问Node*嵌套在private里会让迭代器类获取节点类型变得麻烦。我一般把ListNode定义在List内部public区迭代器通过typename ListT::Node访问既控制命名空间又不破坏封装。2.2 迭代器拉链式推进的类指针list迭代器是模拟实现里最核心、也最容易劝退初学者的部分。先看vectorvectorint::iterator本质上就是int*因为数组内存连续ptr1就是下一个元素ptr5可以直接跳到第五个。list完全不行node1在物理内存上没有意义必须通过node-_next一步一步往后走。所以list迭代器必须是一个类内部保存一个Node*把重载成走_next把--重载成走_prev再把*重载成取_val把-重载成取_val的地址。这样用户写起来跟指针语法一致但内部行为是链表式推进templateclass T, class Ref, class Ptr struct ListIterator { typedef ListNodeT Node; typedef ListIteratorT, Ref, Ptr Self; Node* _pNode; ListIterator(Node* pNode nullptr) : _pNode(pNode) {} Ref operator*() { return _pNode-_val; } Ptr operator-() { return (operator*()); } Self operator() { _pNode _pNode-_next; return *this; } Self operator(int) { Self temp(*this); _pNode _pNode-_next; return temp; } Self operator--() { _pNode _pNode-_prev; return *this; } Self operator--(int) { Self temp(*this); _pNode _pNode-_prev; return temp; } bool operator!(const Self s) const { return _pNode ! s._pNode; } bool operator(const Self s) const { return _pNode s._pNode; } };很多初学者会疑惑为什么要写前缀和后缀两个版本因为C语法规定编译器区分it和it靠的就是参数列表里有没有一个哑元int。前缀直接改完返回自己效率高后缀必须拷贝旧状态、改自己、返回旧状态多一次拷贝。list的迭代器拷贝很轻量这个差异不大但养成正确写法很重要。2.3 一份代码两种用途用模板参数复用const迭代器如果每个容器都老老实实写iterator和const_iterator两个类代码量会翻倍。STL的通用做法是利用模板参数复用同一份实现——让同一个ListIterator模板通过不同模板参数实例化成普通迭代器或const迭代器typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator;这里的Ref控制operator*的返回值Ptr控制operator-的返回值。普通迭代器Ref是T因此*it可读可写const迭代器Ref是const T*it只能读不能写。编译器会在你对const迭代器做写操作时直接报错把错误拦截在编译期。operator-是另一个让初学者困惑的点。当it的元素类型是自定义类Date时it-year 2024这行代码实际被编译器翻译成(it.operator-())-year 2024。也就是先调用迭代器的operator-拿到Date*再用原生指针的-访问成员。理解了这个过程就不会再问为什么迭代器里的operator-返回的是指针而不是引用这类问题。3. 核心接口手写实录构造、插入、删除一步到位3.1 构造函数从带头空表开始List的默认构造只需要创建一个头节点并让它的prev和next都指向自己。这样空表在逻辑上也保持循环templateclass T class List { public: typedef ListNodeT Node; typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; private: void CreateHead() { _pHead new Node; _pHead-_next _pHead; _pHead-_prev _pHead; } Node* _pHead; public: List() { CreateHead(); } templateclass Iterator List(Iterator first, Iterator last) { CreateHead(); while (first ! last) { push_back(*first); first; } } // ... };重点是那个迭代器区间构造函数。它让List可以由任意容器的迭代器区间构造比如用vector的begin/end初始化一个list。写成模板函数是因为不限定传入Iterator必须是list自己的迭代器vector的、deque的、数组指针的都能接收。这个设计让容器之间互相转换非常自然。析构函数则分两步先调用clear清掉所有有效节点再delete头节点。千万不要只delete头节点就完事那样所有有效节点全部泄漏也不要直接从头节点开始逐个delete却忘记头节点本身逻辑很容易乱。先清有效再删哨兵顺序是固定的。3.2 insert和erase最考验指针基本功的地方插入删除是链表操作的重头戏。先说insert它的语义是在pos指向的节点之前插入新节点。因为list是双向循环链表拿到pos节点后它的prev就是前驱四句指针改向就能完成插入iterator insert(iterator pos, const T val) { Node* posNode pos._pNode; Node* prevNode posNode-_prev; Node* newnode new Node(val); prevNode-_next newnode; newnode-_prev prevNode; newnode-_next posNode; posNode-_prev newnode; return iterator(newnode); }为什么返回新插入节点的迭代器因为调用方可能需要在插入后继续处理新节点比如连续在同一个位置插入多个值。返回新节点的迭代器调用方才能继续基于新位置操作。push_back和push_front都可以复用insert。push_back就是insert(end(), val)因为end()指向头节点在头节点之前插入实际上是在尾节点之后插入。我建议在初阶版本里就这么实现代码少且逻辑统一。如果担心多一次函数调用开销再单独写tail指针版本的push_back也不迟。erase的实现同样只有三步指针操作iterator erase(iterator pos) { Node* posNode pos._pNode; Node* prevNode posNode-_prev; Node* nextNode posNode-_next; prevNode-_next nextNode; nextNode-_prev prevNode; delete posNode; return iterator(nextNode); }这里最关键的是返回值。被erase的节点在delete之后就成了悬空指针如果调用方继续使用pos迭代器就是访问已经释放的内存属于未定义行为。所以erase返回被删除节点的下一个有效迭代器让调用方可以安全地继续遍历。这个约定对list、vector、deque通用但list的场景尤其典型因为list的erase在整个链表上频繁进行。提示手动操作链表时任何时刻都要想清楚谁还指向这个节点。改prev的_next时新节点的prev是不是已经接好改next的_prev时原prev的_next是否已经指向新节点。四句指针操作少写任何一句链表就会断。3.3 拷贝与赋值深拷贝才能活下来拷贝构造必须做节点级深拷贝。不能直接_pHead l._pHead否则两个List对象共享同一堆节点析构时double free修改一个会连累另一个。初阶模拟最直观的写法是先创建自己的头节点再遍历源链表逐一push_back数据List(const ListT l) { CreateHead(); for (auto it l.begin(); it ! l.end(); it) { push_back(*it); } }注意这里l.begin()调用的是const版本的begin返回const_iterator*it是const T正好可以作为push_back的参数语义正确。赋值运算符我推荐传值swap写法ListT operator(ListT l) { swap(l); return *this; } void swap(ListT l) { std::swap(_pHead, l._pHead); }这个写法的妙处在于参数l按值传入时已经利用拷贝构造函数生成了当前对象的副本拥有独立的节点资源。swap之后当前对象拿到了副本的数据临时对象l则接管了当前对象原来的旧节点。函数结束时l析构旧资源被自动释放不需要显式写delete循环。整个过程天然具备异常安全性——如果拷贝构造抛异常swap还没执行当前对象保持原状。很多初学者会问operator的参数为什么不写成const ListT如果传引用swap之后临时对象不存在旧资源没人释放还得手动写一遍clear。传值虽然多了一次拷贝但换来的是简洁和异常安全是工程上很经典的取舍。3.4 常用接口总览与vector对比表一个完整的初阶List类还需要提供begin/end的重载、clear、size、empty等接口。这些实现都比较直接我把最容易混淆的list和vector行为整理成表格方便对照记忆对比维度listvector内存布局节点分散在堆上零散分配连续内存块缓存友好随机访问不支持无operator[]支持O(1)按下标访问头部插入删除O(1)直接改头节点指针O(n)需要整体搬移元素尾部插入删除O(1)通过头节点的prev拿到tail均摊O(1)扩容时O(n)已知位置插入删除O(1)只需局部指针改向O(n)后续元素全部搬移insert后迭代器原迭代器不失效可能导致全部迭代器失效扩容erase后迭代器仅被删除位置的迭代器失效被删位置及其后全部迭代器失效size接口std::list为O(1)初阶模拟版O(n)O(1)直接维护_size这张表基本覆盖了面试里最常见的list与vector对比题。核心记忆点可以浓缩成一句话list牺牲了随机访问换来了任意位置插入删除的稳定性和迭代器稳定性vector则相反用连续内存换来了随机访问和缓存性能。4. 模拟实现list踩坑实录4.1 坑一以为空链表是没有节点我第一次写clear时循环条件写成while (cur ! nullptr)遍历完最后一个节点后cur变成nullptr但头节点的prev指针并没有被修复后面再调用push_back时整个链表就乱了。正确的边界判断应该是cur回到头节点而不是cur变成空指针void clear() { Node* cur _pHead-_next; while (cur ! _pHead) { Node* next cur-_next; delete cur; cur next; } _pHead-_next _pHead; _pHead-_prev _pHead; }这个坑的本质是循环链表里没有空指针循环终止条件永远是比较是否回到哨兵节点。写惯单链表的人很容易下意识用nullptr判断结果就是在头节点和尾节点之间打出死循环或漏掉修复环。写完clear之后一定要测试清空后再插入的场景很多隐藏bug会在这一步暴露。4.2 坑二erase之后继续使用旧迭代器list的erase只让被删除节点的迭代器失效其他迭代器不受影响。这是list的优点但也容易让人放松警惕。被删除的那个迭代器继续使用本质上就是访问已经delete的堆内存不报错是运气报错是必然。正确的做法是立刻赋值接收erase的返回值auto it lst.begin(); while (it ! lst.end()) { if (条件) { it lst.erase(it); // 循环内erase必须接收返回值 } else { it; // 不删除时才手动递增 } }这个erase后赋值的写法是所有STL容器遍历删除的统一范式。忘掉这一步程序可能在某个数据规模下正常运行换一组输入就随机崩溃非常难排查。4.3 坑三浅拷贝导致double free如果你图省事在拷贝构造里直接让_pHead l._pHead两个对象就共享了同一串链表节点。程序退出时第一个对象析构delete了全部节点第二个对象析构时再delete一遍已经释放的内存直接崩溃。这个问题在调试器里表现得很怪异——崩溃点可能在随机的位置因为堆已经被破坏了。排查方法也很简单构造两个List修改其中一个打印另一个发现数据跟着变或者程序退出时在析构函数处断点看到同一个地址被释放两次。修复方法就是3.3节里的深拷贝。这里还引申出一个道理凡是类内部持有堆资源的三/五法则至少要遵守三件套——析构、拷贝构造、赋值运算符缺一个就是隐患。4.4 坑四迭代器失效规则和vector反着记实际写代码时list和vector的迭代器失效规则经常被人记混。我建议按底层原理推vector的insert如果触发扩容所有迭代器、指针、引用全部失效没触发扩容也只有插入位置之后的迭代器失效因为元素被搬移了。list的insert只是新建一个节点、改四句指针原有节点的内存地址完全不变因此原迭代器一个都不会失效。list的erase只让被删除那一个节点对应的迭代器失效其他全部有效。记住这一条的实惠之处在于在list中你可以放心地先保存某个迭代器在别处插入元素再回来继续使用这个迭代器而vector几乎不建议这么做。有经验的C开发者会专门利用list迭代器稳定的特性在需要长期暴露对象地址的场景里选用list而不是vector。5. 测试验证与std::list对照5.1 功能测试用例模拟实现写完不能只看编译通过就收工。我把测试用例分成几组每一组都有明确的验证目标#include iostream #include MyList.h using namespace std; void Print(const Listint lst) { for (auto it lst.begin(); it ! lst.end(); it) { cout *it ; } cout endl; } int main() { // 测试1尾插与遍历 Listint l; for (int i 1; i 5; i) l.push_back(i); Print(l); // 期望 1 2 3 4 5 // 测试2头插 l.push_front(0); Print(l); // 期望 0 1 2 3 4 5 // 测试3中间位置插入 auto pos l.begin(); pos; pos; l.insert(pos, 99); Print(l); // 期望 0 1 99 2 3 4 5 // 测试4删除指定位置 auto del l.begin(); del; l.erase(del); Print(l); // 期望 0 99 2 3 4 5 // 测试5深拷贝验证 Listint copy(l); for (int x : copy) x * 2; Print(l); // 期望 0 99 2 3 4 5原表不受影响 Print(copy); // 期望 0 198 4 6 8 10 // 测试6clear后复用 l.clear(); l.push_back(7); Print(l); // 期望 7 return 0; }如果上面的测试都能通过说明构造、析构、插入删除、深浅拷贝都没有大问题。尤其测试5范围for能修改copy里的元素说明普通iterator返回的是可写的TPrint函数接收const List 却能正常遍历说明const_iterator的路径也走通了。5.2 与std::list的行为和性能差异初阶模拟版和真实std::list存在几个关键差异知道这些差异能帮你更好地理解STL的工程复杂度size复杂度std::list在C11之后保证size为O(1)因为它维护了一个计数器成员。初阶模拟版没有计数器size需要遍历整个链表是O(n)。自己加一个_size成员并同步更新就可以把这个差异补上。节点内存分配std::list的节点内存默认通过allocator分配而且分配的是节点大小的内存块不是先构造T再套节点。真实实现中节点中存放的是T的存储空间通过placement new构造。初阶模拟版用new Node(val)简单直接教学上完全够用但性能会有差距。专属成员函数std::list还有splice、merge、unique、sort、remove等专属操作。这些操作充分利用了list节点可拆装的特性是工程里非常实用的功能初阶模拟版并没有实现。想深入的话splice是下一个好目标。性能层面也要有正确认知。list的O(1)插入删除是已知位置前提下的理论复杂度实际运行时节点分散缓存命中率远低于vector。真实工程里如果元素数量不大且以遍历为主vector往往反而比list更快。list的优势体现在海量元素、频繁在中间插入删除、需要保持迭代器长期有效。模拟实现一遍list后你会对复杂度低不等于跑得快这句话有更深的体会。6. 个人总结与扩展方向6.1 手写list给我的四个收获写这一版list模拟实现给我带来最直接的四个改变。第一指针操作变得严密很多写完insert/erase的几句指针改向心里会自动过一遍每个被改动节点还有没有被谁引用这个意识在写任何涉及链表、树、图的代码时都受用。第二真正理解了迭代器的边界它既可以封装连续内存也可以封装链式内存用户语法统一底层逻辑却可以截然不同。第三深刻体会到深浅拷贝不是概念题list的double free会在你稍微马虎时立刻找上门。第四对选择容器要看场景这句话有了实感list和vector没有绝对优劣只有匹配不匹配。6.2 想继续深入可以做这些扩展如果你的目标不止于C初阶可以在这一版基础上做几个升级。最推荐的是反向迭代器给ListIterator包一层ReverseIterator适配器把映射成内部的--就能复用现有迭代器逻辑。其次是给List维护_size成员让size变成O(1)同时注意所有插入删除操作都要同步更新计数器。再往深走可以做splice接口实现两个list之间O(1)的节点转移或者研究内存池分配器为节点分配做缓存优化。我写完这个模拟版本之后再回头使用std::list最大的变化是看到它的接口文档脑子里能直接浮现出节点指针的流动路径被问到迭代器失效也能从底层原理推导而不是死记规则。如果你也卡在容器原理这道坎上强烈建议动手抄一遍代码然后自己设计测试用例去跑、去改bug、再跑这个过程比看十篇源码分析都管用。