一文带你彻底搞懂 C++ list —— 使用与模拟实现

一、引言相较于vector的连续线性空间, list就显得复杂许多, 它的好处是每次插入或删除一个元素, 就配置或释放一下元素空间. 因此, 李斯特对于空间的运用有绝对的精准, 一点也不浪费. 而且, 对于任何位置的元素阐述或元素一处, list永远是常数时间.vector 底层是连续内存随机访问 O(1)插入删除 O(n)而 list 底层是双向链表插入删除 O(1)随机访问 O(n)。两者看似互补但在实际开发中很多初学者对 list 的理解往往停留在知道怎么调用的层面——会用 push_back、会用迭代器遍历但问到为什么 list 的迭代器不支持 3、哨兵头节点有什么作用就说不清了。根本原因在于你没有亲手实现过它。本文将从两个角度带你吃透 list使用篇——覆盖 list 最常用的接口配合代码示例快速上手模拟实现篇——从节点设计到迭代器封装从哨兵头节点到 insert/erase逐行手写一个完整的 zy::list读完这篇文章你不仅能熟练使用 std::list还能清晰说出它底层每一行代码的设计意图。二、list 使用篇在动手实现之前先看看 std::list 怎么用.2.1 基本操作#includeiostream#includelistusingnamespacestd;intmain(){listintlt;// 构造空listlt.push_back(1);// 尾插lt.push_back(2);lt.push_back(3);lt.push_front(0);// 头插coutlt.front()endl;// 0 取头节点coutlt.back()endl;// 3 取尾节点lt.pop_front();// 头删lt.pop_back();// 尾删coutlt.size()endl;// 2 list的大小coutlt.empty()endl;// 0 (false) list是否为空return0;}以上是list的最基本的用法.2.2 遍历方式listintlt{1,2,3,4,5};// 方式一迭代器autoitlt.begin();while(it!lt.end()){cout*it ;it;}coutendl;// 方式二范围 forC11 起本质也是迭代器for(autox:lt)coutx ;coutendl;注意这里 it 或是 it不能是it(数字). 因为 list 迭代器是双向迭代器BidirectionalIterator不支持 it 3 这样的随机访问——这也正是因为我们后面实现时只重载了 operator 而没有重载 operator。2.3 插入与删除listintlt{1,2,3,4,5};autoitlt.begin();it;it;// it 指向 3lt.insert(it,99);// 在 3 之前插入 99 → {1, 2, 99, 3, 4, 5}lt.erase(it);// 删除 3 → {1, 2, 99, 4, 5}⚠️迭代器失效 erase 之后被删除位置的迭代器失效但 erase 会返回下一个有效迭代器。insert 不会使任何原有迭代器失效区别于 vector。这是初学阶段最容易踩的坑把两者对比着看就很清楚了vectorintv{1,2,3,4,5};autovitv.begin()2;// vit 指向 3v.insert(vit,99);// ❌ vector 可能扩容所有迭代器失效// vit 已经失效不能再使用v.erase(vit);// ❌ vit 在上一行已经失效操作listvectorinsert 单个元素✅ 不影响任何已有迭代器❌ 若扩容全部失效若未扩容插入位置之后的迭代器失效erase 单个元素✅ 仅被删除的迭代器失效❌ 被删除位置之后的迭代器全部失效insert / erase 多个✅ 同上❌ 影响范围更大根本原因在于内存布局不同vector 是连续内存插入删除会导致元素挪动指向挪动过位置的迭代器自然失效而 list 每个节点独立分配插入删除只修改相邻节点的指针其他节点的地址不变指向它们的迭代器自然有效。2.4 构造函数一览listintlt1;// 默认构造listintlt2(5,10);// 5 个 10 n个val构造listintlt3{1,2,3,4};// initializer_listlistintlt4(lt3.begin(),lt3.end());// 迭代器区间构造listintlt5(lt4);// 拷贝构造lt5lt2;// 赋值重载initializer_list 是什么C11 引入的轻量级类模板本质是一个编译器生成的临时数组的包装。当你写 {1, 2, 3, 4} 时编译器构造一个 initializer_list int 对象list 的构造函数再从中逐个拷贝元素。它只有三个成员首指针、尾指针和长度遍历方式就是简单的指针移动无额外开销。几乎所有 STL 容器都支持用 {} 列表初始化本质就是这个重载。2.5 进阶操作——Operations实际场景中list 还有一些 STL 其他容器没有的独门操作定义在 cplusplus.com 的 Operations 分类下操作作用复杂度splice将一个 list 中的元素转移到另一个 list零拷贝只改指针O(1) 或 O(n)remove删除所有等于指定值的元素O(n)remove_if删除所有满足谓词条件的元素O(n)unique删除连续重复元素仅保留第一个O(n)merge合并两个已排序的 list归并O(n)sort排序list 不能用 std::sort因为需要随机访问迭代器O(n log n)reverse反转链表O(n)这些操作大多利用了 list 链式结构的特性:splice 改几个指针就能把节点从一个链表搬到另一个零拷贝开销sort 用的是归并排序不依赖随机访问remove / unique 直接遍历 erase 即可。⚠️ 注意std::list 自己实现了 sort但比 std::sort 慢得多。如果数据量大且不需要频繁中间插入优先用 vector std::sort。list模拟实现3.1 list 由什么组成一个list从结构上看,可以由,一下四部分组成:如图:节点 ListNode T — 存储数据的单元每个节点包含 prev、next 两个指针和一个数据域 _ val。节点们通过指针串联成双向链表。哨兵头节点 — 一个不存有效数据的特殊节点作为链表的锚点。它的 next 指向第一个有效节点prev 指向最后一个有效节点。空表时自己指向自己。迭代器 list_iterator — 对节点指针的封装。因为在链表上 p 不能跳到下一个元素必须通过重载运算符来定义移动规则。迭代器让用户可以像遍历数组一样遍历链表。list 类本身 — 对外暴露的容器接口持有 _ head 和 _ size管理所有节点的生命周期提供 push_back、insert、erase 等操作。下面按这个顺序逐一展开。3.2 节点 ListNode T 链表的基本单元是一个节点。双向链表的每个节点需要三个信息存什么数据、前一个节点是谁、后一个节点是谁。templatetypenameTstructListNode{ListNodeT*prev;// 前驱指针ListNodeT*next;// 后继指针T _val;// 数据域ListNode(constTvalT()):_val(val),prev(nullptr),next(nullptr){}};为什么用 struct 而不是 class节点只是内部的数据结构所有成员对外公开用 struct 更简洁。构造函数为什么给默认参数 T()这是为了支持哨兵节点的创建。哨兵节点不存有效数据但创建时仍然需要调用构造函数——new Node() 会使用默认值 T() 初始化 _ val。对于内置类型如 intint() 就是 0对于自定义类型会调用其默认构造函数。指针指向关系示意每个节点的 prev 指向前一个next 指向后一个。这就是双向链表最朴素的结构。多个 ListNode 串联起来再加上哨兵头和 list 类的管理就构成了完整的 list。3.3 哨兵头节点先看一个问题空表长什么样没有哨兵的话空表就是 _ head nullptr。这会导致很多操作需要特判// 没有哨兵时begin() 得这么写iteratorbegin(){if(_headnullptr)returniterator(nullptr);// end 也是 nullptr那 begin end?returniterator(_head);}更麻烦的是空表和非空表的插入逻辑不能统一——空表时插入第一个节点要改 _ head非空表时只要改相邻节点的指针。哨兵节点就是为了消除这些特判而引入的。它是一个永远存在的虚拟节点不存有效数据。初始化voidInit_empty(){_headnewNode();// 创建哨兵_val 使用默认值 T()_head-next_head;// 自己指向自己_head-prev_head;_size0;}空表时哨兵节点指针形成一个环插入元素后:_ head → node1 → node2 → … → nodeN↑ │└─────────────────────┘哨兵的 next 指向第一个节点prev 指向最后一个节点最后一个节点的 next 指回哨兵第一个节点的 prev 也指回哨兵——始终是一个环形。3.4 迭代器 list_iterator为什么需要封装vector 的迭代器直接用 T* 就行vectorintv{1,2,3};autoitv.begin();// 底层就是个 int*it;// 地址 4跳到 v[1]vector 的元素存储在连续内存中v[0]和v[1]的地址差正好是sizeof(T)。所以 vector 的迭代器底层就是一个T*it等价于地址加sizeof(T)自然就跳到下一个元素了.但 list 的节点在堆上独立分配地址不连续// 假设三个节点的地址0x100、0x200、0x150Nodeint*phead;p;// 从 0x100 变成 0x104完全不是下一个节点对Node*做 只是在地址上加sizeof(Node)但下一个节点的地址是存储在p-next里的。正确的移动方式必须是p p-next。所以 list 的迭代器不能直接用原生指针需要封装一层通过重载operator来重新定义前进的含义。基本结构templateclassT,classRef,classPtrstructlist_iterator{typedefListNodeTNode;typedeflist_iteratorT,Ref,PtrSelf;Node*_node;// 内部封装的就是一个节点指针list_iterator(Node*node):_node(node){}// ...};迭代器内部只有一个成员_node所有操作都围绕它展开。构造函数接受一个Node*来初始化。三个模板参数的用意typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;T 是元素类型Ref和Ptr分别控制operator*和operator-的返回类型。如果不这样做就得写两个几乎一样的类// ❌ 冗余写法structlist_iterator{// 普通迭代器Toperator*(){return_node-_val;}};structconst_list_iterator{// const 迭代器constToperator*(){return_node-_val;}};用一个模板 Ref/Ptr 参数一份代码生成两个类型消除重复。operator* 和 operator-Refoperator*(){return_node-_val;// iterator 返回 Tconst_iterator 返回 const T}Ptroperator-(){return_node-_val;// iterator 返回 T*const_iterator 返回 const T*}当容器储存的是自定义类型时operator-有个巧妙之处当调用it-member时编译器会翻译成(it.operator-())-member。如果 it 是迭代器operator-()返回T*然后编译器再对T*取一次 -最终访问到_val的成员。structAA{int_a1;int_a2;};listAAlt;autoitlt.begin();it-_a110;// 等价于 (it.operator-())-_a1 → (it._node-_val)-_a1operator 和 operator–Selfoperator(){_node_node-next;// 前移跳到下一个节点return*this;}Selfoperator--(){_node_node-prev;// 后移跳到上一个节点return*this;}这是双向迭代器的核心——可以向两个方向移动。注意返回Self引用支持链式调用如it。这里的实现只重载了前置/--没有提供后置版本。后置版本可以加但日常遍历中用前置更多因为没有临时对象的开销。operator 和 operator!booloperator(constSelfx)const{return_nodex._node;// 比较两个迭代器是否指向同一个节点}booloperator!(constSelfx)const{return_node!x._node;}比较逻辑很简单——直接比较封装的节点指针是否相等。小结list_iterator的本质是一个会走路的节点指针。它在ListNode*外面包了一层重载了*、-、、--、、!让用户可以像用普通指针一样遍历链表。三个模板参数的设计则优雅地解决了iterator和const_iterator的代码重复问题。3.5 list 类3.5.1 基本骨架有了节点、哨兵、迭代器把它们组装起来就是 list 类templateclassTclasslist{typedefListNodeTNode;public:typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;// ...private:Node*_head;size_t _size;};_head指向哨兵节点_size记录有效元素个数。对外暴露两种迭代器类型iterator可读写const_iterator只读。begin / end 的实现基于哨兵极其简洁iteratorbegin(){return_head-next;}iteratorend(){return_head;}const_iteratorbegin()const{return_head-next;}const_iteratorend()const{return_head;}begin()哨兵的next就是第一个有效节点。空表时_head-next _head此时begin() end()区间为空行为正确。end()返回哨兵自身--end()就是最后一个有效节点。3.5.2 构造与析构默认构造voidInit_empty(){_headnewNode();_head-next_head;_head-prev_head;_size0;}list(){Init_empty();}哨兵自环_size 0。填充构造list(intn,constTvalueT()){Init_empty();while(n--)push_back(value);}initializer_list构造:list(initializer_listTil){Init_empty();for(autoc:il)push_back(c);}迭代器区间构造templateclassIteratorlist(Iterator first,Iterator last){Init_empty();while(first!last)push_back(*first);}模板构造函数可以从任意兼容的迭代器区间构造比如从 vector 的迭代器vectorint v {1, 2, 3, 4};listint lt(v.begin(), v.end());// 没问题拷贝构造list(constlistTl){Init_empty();for(autoc:l)push_back(c);}析构~list(){clear();delete_head;_headnullptr;}先clear()释放所有有效节点再释放哨兵节点。3.5.3 赋值与 swapvoidswap(listTl){std::swap(_head,l._head);std::swap(_size,l._size);}listToperator(listTl){swap(l);return*this;}赋值重载用了 copy-and-swap 技巧参数传值触发拷贝构造生成一个临时对象l把自己和l交换旧数据转移到了l中l出作用域自动析构旧资源被正确释放好处异常安全拷贝失败不会修改原对象且一份代码同时处理了自赋值。3.5.4 核心增删操作insert—— 通用插入iteratorinsert(iterator pos,constTx){Node*curpos._node;Node*newnodenewNode(x);newnode-nextcur;// 1. 新节点的 next 指向 curnewnode-prevcur-prev;// 2. 新节点的 prev 指向 cur 的前驱cur-prev-nextnewnode;// 3. 前驱节点的 next 指向新节点cur-prevnewnode;// 4. cur 的 prev 指向新节点_size;returnnewnode;}顺序要求1 和 2 必须在 3 和 4 之前。原因很简单——第 3 步要用到 cur-prev 来找到前驱节点如果先改第 4 步cur-prev newnodecur-prev 就变成新节点了前驱节点就找不到了。只要 1 和 2 先做完3 和 4 的顺序无所谓因为前驱地址已经在 newnode-prev 里保存好了。push_back / push_front直接复用void push_back(const T val) { insert(end(), val); }void push_front(const T val) { insert(begin(), val); }注意end()就是哨兵insert(end(), val)在哨兵前面插入等价于尾插erase —— 通用删除*iteratorerase(iterator pos){assert(pos._node!_head)Node*curpos._node;Node*nextcur-next;cur-prev-nextcur-next;cur-next-prevcur-prev;deletecur;_size--;returnnext;}前后两句指针修改顺序无所谓——cur 已经被孤立出来了。删除哨兵节点本身怎么办erase 不会用到哨兵节点因为 begin() 返回哨兵的 next用户拿到的永远是有效节点或哨兵自身。如果用户意外传了 end()哨兵会删除哨兵这是个 bug——但可以在 erase 里加 assert 做防御。pop_back / pop_front的复用void pop_back() { erase(--end()); }void pop_front() { erase(begin()); }3.5.5 其他接口voidclear(){autoitbegin();while(it!end())iterase(it);}size_tsize()const{return_size;}boolempty()const{return_size0;}Tfront(){return*begin();}constTfront()const{return*begin();}Tback(){return*(--end());}constTback()const{return*(--end());}front()和back()通过迭代器的operator*间接访问不需要单独实现取值的逻辑。clear()利用erase的返回值持续删除直到链表为空。至此一个完整的 list 就实现了。 整个设计环环相扣哨兵 →begin/end统一 →insert/erase统一 →push/pop统一↓迭代器运算符重载 → 通用遍历总结本文从一个问题出发list 到底怎么用底层又怎么实现我们走了两条线使用线——覆盖了 list 的构造、增删改查、迭代器遍历、initializer_list语法以及Operations中的splice、sort、remove等进阶操作。这些足够覆盖日常开发 90% 的场景。实现线——ListNodeT→ 存储单元prev / next / val 三要素哨兵头节点 → 简化边界让 begin/end 无歧义list_iteratorT,R,P→ 封装指针重载运算符适配遍历listT→ 生命周期管理 insert/erase 复用体系每个部分环环相扣哨兵让insert(end())能统一尾插迭代器让范围 for 能像遍历数组一样遍历链表copy-and-swap让赋值重载既简洁又异常安全。当你亲手实现过一轮 list再看 std::list 的文档和代码时看到的就不再是黑盒而是一套清晰的设计取舍。文中全部实现代码在项目 list.h 中欢迎对照阅读。也建议你在此基础上自己补充几个功能试试添加 reverse_iterator 支持实现 splice 成员函数添加 emplace_back完美转发构造实现 remove_if接受谓词动手写一遍比读十遍更有用。