尧图网站开发 
1. 从一次面试聊起list 到底难在哪大概三年前我面试一个中级 C 岗位对方让我手写一个 list 的迭代器。当时我在纸上画了半天结构体倒是写出来了迭代器的 operator 却把 prev 和 next 的方向搞反了。面试官没说什么只是笑了笑。后来我才明白list 的模拟实现不是一个“背代码”的活它考的是你对指针、节点关系、容器生命周期这三个核心概念的掌握程度。尤其是迭代器list 的迭代器和 vector 的迭代器完全是两码事vector 的迭代器可以用原生指针直接顶替list 的迭代器必须自己封装。这篇文章我打算从一个“手写 list”的角度把整个模拟实现从头到尾走一遍。内容包括节点设计、迭代器封装、构造析构、插入删除、迭代器失效问题、以及 list 和 vector 的选型对比。适合正在学 STL 源码的初学者也适合准备面试想系统梳理一遍的兄弟。文章里所有代码都是我实际编译运行过的环境是 Ubuntu 22.04 g 11.4C11 标准后面所有代码你复制到本地就能直接跑。先说清楚一个观点手写 list 不是为了重复造轮子而是为了让你在阅读 STL 源码时能看懂每一个成员变量存在的理由。当你自己把 list 从零实现一遍之后再去翻 libstdc 的源码就会有一种“原来如此”的通透感。这也是为什么很多公司面试喜欢让候选人写 list 或 vector 的模拟实现因为这东西能真实反映一个人对 C 底层细节的理解程度。2. list 的整体骨架从节点到双向循环链表2.1 节点设计为什么需要一个哨兵位头节点list 的底层结构是双向链表这一点大家应该都知道。但很多人不知道的是STL 里真正的 list 实现并不是普通的双向链表而是一个带哨兵位头节点的双向循环链表。这个设计非常巧妙哨兵位节点不存储有效数据它的 next 指向第一个有效节点prev 指向最后一个有效节点而最后一个节点的 next 又指回哨兵位第一个节点的 prev 也指回哨兵位。这样设计带来的第一个好处是插入和删除操作不需要特判空链表。如果链表为空哨兵位的 next 和 prev 都指向它自己。无论是头插、尾插、还是任意位置插入统一走同一套逻辑根本不需要对空链表写特殊分支。第二个好处是遍历时不需要额外的边界判断从哨兵位的 next 开始走走到哨兵位就说明遍历完了。节点结构体的代码很简单但有几个细节值得注意。数据域我们直接用模板参数 T指针域使用 Node *每个构造函数都要把两个指针初始化为空避免野指针。template typename T struct list_node { T data; list_nodeT* prev; list_nodeT* next; list_node(const T value T()) : data(value), prev(nullptr), next(nullptr) {} };这里有个小坑如果 T 是自定义类型默认参数 T() 会调用该类型的默认构造函数。如果 T 没有默认构造函数编译就会报错。所以在写泛型容器的时候构造节点的参数尽量从外部传进来不要依赖默认参数。2.2 类模板的基本框架成员变量和类型重定义list 作为一个容器类对外暴露的类型别名非常重要。这里的设计思路和 STL 保持一致用 typedef 或 using 定义 value_type、pointer、reference、const_iterator 等类型别名。这样做的意义在于当我们在写泛型算法或者使用迭代器萃取时可以通过类型别名拿到容器内部的具体类型这种设计被称为“成员类型萃取”。成员变量只有一个node_type* _head这个指针指向哨兵位节点。为什么只用一个指针就能管理整个链表因为这是一个循环双向链表头节点即哨兵位从它出发可以访问到任意节点。另外我们还需要一个 size但很多 STL 实现并不单独存 size而是通过 std::distance(begin(), end()) 来计算复杂度是 O(n)。为了效率我们可以在类里加一个 _size 成员每次插入删除时同步维护这样 size() 就能做到 O(1)。既然要模拟实现我建议把 _size 加上这也是实际项目里常见的选择。template typename T class list { public: using value_type T; using size_type size_t; using reference T; using const_reference const T; typedef list_nodeT node_type; typedef node_type* node_ptr; typedef list_iteratorT, T, T* iterator; typedef list_iteratorT, const T, const T* const_iterator; private: node_ptr _head; size_type _size; public: list() { _head new node_type; _head-next _head; _head-prev _head; _size 0; } ~list() { clear(); delete _head; _head nullptr; } };构造函数初始化 _size 为 0哨兵位的两个指针都指向自己。这里我提前写出了 iterator 的类型别名list_iterator 需要三个模板参数分别是节点数据类型、引用类型和指针类型。为什么要三个参数这是做 const 迭代器复用的关键后面第三章会详细讲。2.3 为什么不用数组或单链表来实现 list面试中经常被追问的一个变体题目是“既然 list 和 vector 都能存数据为什么不统一用数组”答案的核心在插入删除的效率和迭代器的稳定性上。数组的插入删除需要搬移元素平均时间复杂度 O(n)而且一旦容量不足还需要扩容扩容时所有迭代器和引用都会失效。而链表只需要修改指针中间插入删除的时间复杂度是 O(1)并且除了被删除节点之外其他迭代器引用都不会失效。那为什么不直接手写一个单链表单链表也有问题尾插效率低需要遍历找到尾部反向遍历完全做不到删除一个节点时必须知道它的前驱节点需要从头遍历。而双向循环链表完美避开了这些问题尾部插入通过哨兵位的 prev 直接拿到尾节点删除节点通过节点的 prev 指针直接拿到前驱操作成本都是 O(1)。从工程角度来说选择“带哨兵位的双向循环链表”而不是“普通双向链表”是在代码复杂度和运行性能之间取了一个很好的平衡点。普通双向链表在插入删除时依然要特判边界情况而带哨兵位后所有操作统一代码量减少 30% 以上逻辑也更不容易出错。3. 迭代器list 的灵魂所在3.1 为什么原生指针不能当 list 的迭代器vector 的迭代器本质上就是 T*因为 vector 的内存是连续线性结构指针自增自减对应的就是一个个元素的位置变化。但 list 的节点在各个堆内存里分布是零散的节点之间只能通过 prev 和 next 指针关联。如果拿原生指针当迭代器那么“迭代器自增”这个操作在 C 语法层面只会让指针移动到相邻内存地址根本到不了下一个节点。这就意味着 list 迭代器必须是一个自定义类内部封装节点指针并通过重载 operator、operator-- 来模拟“移动到下一个节点”“移动到上一个节点”的行为。这个设计思路要理解透彻它解释了为什么 list 不支持随机访问迭代器因为 operator 和 operator[] 无法高效实现只能重载 operator 和 operator-- 实现双向遍历。迭代器类最核心的成员就是一个 node_ptr _node所有操作都围绕这个指针展开。构造时把节点指针传进来operator* 返回节点中的数据引用operator- 返回数据指针。这里的引用和指针都必须支持两种形式普通版本和 const 版本。如果我们把 const 修饰符直接写死在类模板里实现就会出现大量重复代码所以在设计时我选择了“三个模板参数”的方法来复用。3.2 迭代器的运算符重载核心代码一步步拆解先看迭代器类的基本定义。Ref 是 reference 类型Ptr 是 pointer 类型。当 T 为普通类型时Ref 是 TPtr 是 T*当 T 为 const 类型时Ref 是 const TPtr 是 const T*。通过这三个模板参数我们可以让同一个类模板实例化出 iterator 和 const_iterator 两种类型而不需要写两套代码。template typename T, typename Ref, typename Ptr class list_iterator { public: typedef list_nodeT node_type; typedef node_type* node_ptr; typedef list_iteratorT, Ref, Ptr self; node_ptr _node; list_iterator(node_ptr node nullptr) : _node(node) {} Ref operator*() { return _node-data; } Ptr operator-() { return (_node-data); } self operator() { _node _node-next; return *this; } self operator(int) { self tmp *this; _node _node-next; return tmp; } self operator--() { _node _node-prev; return *this; } self operator--(int) { self tmp *this; _node _node-prev; return tmp; } bool operator(const self other) const { return _node other._node; } bool operator!(const self other) const { return _node ! other._node; } };前缀 和后缀 的区别在函数签名上后缀版本有一个 int 形参这是一个哑参数纯粹为了和前缀版本区分。前缀版本直接返回自身引用效率更高后缀版本需要先保存一份拷贝再自增因为要返回自增前的状态所以多了一次拷贝构造性能略差。日常遍历优先使用前缀 。operator- 的返回值是数据的地址这样在使用迭代器调用成员方法时就可以写成 it-member编译器会先调用 operator- 拿到数据指针再访问成员。另外注意一下 operator 比较的是内部节点地址而不是数据内容这符合迭代器语义只有指向同一个节点才相等。3.3 iterator 到 const_iterator 的类型转换const 迭代器的主要作用是通过它不能修改容器中的数据。当你用 const 方法返回容器时你只能拿到 const_iterator这个迭代器的 operator* 返回 const T写操作被编译器拦截。如果迭代器类没有用好模板参数通常的做法是再写一个 const_list_iterator代码大量重复后续维护也很痛苦。用三个模板参数之后迭代器类本身不需要做太多额外工作。但有一个细节需要处理普通 iterator 应当能隐式转换为 const_iterator而 const_iterator 不能转换为 iterator。这是符合语义的因为一个指向可变数据的迭代器可以降级为指向不可变数据的迭代器反过来则不允许。实现方式是给 list_iterator 添加一个支持从 iterator 构造的构造函数。这里需要让 iterator 和 const_iterator 是同一个类模板的不同实例化这样我们可以用模板构造函数把 iterator 转成 const_iterator编译器会做类型推导和权限收窄template typename T, typename Ref, typename Ptr class list_iterator { public: // 支持 iterator 到 const_iterator 的转换 list_iterator(const list_iteratorT, T, T* other) : _node(other._node) {} };不过这个构造函数要小心对于 iterator 版本这个构造函数相当于拷贝构造函数重载不会产生歧义。对于 const_iterator 版本它就是一个接收 iterator 的隐式转换构造函数。这种写法在工作中很常见核心思想就是让模板实例化去处理类型差异省掉重复代码。4. 核心接口实现构造、析构、插入、删除4.1 构造函数和初始化从空链表到 n 个元素list 的构造需要一个空链表初始化的过程。构造函数先 new 一个哨兵节点然后让 _head 的 next 和 prev 都指向自己_size 设置为 0。这一步别漏掉很多初学者写链表最容易犯的错就是 new 完头节点不初始化指针导致后面插入时访问到野指针。除了默认构造函数我们还需要支持这样几种构造方式用 n 个值为 value 的元素构造、用迭代器区间构造、以及拷贝构造。迭代器区间构造的关键在于它要兼容任意容器的迭代器只要 value_type 之间可以隐式转换就行。实现方式很统一先初始化空链表然后遍历区间不断使用 push_back 把元素插到尾部。template typename InputIterator list(InputIterator first, InputIterator last) { _head new node_type; _head-next _head; _head-prev _head; _size 0; for (InputIterator it first; it ! last; it) { push_back(*it); } }这里有个细节InputIterator 类型是模板参数它不需要是 list 自己的迭代器可以是 vector 的迭代器、数组指针、甚至是 istream_iterator。这就是泛型编程的好处接口更通用。但是注意如果传入的迭代器类型不支持 或者解引用编译时就会报错报错信息通常会很长定位起来比较痛苦。实际开发中可以用 static_assert 和 iterator_traits 做一些约束检查C20 之后可以用 concept 直接约束可读性好很多。4.2 push_back、pop_back、push_front、pop_front基础接口不简单先从一个问题入手push_back 需要找到尾节点在带哨兵位的循环链表中尾节点就是 _head-prev。我们 new 一个新节点把新节点的 prev 指向尾节点next 指向 _head然后让尾节点的 next 指向新节点最后让 _head-prev 指向新节点。这个过程涉及四条指针的修改顺序错了就可能丢节点或者形成错误环。我的习惯是写一个通用的 insert 函数然后让 push_back 和 push_front 都调它。这样逻辑统一代码复用率高。insert(pos, value) 的核心逻辑是在 pos 指向的节点之前插入一个值为 value 的新节点。实现时我们先 new 出节点然后依次修改新节点和前后节点的指针。注意要先把新节点的两个指针设置好再修改 prev_node 的 next 和 pos 的 prev顺序不能反否则可能丢失节点。iterator insert(iterator pos, const T value) { node_ptr cur pos._node; node_ptr prev_node cur-prev; node_ptr new_node new node_type(value); new_node-prev prev_node; new_node-next cur; prev_node-next new_node; cur-prev new_node; _size; return iterator(new_node); }push_back 和 push_front 不需要重新实现直接调用 insert 就行push_back 就是 insert(end(), value)push_front 就是 insert(begin(), value)。这里的 end() 返回的是指向哨兵位节点的迭代器哨兵位是最后一个有效节点的 next在它之前插入就相当于尾插完美符合语义。删除操作则统一封装成 erasepop_back 就是 erase(iterator 指向倒数第一个元素)pop_front 就是 erase(begin())。erase 在实现时要注意先保存待删除节点的前后节点然后修改前驱的 next 指向后继后继的 prev 指向前驱最后 delete 当前节点_size 减一。返回值要指向被删除节点的下一个节点这样循环删除容器元素时才能不断更新迭代器。iterator erase(iterator pos) { node_ptr cur pos._node; node_ptr prev_node cur-prev; node_ptr next_node cur-next; prev_node-next next_node; next_node-prev prev_node; delete cur; --_size; return iterator(next_node); }4.3 clear 和析构别让内存泄漏找上门list 析构之前必须把有效节点全部释放否则就会内存泄漏。clear 函数负责释放所有有效节点但保留哨兵位。实现思路是从 _head-next 开始依次保存下一个节点的指针delete 当前节点直到回到 _head。这里有个很容易犯的错只保存了当前节点的下一个节点但当前节点被 delete 之后再去访问它内部的 next 指针就是未定义行为。所以要先取 next 再 delete顺序不能反。void clear() { node_ptr cur _head-next; while (cur ! _head) { node_ptr next_node cur-next; delete cur; cur next_node; } _head-next _head; _head-prev _head; _size 0; }析构函数直接调用 clear然后再 delete 哨兵节点最后把 _head 设为 nullptr。还有人会问析构函数里为什么需要把 _head 置空其实析构之后对象生命周期就结束了置不置空理论上来讲区别不大但为了防御性编程避免在调试阶段访问悬空指针尽量还是置空一下这是个好习惯。4.4 拷贝构造与赋值运算符不能走默认的浅拷贝list 类内部有指针成员如果使用默认的拷贝构造函数那只是浅拷贝新旧两个对象的 _head 会指向同一个节点_size 也会同步变化但实际上是同一份内存。这会导致两个对象共享同一个链表任何一个对象析构时都会释放掉所有节点另一个对象再使用时就会访问悬空指针程序崩溃几乎是必然的。正确做法是深拷贝。拷贝构造函数先创建空链表然后遍历源链表的所有有效节点逐个 push_back。赋值运算符有一个推荐写法叫 copy-and-swap先以实参构造一个临时 list然后把临时 list 和当前对象的 _head 以及 _size 交换临时对象析构时会自动释放原本持有的节点。这个写法代码简洁、异常安全是 C 里很经典的惯用法。list(const list other) { _head new node_type; _head-next _head; _head-prev _head; _size 0; for (const auto value : other) { push_back(value); } } list operator(list other) { std::swap(_head, other._head); std::swap(_size, other._size); return *this; }这里再把“三/五法则”补充一下因为我们自定义了析构函数、拷贝构造函数和赋值运算符所以还要考虑移动构造和移动赋值。如果不需要显式支持移动语义编译器通常不会自动生成这时候对象拷贝会有额外开销。我一般建议把移动构造和移动赋值也写上实现很轻量就是把自己的 _head 参数初始化后把对方的 _head 置空这样能显著提升大链表拷贝场景下的性能。5. 模拟实现中容易踩的坑迭代器失效与细节问题5.1 迭代器失效问题insert 后还能用吗list 的迭代器失效规则和 vector 有本质不同。vector 在插入导致扩容时所有迭代器全部失效即使没有扩容插入位置之后的迭代器也全部失效。而 list 的插入操作不会使任何现有迭代器失效因为插入不会移动已有节点节点的内存地址不会变化。删除操作会使被删除元素的迭代器失效但其他迭代器不受影响。这一点和 vector 不同vector 删除某个元素后删除位置之后的迭代器全部失效因为要搬移元素。list 只需要注意如果你想实现“删除满足条件的元素”这种操作用 erase 返回的迭代器继续遍历即可erase 返回的是被删除节点的后继节点完美支持这种场景。auto it lst.begin(); while (it ! lst.end()) { if (*it % 2 0) { it lst.erase(it); } else { it; } }如果你用 it 而不是 it erase(it)那在 erase 之后 it 就成了悬空迭代器继续 it 就是行为未定义的野操作。这是面试里最喜欢考的场景也是实际项目中最容易踩的坑。5.2 拷贝构造时 T 的拷贝语义千万别把引用绑错了list 是模板容器T 可能是 int、string、自定义类、甚至是指针。在设计 push_back 和 insert 时我们传入的是 const T这样避免了拷贝开销而且在插入时调用的是 T 的拷贝构造函数。当 T 是像 std::string 这样的深拷贝类型时这没问题。但如果 T 是原始指针那容器只是复制了指针值并不复制指针指向的对象。你需要在业务层自己管理好内存生命周期这是容器的语义边界不是 bug。在节点构造函数中我写了 list_node(const T value T()) : data(value)。如果 T 是自定义类且没有合适的拷贝构造函数编译直接报错。在实际使用 list 时要确保 T 满足可拷贝构造、可析构的基本要求。C11 之后可以给 list_node 添加移动语义使用 std::move 来避免不必要的深拷贝尤其是存储字符串或大对象时性能差异非常明显。如果想让 list 支持移动语义节点的构造最好写成两个版本list_node(const T value) : data(value), prev(nullptr), next(nullptr) {} list_node(T value) : data(std::move(value)), prev(nullptr), next(nullptr) {}然后把 push_back 和 insert 也提供右值引用重载版本或者直接使用万能引用配合完美转发。这部分属于进阶优化如果只是为了理解原理可以先不做。5.3 size 的维护和哨兵节点的特殊性每次插入和删除_size 要同步加一或减一。如果把 _size 漏了size() 接口就会返回错误结果但程序不会立刻崩溃这种“慢性的逻辑错误”最坑人。我习惯在 clear 和构造时就统一置零然后在 insert 和 erase 里各写一次 _size 或 --_size代码注释强调“必须与 _size 同步更新”。另一个需要注意的点是 end() 返回的迭代器不能执行 operator*因为 _node 指向的是哨兵节点它的 data 是默认构造的无效数据。很多同学在写遍历时习惯 for (auto it begin(); it ! end(); it) 就不会出问题但如果写 while (true) 比对了 it 和 end() 再在循环体里解引用就要小心别把哨兵的无效数据拿出来了。在实际工程的容器实现中通常还会加断言来检查这个前置条件。5.4 内存对齐与分配器问题顺手聊聊 allocator正规 STL 的 list 并不是直接使用 new/delete 来分配节点的而是使用分配器allocator来统一管理内存。new/delete 每次都会调用 operator new 和 operator delete在频繁插入删除时会产生大量小内存块申请释放效率比较低。STL 默认的 std::allocator 会结合内存池技术减少系统调用频率。我们的模拟实现作为教学版本直接使用 new/delete 是合理的方便理解核心逻辑。但如果你要把它用到生产环境或者做性能优化建议理解一下 allocator 的作用它把“内存分配”和“对象构造”解耦开来。C17 提供了 std::allocator_traits 作为统一接口现代 C 也鼓励使用 std::allocator 的 rebind 来适配不同节点类型。学到这里vector 的 reserve 为什么比多次 push_back 快list 的节点分配为什么适合内存池就不难理解了。6. 性能分析list 和 vector 到底怎么选6.1 中间插入删除是 list 的主场list 最大的优势就是任意位置的插入和删除都是 O(1) 时间只要你已经拿到了对应位置的迭代器。比如我们需要维护一个有序结构频繁在中间插入、删除节点list 就比 vector 有优势。vector 的中间插入需要把插入点之后的所有元素都往后搬一位删除同理整体搬移成本是 O(n)当元素是大对象时搬移还会伴随多次拷贝构造或移动构造开销不小。刚才说的“只要你已经拿到了迭代器”非常关键。如果每次插入前都需要遍历找到位置那遍历是 O(n)总复杂度还是 O(n)。list 没有随机访问能力查找某一个元素必须从头遍历这正是它最大的弱点。所以“list 插入是 O(1)”这句话完整版本是“给定迭代器时插入是 O(1)但没有随机访问找到插入点本身就是 O(n)”。在缓存友好性方面list 也远不如 vector。vector 的数据在内存中是连续存放的CPU 缓存命中率极高。list 的节点分散在不同堆地址每一次遍历都是一次随机内存访问缓存命中率低在数据量大的时候性能差距非常夸张。实测下来对于一千万个 intvector 的遍历速度可能比 list 快 20 到 50 倍这个数字在不同编译器上略有差异但趋势是一致的。6.2 什么场景不要用 list如果你主要是“尾部追加数据偶尔遍历”那 list 完全不是最优解vector 或者 deque 会更好。vector 的尾部插入是均摊 O(1)而且扩容策略可以提前预留空间。list 尾部插入虽然也是 O(1)但每次插入都要 new 一个节点开销比 vector 的尾部追加高不少。频繁查找的场景也不要用 list。list 的 std::find 是 O(n)而如果你用 vector 并存放在有序数组里可以用二分查找复杂度 O(log n)差距巨大。最简单的判断标准是如果你发现自己经常要使用 std::advance(it, n)、std::distance、operator[]说明你更需要一个随机访问容器。deque 是另一个容易被忽略的容器。很多情况下双端队列 deque 比 list 更合适它支持双端插入删除同时支持随机访问底层用分段连续内存实现。如果你只需要在头和尾操作deque 的性能通常优于 list。list 真正不可替代的场景是“需要在容器中间频繁插入删除并且操作都基于已持有的迭代器”。6.3 实际项目中的 list 使用建议根据我个人经验实际项目里 list 的使用频率远低于 vector 和 deque。很多开发者一看到“需要频繁插入删除”就直接上 list这是惯性思维但不一定是工程最优解。正确的思路是先分析数据的访问模式和操作位置再用 benchmark 验证。如果元素数量很少比如不到几百个vector 和 list 的性能差别根本不重要选择代码可读性更好的那个就行。如果你的数据对象非常大比如一个自定义结构体有几百字节list 在插入时比 vector 有优势因为 vector 扩容时会搬移所有已有对象而 list 只需要 new 一个节点。但现代 C 的移动语义已经大幅缓解了 vector 的搬移成本如果你的对象可以低成本移动vector 的优势会更明显。所以在 2025 年的工程实践中list 的使用场景进一步缩小主要还是在 LRU Cache、消息队列、链表哈希等特定数据结构中发光发热。模拟实现 list 的价值并不在于让你“以后都用 list”而在于你彻底理解一个双向链表容器需要处理哪些问题。这些问题包括内存布局、迭代器语义、异常安全、生命周期管理。理解之后不管遇到什么容器你的学习曲线都会平缓很多。7. 测试与调试经验模拟实现写完后怎么验证7.1 写一个尽可能全面的单元测试写完模拟实现之后第一件事不是直接上复杂业务而是从最基本的接口开始验证。我建议按这个顺序测试先测试默认构造和空链表遍历再测试 push_back 和 push_front 后的正向和反向遍历再测试 insert 和 erase接着测试拷贝构造和赋值运算符最后测试 const 迭代器和迭代器失效场景。一个比较有用的技巧是在测试代码里用 int 类型跑通所有基本接口之后再用自定义类包含指针成员或 unique_ptr 成员重新编译一遍这样可以发现拷贝构造中的浅拷贝问题。比如你可以定义一个类构造函数和析构函数里打印日志运行测试时观察对象的创建和销毁次数确认是否存在内存泄漏或重复释放。我平时还会配合 assert 来验证内部不变量遍历完后 _size 必须和实际节点数一致空链表的 begin() 等于 end()删除全部元素后 _head-next 和 _head-prev 都指向 _head。这些不变量可以在 insert、erase、clear 之后各检查一次用来快速定位 bug 出现在哪一步。7.2 gdb 调试链表结构的小技巧链表 bug 比较难调试因为节点之间的指针跳转不直观。我一般会在 gdb 里定义一个辅助打印函数直接打印节点地址、当前节点的 data、prev 的地址和 next 的地址。这样能快速看出链表是否成环、指针是否连接正确。比如在插入操作之后如果发现某个节点的 next 指向了一个还没分配的内存区域那基本就是指针赋值顺序出了问题。另一个工具是 AddressSanitizer编译时加 -fsanitizeaddress -g运行时会自动检测内存泄漏、越界访问和悬空指针。我自己写模拟实现时每完成一个阶段就会开启 ASan 跑一遍测试能抓到大量传统调试很难发现的细节问题。比如 delete 之后没有把指针置空后续访问了悬空节点这种问题 ASan 会立刻报出来。调试时的核心思路是“从内向外”先确认单节点构造正确再确认两个节点的连接正确最后才扩大规模测试。不要一上来就插入一万个节点出问题很难定位。每次只改变一个操作配合打印或者单步跟踪很快就能找到问题所在。7.3 一个经典 bug 的排查实录有一次我在实现 erase 时返回值写成 pos 本身而不是 pos 的下一个节点。在顺序遍历删除偶数的测试里程序没有崩但跳着删除了元素结果就是奇数也被删掉了。原因很简单删除当前节点后pos 的 next 指针已经被 delete 释放再拿原来的 pos 去 it行为的未确定性导致 next 指针指向了不可预知的内存。后来我改成先保存 next_node再 delete 当前节点最后返回 next_node 的迭代器问题就消失了。这个 bug 在面试时很常见面试官会问“erase 之后为什么要返回迭代器”。如果返回值指向下一个有效节点就能支持循环删除如果返回 void你只能自己在删除前保存下一个迭代器。STL 标准选择返回下一个迭代器就是为了让遍历删除的代码写起来既安全又简洁。8. 进阶扩展从 list 到 forward_list 和自定义容器8.1 forward_list单链表的特殊存在C11 引入了 forward_list它的底层是单链表只支持前向遍历。为了保证操作效率forward_list 的 insert 和 erase 接口和 list 不太一样它提供 insert_after 和 erase_after因为单链表只保存后继指针在给定位置之前插入需要遍历找前驱。forward_list 的优点是每个节点少一个指针内存占用更小在存储大量小对象时内存开销优势明显。如果你已经完整理解了 list 的实现forward_list 就是一次“减法题”节点去掉 prev 指针迭代器去掉 operator--插入删除改成为 after 语义。这个数据结构在内存受限的嵌入式场景中用得比较多工程里普通业务代码用 forward_list 的非常少。但理解它的设计能帮你加深对“容器接口设计和底层数据结构强相关”这个观点的印象。8.2 自己实现一个 list 的 reverse 接口list 的反转不需要像 vector 那样交换数据只需要把每个节点的 prev 和 next 指针互换。实现方式有两种一种是遍历所有节点依次交换每个节点的 prev 和 next另一种是将头尾交换并重新连接。对于带哨兵位的双向链表前一种更直观从第一个有效节点走到哨兵位对每一个节点执行 std::swap(node-prev, node-next)最后不要忘了把哨兵位的 prev 和 next 也交换。reverse 的时间复杂度是 O(n)空间复杂度 O(1)。这也是链表类容器常被称赞的点就地反转只需要修改指针不需要额外空间。如果你对链表结构足够熟悉reverse 的代码十行之内就能写完但很多新手还是会写错关键就是哨兵位的两个指针也要交换漏掉这一句就会出现诡异的行为。8.3 从模拟实现到阅读真实 STL 源码做到这里你已经把 list 的核心逻辑完整实现了一遍。如果想去读真实的 STL 源码我给你指条路先看 libstdc 里的 stl_list.h。你会发现它实现了 _List_node、_List_iterator、_List_const_iterator 三个结构整体设计和我们讲的高度一致但多了 allocator、异常安全、节点回收池等工程化细节。第一遍读的时候不要钻进 allocator 的细节里先沿着构造、析构、插入、删除这条主线走。读源码时重点关注两个东西一是 _List_node_base 这个基类它把 prev 和 next 指针抽出来避免模板实例化时重复存储二是 _List_iterator 和 _List_const_iterator 都继承自 _List_node_base迭代器的 和 -- 操作通过基类指针完成。这种设计减少模板展开的代码膨胀是源码工程化的一个重要细节。看完之后再回到你自己的代码会发现有些设计思路完全可以借鉴比如把节点基类独立出来、使用节点分配器等等。到这一步你这套模拟实现就算是真正学透了。 
1. 从一次面试聊起list 到底难在哪大概三年前我面试一个中级 C 岗位对方让我手写一个 list 的迭代器。当时我在纸上画了半天结构体倒是写出来了迭代器的 operator 却把 prev 和 next 的方向搞反了。面试官没说什么只是笑了笑。后来我才明白list 的模拟实现不是一个“背代码”的活它考的是你对指针、节点关系、容器生命周期这三个核心概念的掌握程度。尤其是迭代器list 的迭代器和 vector 的迭代器完全是两码事vector 的迭代器可以用原生指针直接顶替list 的迭代器必须自己封装。这篇文章我打算从一个“手写 list”的角度把整个模拟实现从头到尾走一遍。内容包括节点设计、迭代器封装、构造析构、插入删除、迭代器失效问题、以及 list 和 vector 的选型对比。适合正在学 STL 源码的初学者也适合准备面试想系统梳理一遍的兄弟。文章里所有代码都是我实际编译运行过的环境是 Ubuntu 22.04 g 11.4C11 标准后面所有代码你复制到本地就能直接跑。先说清楚一个观点手写 list 不是为了重复造轮子而是为了让你在阅读 STL 源码时能看懂每一个成员变量存在的理由。当你自己把 list 从零实现一遍之后再去翻 libstdc 的源码就会有一种“原来如此”的通透感。这也是为什么很多公司面试喜欢让候选人写 list 或 vector 的模拟实现因为这东西能真实反映一个人对 C 底层细节的理解程度。2. list 的整体骨架从节点到双向循环链表2.1 节点设计为什么需要一个哨兵位头节点list 的底层结构是双向链表这一点大家应该都知道。但很多人不知道的是STL 里真正的 list 实现并不是普通的双向链表而是一个带哨兵位头节点的双向循环链表。这个设计非常巧妙哨兵位节点不存储有效数据它的 next 指向第一个有效节点prev 指向最后一个有效节点而最后一个节点的 next 又指回哨兵位第一个节点的 prev 也指回哨兵位。这样设计带来的第一个好处是插入和删除操作不需要特判空链表。如果链表为空哨兵位的 next 和 prev 都指向它自己。无论是头插、尾插、还是任意位置插入统一走同一套逻辑根本不需要对空链表写特殊分支。第二个好处是遍历时不需要额外的边界判断从哨兵位的 next 开始走走到哨兵位就说明遍历完了。节点结构体的代码很简单但有几个细节值得注意。数据域我们直接用模板参数 T指针域使用 Node *每个构造函数都要把两个指针初始化为空避免野指针。template typename T struct list_node { T data; list_nodeT* prev; list_nodeT* next; list_node(const T value T()) : data(value), prev(nullptr), next(nullptr) {} };这里有个小坑如果 T 是自定义类型默认参数 T() 会调用该类型的默认构造函数。如果 T 没有默认构造函数编译就会报错。所以在写泛型容器的时候构造节点的参数尽量从外部传进来不要依赖默认参数。2.2 类模板的基本框架成员变量和类型重定义list 作为一个容器类对外暴露的类型别名非常重要。这里的设计思路和 STL 保持一致用 typedef 或 using 定义 value_type、pointer、reference、const_iterator 等类型别名。这样做的意义在于当我们在写泛型算法或者使用迭代器萃取时可以通过类型别名拿到容器内部的具体类型这种设计被称为“成员类型萃取”。成员变量只有一个node_type* _head这个指针指向哨兵位节点。为什么只用一个指针就能管理整个链表因为这是一个循环双向链表头节点即哨兵位从它出发可以访问到任意节点。另外我们还需要一个 size但很多 STL 实现并不单独存 size而是通过 std::distance(begin(), end()) 来计算复杂度是 O(n)。为了效率我们可以在类里加一个 _size 成员每次插入删除时同步维护这样 size() 就能做到 O(1)。既然要模拟实现我建议把 _size 加上这也是实际项目里常见的选择。template typename T class list { public: using value_type T; using size_type size_t; using reference T; using const_reference const T; typedef list_nodeT node_type; typedef node_type* node_ptr; typedef list_iteratorT, T, T* iterator; typedef list_iteratorT, const T, const T* const_iterator; private: node_ptr _head; size_type _size; public: list() { _head new node_type; _head-next _head; _head-prev _head; _size 0; } ~list() { clear(); delete _head; _head nullptr; } };构造函数初始化 _size 为 0哨兵位的两个指针都指向自己。这里我提前写出了 iterator 的类型别名list_iterator 需要三个模板参数分别是节点数据类型、引用类型和指针类型。为什么要三个参数这是做 const 迭代器复用的关键后面第三章会详细讲。2.3 为什么不用数组或单链表来实现 list面试中经常被追问的一个变体题目是“既然 list 和 vector 都能存数据为什么不统一用数组”答案的核心在插入删除的效率和迭代器的稳定性上。数组的插入删除需要搬移元素平均时间复杂度 O(n)而且一旦容量不足还需要扩容扩容时所有迭代器和引用都会失效。而链表只需要修改指针中间插入删除的时间复杂度是 O(1)并且除了被删除节点之外其他迭代器引用都不会失效。那为什么不直接手写一个单链表单链表也有问题尾插效率低需要遍历找到尾部反向遍历完全做不到删除一个节点时必须知道它的前驱节点需要从头遍历。而双向循环链表完美避开了这些问题尾部插入通过哨兵位的 prev 直接拿到尾节点删除节点通过节点的 prev 指针直接拿到前驱操作成本都是 O(1)。从工程角度来说选择“带哨兵位的双向循环链表”而不是“普通双向链表”是在代码复杂度和运行性能之间取了一个很好的平衡点。普通双向链表在插入删除时依然要特判边界情况而带哨兵位后所有操作统一代码量减少 30% 以上逻辑也更不容易出错。3. 迭代器list 的灵魂所在3.1 为什么原生指针不能当 list 的迭代器vector 的迭代器本质上就是 T*因为 vector 的内存是连续线性结构指针自增自减对应的就是一个个元素的位置变化。但 list 的节点在各个堆内存里分布是零散的节点之间只能通过 prev 和 next 指针关联。如果拿原生指针当迭代器那么“迭代器自增”这个操作在 C 语法层面只会让指针移动到相邻内存地址根本到不了下一个节点。这就意味着 list 迭代器必须是一个自定义类内部封装节点指针并通过重载 operator、operator-- 来模拟“移动到下一个节点”“移动到上一个节点”的行为。这个设计思路要理解透彻它解释了为什么 list 不支持随机访问迭代器因为 operator 和 operator[] 无法高效实现只能重载 operator 和 operator-- 实现双向遍历。迭代器类最核心的成员就是一个 node_ptr _node所有操作都围绕这个指针展开。构造时把节点指针传进来operator* 返回节点中的数据引用operator- 返回数据指针。这里的引用和指针都必须支持两种形式普通版本和 const 版本。如果我们把 const 修饰符直接写死在类模板里实现就会出现大量重复代码所以在设计时我选择了“三个模板参数”的方法来复用。3.2 迭代器的运算符重载核心代码一步步拆解先看迭代器类的基本定义。Ref 是 reference 类型Ptr 是 pointer 类型。当 T 为普通类型时Ref 是 TPtr 是 T*当 T 为 const 类型时Ref 是 const TPtr 是 const T*。通过这三个模板参数我们可以让同一个类模板实例化出 iterator 和 const_iterator 两种类型而不需要写两套代码。template typename T, typename Ref, typename Ptr class list_iterator { public: typedef list_nodeT node_type; typedef node_type* node_ptr; typedef list_iteratorT, Ref, Ptr self; node_ptr _node; list_iterator(node_ptr node nullptr) : _node(node) {} Ref operator*() { return _node-data; } Ptr operator-() { return (_node-data); } self operator() { _node _node-next; return *this; } self operator(int) { self tmp *this; _node _node-next; return tmp; } self operator--() { _node _node-prev; return *this; } self operator--(int) { self tmp *this; _node _node-prev; return tmp; } bool operator(const self other) const { return _node other._node; } bool operator!(const self other) const { return _node ! other._node; } };前缀 和后缀 的区别在函数签名上后缀版本有一个 int 形参这是一个哑参数纯粹为了和前缀版本区分。前缀版本直接返回自身引用效率更高后缀版本需要先保存一份拷贝再自增因为要返回自增前的状态所以多了一次拷贝构造性能略差。日常遍历优先使用前缀 。operator- 的返回值是数据的地址这样在使用迭代器调用成员方法时就可以写成 it-member编译器会先调用 operator- 拿到数据指针再访问成员。另外注意一下 operator 比较的是内部节点地址而不是数据内容这符合迭代器语义只有指向同一个节点才相等。3.3 iterator 到 const_iterator 的类型转换const 迭代器的主要作用是通过它不能修改容器中的数据。当你用 const 方法返回容器时你只能拿到 const_iterator这个迭代器的 operator* 返回 const T写操作被编译器拦截。如果迭代器类没有用好模板参数通常的做法是再写一个 const_list_iterator代码大量重复后续维护也很痛苦。用三个模板参数之后迭代器类本身不需要做太多额外工作。但有一个细节需要处理普通 iterator 应当能隐式转换为 const_iterator而 const_iterator 不能转换为 iterator。这是符合语义的因为一个指向可变数据的迭代器可以降级为指向不可变数据的迭代器反过来则不允许。实现方式是给 list_iterator 添加一个支持从 iterator 构造的构造函数。这里需要让 iterator 和 const_iterator 是同一个类模板的不同实例化这样我们可以用模板构造函数把 iterator 转成 const_iterator编译器会做类型推导和权限收窄template typename T, typename Ref, typename Ptr class list_iterator { public: // 支持 iterator 到 const_iterator 的转换 list_iterator(const list_iteratorT, T, T* other) : _node(other._node) {} };不过这个构造函数要小心对于 iterator 版本这个构造函数相当于拷贝构造函数重载不会产生歧义。对于 const_iterator 版本它就是一个接收 iterator 的隐式转换构造函数。这种写法在工作中很常见核心思想就是让模板实例化去处理类型差异省掉重复代码。4. 核心接口实现构造、析构、插入、删除4.1 构造函数和初始化从空链表到 n 个元素list 的构造需要一个空链表初始化的过程。构造函数先 new 一个哨兵节点然后让 _head 的 next 和 prev 都指向自己_size 设置为 0。这一步别漏掉很多初学者写链表最容易犯的错就是 new 完头节点不初始化指针导致后面插入时访问到野指针。除了默认构造函数我们还需要支持这样几种构造方式用 n 个值为 value 的元素构造、用迭代器区间构造、以及拷贝构造。迭代器区间构造的关键在于它要兼容任意容器的迭代器只要 value_type 之间可以隐式转换就行。实现方式很统一先初始化空链表然后遍历区间不断使用 push_back 把元素插到尾部。template typename InputIterator list(InputIterator first, InputIterator last) { _head new node_type; _head-next _head; _head-prev _head; _size 0; for (InputIterator it first; it ! last; it) { push_back(*it); } }这里有个细节InputIterator 类型是模板参数它不需要是 list 自己的迭代器可以是 vector 的迭代器、数组指针、甚至是 istream_iterator。这就是泛型编程的好处接口更通用。但是注意如果传入的迭代器类型不支持 或者解引用编译时就会报错报错信息通常会很长定位起来比较痛苦。实际开发中可以用 static_assert 和 iterator_traits 做一些约束检查C20 之后可以用 concept 直接约束可读性好很多。4.2 push_back、pop_back、push_front、pop_front基础接口不简单先从一个问题入手push_back 需要找到尾节点在带哨兵位的循环链表中尾节点就是 _head-prev。我们 new 一个新节点把新节点的 prev 指向尾节点next 指向 _head然后让尾节点的 next 指向新节点最后让 _head-prev 指向新节点。这个过程涉及四条指针的修改顺序错了就可能丢节点或者形成错误环。我的习惯是写一个通用的 insert 函数然后让 push_back 和 push_front 都调它。这样逻辑统一代码复用率高。insert(pos, value) 的核心逻辑是在 pos 指向的节点之前插入一个值为 value 的新节点。实现时我们先 new 出节点然后依次修改新节点和前后节点的指针。注意要先把新节点的两个指针设置好再修改 prev_node 的 next 和 pos 的 prev顺序不能反否则可能丢失节点。iterator insert(iterator pos, const T value) { node_ptr cur pos._node; node_ptr prev_node cur-prev; node_ptr new_node new node_type(value); new_node-prev prev_node; new_node-next cur; prev_node-next new_node; cur-prev new_node; _size; return iterator(new_node); }push_back 和 push_front 不需要重新实现直接调用 insert 就行push_back 就是 insert(end(), value)push_front 就是 insert(begin(), value)。这里的 end() 返回的是指向哨兵位节点的迭代器哨兵位是最后一个有效节点的 next在它之前插入就相当于尾插完美符合语义。删除操作则统一封装成 erasepop_back 就是 erase(iterator 指向倒数第一个元素)pop_front 就是 erase(begin())。erase 在实现时要注意先保存待删除节点的前后节点然后修改前驱的 next 指向后继后继的 prev 指向前驱最后 delete 当前节点_size 减一。返回值要指向被删除节点的下一个节点这样循环删除容器元素时才能不断更新迭代器。iterator erase(iterator pos) { node_ptr cur pos._node; node_ptr prev_node cur-prev; node_ptr next_node cur-next; prev_node-next next_node; next_node-prev prev_node; delete cur; --_size; return iterator(next_node); }4.3 clear 和析构别让内存泄漏找上门list 析构之前必须把有效节点全部释放否则就会内存泄漏。clear 函数负责释放所有有效节点但保留哨兵位。实现思路是从 _head-next 开始依次保存下一个节点的指针delete 当前节点直到回到 _head。这里有个很容易犯的错只保存了当前节点的下一个节点但当前节点被 delete 之后再去访问它内部的 next 指针就是未定义行为。所以要先取 next 再 delete顺序不能反。void clear() { node_ptr cur _head-next; while (cur ! _head) { node_ptr next_node cur-next; delete cur; cur next_node; } _head-next _head; _head-prev _head; _size 0; }析构函数直接调用 clear然后再 delete 哨兵节点最后把 _head 设为 nullptr。还有人会问析构函数里为什么需要把 _head 置空其实析构之后对象生命周期就结束了置不置空理论上来讲区别不大但为了防御性编程避免在调试阶段访问悬空指针尽量还是置空一下这是个好习惯。4.4 拷贝构造与赋值运算符不能走默认的浅拷贝list 类内部有指针成员如果使用默认的拷贝构造函数那只是浅拷贝新旧两个对象的 _head 会指向同一个节点_size 也会同步变化但实际上是同一份内存。这会导致两个对象共享同一个链表任何一个对象析构时都会释放掉所有节点另一个对象再使用时就会访问悬空指针程序崩溃几乎是必然的。正确做法是深拷贝。拷贝构造函数先创建空链表然后遍历源链表的所有有效节点逐个 push_back。赋值运算符有一个推荐写法叫 copy-and-swap先以实参构造一个临时 list然后把临时 list 和当前对象的 _head 以及 _size 交换临时对象析构时会自动释放原本持有的节点。这个写法代码简洁、异常安全是 C 里很经典的惯用法。list(const list other) { _head new node_type; _head-next _head; _head-prev _head; _size 0; for (const auto value : other) { push_back(value); } } list operator(list other) { std::swap(_head, other._head); std::swap(_size, other._size); return *this; }这里再把“三/五法则”补充一下因为我们自定义了析构函数、拷贝构造函数和赋值运算符所以还要考虑移动构造和移动赋值。如果不需要显式支持移动语义编译器通常不会自动生成这时候对象拷贝会有额外开销。我一般建议把移动构造和移动赋值也写上实现很轻量就是把自己的 _head 参数初始化后把对方的 _head 置空这样能显著提升大链表拷贝场景下的性能。5. 模拟实现中容易踩的坑迭代器失效与细节问题5.1 迭代器失效问题insert 后还能用吗list 的迭代器失效规则和 vector 有本质不同。vector 在插入导致扩容时所有迭代器全部失效即使没有扩容插入位置之后的迭代器也全部失效。而 list 的插入操作不会使任何现有迭代器失效因为插入不会移动已有节点节点的内存地址不会变化。删除操作会使被删除元素的迭代器失效但其他迭代器不受影响。这一点和 vector 不同vector 删除某个元素后删除位置之后的迭代器全部失效因为要搬移元素。list 只需要注意如果你想实现“删除满足条件的元素”这种操作用 erase 返回的迭代器继续遍历即可erase 返回的是被删除节点的后继节点完美支持这种场景。auto it lst.begin(); while (it ! lst.end()) { if (*it % 2 0) { it lst.erase(it); } else { it; } }如果你用 it 而不是 it erase(it)那在 erase 之后 it 就成了悬空迭代器继续 it 就是行为未定义的野操作。这是面试里最喜欢考的场景也是实际项目中最容易踩的坑。5.2 拷贝构造时 T 的拷贝语义千万别把引用绑错了list 是模板容器T 可能是 int、string、自定义类、甚至是指针。在设计 push_back 和 insert 时我们传入的是 const T这样避免了拷贝开销而且在插入时调用的是 T 的拷贝构造函数。当 T 是像 std::string 这样的深拷贝类型时这没问题。但如果 T 是原始指针那容器只是复制了指针值并不复制指针指向的对象。你需要在业务层自己管理好内存生命周期这是容器的语义边界不是 bug。在节点构造函数中我写了 list_node(const T value T()) : data(value)。如果 T 是自定义类且没有合适的拷贝构造函数编译直接报错。在实际使用 list 时要确保 T 满足可拷贝构造、可析构的基本要求。C11 之后可以给 list_node 添加移动语义使用 std::move 来避免不必要的深拷贝尤其是存储字符串或大对象时性能差异非常明显。如果想让 list 支持移动语义节点的构造最好写成两个版本list_node(const T value) : data(value), prev(nullptr), next(nullptr) {} list_node(T value) : data(std::move(value)), prev(nullptr), next(nullptr) {}然后把 push_back 和 insert 也提供右值引用重载版本或者直接使用万能引用配合完美转发。这部分属于进阶优化如果只是为了理解原理可以先不做。5.3 size 的维护和哨兵节点的特殊性每次插入和删除_size 要同步加一或减一。如果把 _size 漏了size() 接口就会返回错误结果但程序不会立刻崩溃这种“慢性的逻辑错误”最坑人。我习惯在 clear 和构造时就统一置零然后在 insert 和 erase 里各写一次 _size 或 --_size代码注释强调“必须与 _size 同步更新”。另一个需要注意的点是 end() 返回的迭代器不能执行 operator*因为 _node 指向的是哨兵节点它的 data 是默认构造的无效数据。很多同学在写遍历时习惯 for (auto it begin(); it ! end(); it) 就不会出问题但如果写 while (true) 比对了 it 和 end() 再在循环体里解引用就要小心别把哨兵的无效数据拿出来了。在实际工程的容器实现中通常还会加断言来检查这个前置条件。5.4 内存对齐与分配器问题顺手聊聊 allocator正规 STL 的 list 并不是直接使用 new/delete 来分配节点的而是使用分配器allocator来统一管理内存。new/delete 每次都会调用 operator new 和 operator delete在频繁插入删除时会产生大量小内存块申请释放效率比较低。STL 默认的 std::allocator 会结合内存池技术减少系统调用频率。我们的模拟实现作为教学版本直接使用 new/delete 是合理的方便理解核心逻辑。但如果你要把它用到生产环境或者做性能优化建议理解一下 allocator 的作用它把“内存分配”和“对象构造”解耦开来。C17 提供了 std::allocator_traits 作为统一接口现代 C 也鼓励使用 std::allocator 的 rebind 来适配不同节点类型。学到这里vector 的 reserve 为什么比多次 push_back 快list 的节点分配为什么适合内存池就不难理解了。6. 性能分析list 和 vector 到底怎么选6.1 中间插入删除是 list 的主场list 最大的优势就是任意位置的插入和删除都是 O(1) 时间只要你已经拿到了对应位置的迭代器。比如我们需要维护一个有序结构频繁在中间插入、删除节点list 就比 vector 有优势。vector 的中间插入需要把插入点之后的所有元素都往后搬一位删除同理整体搬移成本是 O(n)当元素是大对象时搬移还会伴随多次拷贝构造或移动构造开销不小。刚才说的“只要你已经拿到了迭代器”非常关键。如果每次插入前都需要遍历找到位置那遍历是 O(n)总复杂度还是 O(n)。list 没有随机访问能力查找某一个元素必须从头遍历这正是它最大的弱点。所以“list 插入是 O(1)”这句话完整版本是“给定迭代器时插入是 O(1)但没有随机访问找到插入点本身就是 O(n)”。在缓存友好性方面list 也远不如 vector。vector 的数据在内存中是连续存放的CPU 缓存命中率极高。list 的节点分散在不同堆地址每一次遍历都是一次随机内存访问缓存命中率低在数据量大的时候性能差距非常夸张。实测下来对于一千万个 intvector 的遍历速度可能比 list 快 20 到 50 倍这个数字在不同编译器上略有差异但趋势是一致的。6.2 什么场景不要用 list如果你主要是“尾部追加数据偶尔遍历”那 list 完全不是最优解vector 或者 deque 会更好。vector 的尾部插入是均摊 O(1)而且扩容策略可以提前预留空间。list 尾部插入虽然也是 O(1)但每次插入都要 new 一个节点开销比 vector 的尾部追加高不少。频繁查找的场景也不要用 list。list 的 std::find 是 O(n)而如果你用 vector 并存放在有序数组里可以用二分查找复杂度 O(log n)差距巨大。最简单的判断标准是如果你发现自己经常要使用 std::advance(it, n)、std::distance、operator[]说明你更需要一个随机访问容器。deque 是另一个容易被忽略的容器。很多情况下双端队列 deque 比 list 更合适它支持双端插入删除同时支持随机访问底层用分段连续内存实现。如果你只需要在头和尾操作deque 的性能通常优于 list。list 真正不可替代的场景是“需要在容器中间频繁插入删除并且操作都基于已持有的迭代器”。6.3 实际项目中的 list 使用建议根据我个人经验实际项目里 list 的使用频率远低于 vector 和 deque。很多开发者一看到“需要频繁插入删除”就直接上 list这是惯性思维但不一定是工程最优解。正确的思路是先分析数据的访问模式和操作位置再用 benchmark 验证。如果元素数量很少比如不到几百个vector 和 list 的性能差别根本不重要选择代码可读性更好的那个就行。如果你的数据对象非常大比如一个自定义结构体有几百字节list 在插入时比 vector 有优势因为 vector 扩容时会搬移所有已有对象而 list 只需要 new 一个节点。但现代 C 的移动语义已经大幅缓解了 vector 的搬移成本如果你的对象可以低成本移动vector 的优势会更明显。所以在 2025 年的工程实践中list 的使用场景进一步缩小主要还是在 LRU Cache、消息队列、链表哈希等特定数据结构中发光发热。模拟实现 list 的价值并不在于让你“以后都用 list”而在于你彻底理解一个双向链表容器需要处理哪些问题。这些问题包括内存布局、迭代器语义、异常安全、生命周期管理。理解之后不管遇到什么容器你的学习曲线都会平缓很多。7. 测试与调试经验模拟实现写完后怎么验证7.1 写一个尽可能全面的单元测试写完模拟实现之后第一件事不是直接上复杂业务而是从最基本的接口开始验证。我建议按这个顺序测试先测试默认构造和空链表遍历再测试 push_back 和 push_front 后的正向和反向遍历再测试 insert 和 erase接着测试拷贝构造和赋值运算符最后测试 const 迭代器和迭代器失效场景。一个比较有用的技巧是在测试代码里用 int 类型跑通所有基本接口之后再用自定义类包含指针成员或 unique_ptr 成员重新编译一遍这样可以发现拷贝构造中的浅拷贝问题。比如你可以定义一个类构造函数和析构函数里打印日志运行测试时观察对象的创建和销毁次数确认是否存在内存泄漏或重复释放。我平时还会配合 assert 来验证内部不变量遍历完后 _size 必须和实际节点数一致空链表的 begin() 等于 end()删除全部元素后 _head-next 和 _head-prev 都指向 _head。这些不变量可以在 insert、erase、clear 之后各检查一次用来快速定位 bug 出现在哪一步。7.2 gdb 调试链表结构的小技巧链表 bug 比较难调试因为节点之间的指针跳转不直观。我一般会在 gdb 里定义一个辅助打印函数直接打印节点地址、当前节点的 data、prev 的地址和 next 的地址。这样能快速看出链表是否成环、指针是否连接正确。比如在插入操作之后如果发现某个节点的 next 指向了一个还没分配的内存区域那基本就是指针赋值顺序出了问题。另一个工具是 AddressSanitizer编译时加 -fsanitizeaddress -g运行时会自动检测内存泄漏、越界访问和悬空指针。我自己写模拟实现时每完成一个阶段就会开启 ASan 跑一遍测试能抓到大量传统调试很难发现的细节问题。比如 delete 之后没有把指针置空后续访问了悬空节点这种问题 ASan 会立刻报出来。调试时的核心思路是“从内向外”先确认单节点构造正确再确认两个节点的连接正确最后才扩大规模测试。不要一上来就插入一万个节点出问题很难定位。每次只改变一个操作配合打印或者单步跟踪很快就能找到问题所在。7.3 一个经典 bug 的排查实录有一次我在实现 erase 时返回值写成 pos 本身而不是 pos 的下一个节点。在顺序遍历删除偶数的测试里程序没有崩但跳着删除了元素结果就是奇数也被删掉了。原因很简单删除当前节点后pos 的 next 指针已经被 delete 释放再拿原来的 pos 去 it行为的未确定性导致 next 指针指向了不可预知的内存。后来我改成先保存 next_node再 delete 当前节点最后返回 next_node 的迭代器问题就消失了。这个 bug 在面试时很常见面试官会问“erase 之后为什么要返回迭代器”。如果返回值指向下一个有效节点就能支持循环删除如果返回 void你只能自己在删除前保存下一个迭代器。STL 标准选择返回下一个迭代器就是为了让遍历删除的代码写起来既安全又简洁。8. 进阶扩展从 list 到 forward_list 和自定义容器8.1 forward_list单链表的特殊存在C11 引入了 forward_list它的底层是单链表只支持前向遍历。为了保证操作效率forward_list 的 insert 和 erase 接口和 list 不太一样它提供 insert_after 和 erase_after因为单链表只保存后继指针在给定位置之前插入需要遍历找前驱。forward_list 的优点是每个节点少一个指针内存占用更小在存储大量小对象时内存开销优势明显。如果你已经完整理解了 list 的实现forward_list 就是一次“减法题”节点去掉 prev 指针迭代器去掉 operator--插入删除改成为 after 语义。这个数据结构在内存受限的嵌入式场景中用得比较多工程里普通业务代码用 forward_list 的非常少。但理解它的设计能帮你加深对“容器接口设计和底层数据结构强相关”这个观点的印象。8.2 自己实现一个 list 的 reverse 接口list 的反转不需要像 vector 那样交换数据只需要把每个节点的 prev 和 next 指针互换。实现方式有两种一种是遍历所有节点依次交换每个节点的 prev 和 next另一种是将头尾交换并重新连接。对于带哨兵位的双向链表前一种更直观从第一个有效节点走到哨兵位对每一个节点执行 std::swap(node-prev, node-next)最后不要忘了把哨兵位的 prev 和 next 也交换。reverse 的时间复杂度是 O(n)空间复杂度 O(1)。这也是链表类容器常被称赞的点就地反转只需要修改指针不需要额外空间。如果你对链表结构足够熟悉reverse 的代码十行之内就能写完但很多新手还是会写错关键就是哨兵位的两个指针也要交换漏掉这一句就会出现诡异的行为。8.3 从模拟实现到阅读真实 STL 源码做到这里你已经把 list 的核心逻辑完整实现了一遍。如果想去读真实的 STL 源码我给你指条路先看 libstdc 里的 stl_list.h。你会发现它实现了 _List_node、_List_iterator、_List_const_iterator 三个结构整体设计和我们讲的高度一致但多了 allocator、异常安全、节点回收池等工程化细节。第一遍读的时候不要钻进 allocator 的细节里先沿着构造、析构、插入、删除这条主线走。读源码时重点关注两个东西一是 _List_node_base 这个基类它把 prev 和 next 指针抽出来避免模板实例化时重复存储二是 _List_iterator 和 _List_const_iterator 都继承自 _List_node_base迭代器的 和 -- 操作通过基类指针完成。这种设计减少模板展开的代码膨胀是源码工程化的一个重要细节。看完之后再回到你自己的代码会发现有些设计思路完全可以借鉴比如把节点基类独立出来、使用节点分配器等等。到这一步你这套模拟实现就算是真正学透了。