平时写代码顺序容器里用得最多的就是 vector但一旦碰上中间频繁插入删除、迭代器容易失效的场景我基本都会直接换成 list。C 的 list 类在标准模板库里的存在感不算强但它的底层结构——双向带头循环链表以及围绕它设计的迭代器和接口藏着不少值得抠的细节。这篇东西想做的事很简单把 list 的常用接口按使用场景捋一遍再手写一个能跑、能验证的模拟版本从节点的构造到迭代器封装再到插入删除的语义一步步过。适合刚学完 C 语法、想把 STL 容器底层搞明白的读者也适合面试前临时抱佛脚的人。1. 从使用出发list 常用接口到底该记哪些1.1 构造与赋值五种初始化方式怎么选list 的构造接口和 vector 高度相似但有一个很容易被忽略的点list 没有直接提供operator[]也没有at()这意味着它压根不支持随机访问。构造 list 最常见的有五种写法#include list using namespace std; listint l1; // 空表 listint l2(10); // 10 个默认值 0 listint l3(10, 5); // 10 个 5 listint l4(l3); // 拷贝构造深拷贝 listint l5(l4.begin(), l4.end()); // 迭代器区间构造 listint l6 { 1, 2, 3, 4 }; // 初始化列表listint l2(10)这种写法在底层会调用节点的默认构造也就是把每个节点的数据成员用T()初始化。如果你存的类型是自定义结构体请务必保证它有默认构造函数否则编译阶段就会报错。迭代器区间构造特别适合从一个容器里挑一段数据出来建新表适配所有输入迭代器vector、deque、set 都行。赋值相关接口主要有三个listint l1 { 1, 2, 3 }; listint l2; l2 l1; // 赋值运算符深拷贝 l2.assign(5, 8); // 清空后填充 5 个 8 l2.assign(l1.begin(), l1.end()); // 清空后用迭代器区间填充assign 和operator的核心区别在于operator要求两边类型一致assign 可以从任意果迭代器区间填充。实际开发中如果你确定目标表已经有足够空间assign 会比先 clear 再 insert 少一次空表的构造开销不过 list 的节点是逐个 new 出来的这点差异通常可以忽略。1.2 容量与元素访问size 和 front/back 的使用边界list 的容量接口很少就size()、empty()、max_size()三个。这里注意一个细节list 的size()在标准库里是常数时间不是遍历统计的。所以你在循环里反复调用size()做判断没有性能问题但前提是用标准库的 list手写模拟版本时size 的计算方式完全取决于你存不存节点数量这个成员。list 的元素访问接口只有front()和back()listint l { 10, 20, 30 }; int first l.front(); // 10 int last l.back(); // 30 l.front() 99; // 返回引用可以直接改不少人刚接触 list 时会下意识找list[3]找不到就认为 list 很“残废”。其实这不是缺陷而是链表的结构决定了它无法在 O(1) 内完成随机访问。list 的每个节点在内存中是离散分布的想拿到第 3 个元素必须从头节点沿着 next 指针走 3 步。如果你真的需要“按下标快速访问 中间插入删除”那就该考虑 deque而不是硬用 list。1.3 修改接口push/pop/insert/erase 的语义细节修改接口是 list 使用频率最高的部分。基础的四件套是push_back、pop_back、push_front、pop_front这四兄弟都是 O(1) 操作。中间插入和删除对应的就是insert和eraselistint l { 1, 2, 3, 4 }; auto it l.begin(); it; // 指向第二个元素 l.insert(it, 99); // 在第二个元素之前插入 99 l.insert(it, 3, 88); // 在 it 之前插入 3 个 88 l.insert(it, { 5, 6 }); // 在 it 之前插入初始化列表 it l.begin(); it; it l.erase(it); // 删除第二个元素返回下一个有效迭代器 l.erase(l.begin(), it); // 删除一段区间 [begin, it)insert 的返回值是“新插入的第一个元素的迭代器”erase 的返回值是“被删除元素的下一个位置的迭代器”。这个返回值设计非常重要很多人写删除循环时忽略了等到遍历的时候直接迭代器失效程序崩溃。标准写法应该是listint l { 1, 2, 3, 4, 5, 6 }; for (auto it l.begin(); it ! l.end(); ) { if (*it % 2 0) it l.erase(it); // 删除偶数 else it; }这里list 的 erase 不会影响除当前迭代器以外的其他迭代器这也是它比 vector 更适合在遍历过程中删除元素的原因。vector 在 erase 时需要搬移后续元素所有指向删除点之后的迭代器都会失效而 list 的 erase 只是改了几个指针别的节点的地址完全没变指向它们的迭代器当然还活着。2. 为什么模拟实现一定要选双向带头循环链表2.1 三种链表结构对比单链表、双向链表、循环链表教材里讲了一遍又一遍到了自己动手实现 list 时为什么要选“双向带头循环”这个组合逐个拆开看单链表的节点只有一个 next 指针想删掉当前节点必须从头开始找到它的前一个节点复杂度 O(n)。这让erase()变得很尴尬因为end()迭代器对应的是最后一个有效节点的下一个位置单链表根本没法用 O(1) 让前驱的 next 跳过当前节点。双向链表给每个节点加了 prev 指针删除当前节点时直接让prev-_next跳过当前节点就行不需要找前驱了O(1)。这是 list 的erase()能做到常数时间删除的基础。带头节点则解决了一个更隐蔽的问题空表和只有一个节点的表在插入删除时逻辑不统一。不带头节点时删除第一个节点需要额外更新头指针带头节点后头指针永远指向一个不存储有效数据的哨兵节点所有节点包括第一个和最后一个都有前驱和后继插入删除代码完全统一没有任何特判。循环让尾节点的 next 指向头节点头节点的 prev 指向尾节点。这样push_back和push_front的代码一模一样只是改的指针方向相反end()迭代器可以自然地用头节点来表示。总结一下就是无头单向链表实现简单但插入删除边界条件多双向不循环的链表删头节点时要单独处理双向带头循环是 STL 设计者权衡后选的结构因为它把边界情况全部消解在循环结构里代码最干净。2.2 头节点哨兵节点的关键作用头节点不存有效数据但它不是浪费。它让“空表”这个概念不再特殊空表的头节点的 next 和 prev 都指向自己。插入第一个元素时无论插入位置在哪都是一个统一的“在节点 A 和节点 B 之间挂一个新节点”的操作。哨兵节点还引出一个重要的迭代器约定end()返回的就是头节点的位置。所以循环遍历的终止条件是it ! end()而不是it-_next nullptr。这种设计让 for 循环遍历所有容器时的写法高度统一for (auto it l.begin(); it ! l.end(); it)这条代码对所有 STL 容器都成立。实际写代码时头节点的初始化长这样templateclass T struct list_node { list_nodeT* _next; list_nodeT* _prev; T _val; list_node(const T val T()) : _next(nullptr), _prev(nullptr), _val(val) {} };头节点初始化_head new node; _head-_next _head; _head-_prev _head;这行_next和_prev都指向自己的赋值是空表能被正确遍历和插入的基础。新手自己实现链表最容易漏的就是这一步漏了之后空表上 push_back新节点倒是接到了头节点后面但头节点的 next 还是自己链表直接断裂。2.3 模拟实现的整体骨架模拟实现 list 时建议放在一个独立的命名空间里避免和标准库冲突。整体结构分三层namespace mylist { templateclass T struct list_node { ... }; templateclass T, class Ref, class Ptr struct list_iterator { ... }; templateclass T class list { public: typedef list_nodeT node; typedef list_iteratorT, T, T* iterator; typedef list_iteratorT, const T, const T* const_iterator; // 接口声明 private: node* _head; size_t _size; }; }_node 成员不是必须的但有了它size()就能 O(1) 返回没有它就得每次遍历数节点。标准库的 list 确实在 O(1) 内返回 size所以我这里也建议存一个_size。不过要注意所有修改节点数量的接口insert、erase、push、pop、clear都得同步维护_size漏掉任何一个size 就偷偷失真。3. 迭代器封装list 模拟实现的灵魂3.1 为什么原生指针不能直接当迭代器string 和 vector 的迭代器可以直接用原生指针实现因为它们的元素在内存中是连续存储的操作天然就指向下一个元素。但 list 的节点在内存中七零八落节点之间相隔多远完全不可预知原生指针的没有任何意义。所以 list 的迭代器必须是一个自定义类内部封装一个指向节点的指针再重载、--、*、-、、!这些操作符。从使用者视角看它“表现得像指针”但从实现视角看它只是把指针操作翻译成了“走 next 指针”或“走 prev 指针”。templateclass T, class Ref, class Ptr struct list_iterator { typedef list_nodeT node; node* _pnode; list_iterator(node* p nullptr) : _pnode(p) {} Ref operator*() { return _pnode-_val; } Ptr operator-() { return _pnode-_val; } list_iterator operator() { _pnode _pnode-_next; return *this; } list_iterator operator(int) { list_iterator tmp(*this); _pnode _pnode-_next; return tmp; } list_iterator operator--() { _pnode _pnode-_prev; return *this; } bool operator(const list_iterator it) const { return _pnode it._pnode; } bool operator!(const list_iterator it) const { return _pnode ! it._pnode; } };注意operator()和operator(int)的重载区分前置版本返回引用后置版本返回旧值的拷贝。这是因为it的意思是“先自增再返回现在的自己”可以返回引用it的意思是“先返回过去的自己再自增”那个过去的自己必须保存在一个临时对象里返回不了引用。实现后置版本时如果直接返回临时对象一定要记得把tmp保存好再让_pnode往前走顺序反了返回的就是自增后的值了。3.2 operator* 的引用返回为何如此重要operator*返回的是Ref类型。在普通迭代器中Ref是T也就是元素引用。这样写既能读取元素也能直接给它赋值listint l { 1, 2, 3 }; auto it l.begin(); *it 100; // 通过迭代器修改元素需要返回 T如果operator*返回的是值拷贝T那*it 100就只能改到一个临时对象上原链表里的数据纹丝不动。这个“返回引用”的设计是所有可变迭代器的底线要求。在模拟实现里Ref和Ptr作为模板参数传入普通迭代器传T和T*const 迭代器传const T和const T*这样我们只需要写一份迭代器代码编译器自动帮我们实例化出普通版和 const 版。3.3 const 迭代器的两种实现思路一种是把迭代器拷贝一份把operator*的返回类型改成const T代码大量重复。另一种就是上面这种传模板参数的写法这是 STL 本身在部分编译器内部采用过的思路。我更推荐后者因为iterator和const_iterator之间的类型关系也更清晰。typedef list_iteratorT, T, T* iterator; typedef list_iteratorT, const T, const T* const_iterator;const 迭代器的使用场景是你有一个const listint对象或者通过const 引用访问 list这时候begin()返回的必须是const_iterator因为你不允许通过这个对象修改数据。begin 的两个重载版本要这样写iterator begin() { return iterator(_head-_next); } const_iterator begin() const { return const_iterator(_head-_next); }这里有个极其隐蔽的坑如果只写了非 const 版本的begin()那么const listint对象调用begin()时会优先匹配 const 版本找不到就报错。面试时经常会问“const 对象的 begin 返回什么”很多人答不上来本质就是对 const 成员函数重载机制不熟。3.4 迭代器失效的概念与边界list 的迭代器失效规则比 vector 宽松很多但也不是完全不会失效具体规则如下操作vectorlist插入元素插入位置之后所有迭代器失效扩容时全部失效已有迭代器全部有效删除元素删除位置之后所有迭代器失效被删除元素对应的迭代器失效其余有效修改元素指向修改位置的迭代器仍然有效仍然有效list 的这个特性来源于节点内存独立性插入新节点不会搬移旧节点删除旧节点只是释放那一块内存。但请注意下面这段写法的行为就是未定义的listint l { 1, 2, 3 }; auto it l.begin(); l.erase(it); it; // 错误it 指向的节点已经被 delete虽然编译能通过但运行时行为不可预测——it._pnode指向的内存已经释放再访问它的_next就是读野指针。所以 erase 之后一定要用返回的迭代器接力而不是继续使用旧的。4. 核心接口的模拟实现与细节取舍4.1 初始化与销毁构造函数和析构函数怎么配合模拟 list 的构造函数要完成两件事创建哨兵节点并把_next、_prev都指向自己把_size清零。list() : _size(0) { _head new node; _head-_next _head; _head-_prev _head; }析构函数要先清空所有有效节点再释放头节点~list() { clear(); delete _head; _head nullptr; } void clear() { node* cur _head-_next; while (cur ! _head) { node* next cur-_next; delete cur; cur next; } _head-_next _head; _head-_prev _head; _size 0; }clear()之后链表要重新回到“空表”状态所以头节点的两个指针必须再次指向自己。如果只 delete 节点忘了把_head的两个指针拉回原位后续再 push_back 新节点时链表就乱了。4.2 insert 和 erase 的完整逻辑insert是在指定位置之前插入新节点核心逻辑是四步改指针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; _size; return iterator(newnode); }这个顺序不是随便排的先把prev-_next指向新节点再把新节点的 prev 和 next 分别指向 prev 和 cur最后把cur-_prev指向新节点。只要能把新节点“焊”在 prev 和 cur 之间任何顺序其实都能成立但关键是不能在连线之前就修改cur-_prev否则找不回 prev 了。erase是 insert 的逆操作iterator erase(iterator pos) { // 不允许删除哨兵节点否则链表结构会被破坏 if (pos end()) return end(); node* cur pos._pnode; node* prev cur-_prev; node* next cur-_next; prev-_next next; next-_prev prev; delete cur; _size--; return iterator(next); }边界条件检查放在函数开头不能 erase 头节点。头节点是哨兵删掉之后 end() 就失效了链表循环结构也被破坏。标准库的 erase(head()) 行为是未定义的所以这里我们主动拦住比放行更安全。返回值是next也就是被删除节点的后继这点和标准库保持一致。4.3 push、pop 四件套的复用push_back 和 push_front 其实都可以复用一个万能接口在某个位置之前 insert。void push_back(const T val) { insert(end(), val); } void push_front(const T val) { insert(begin(), val); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }push_back用insert(end(), val)正好实现在尾节点后面、头节点之前插入语义完全吻合。pop_back用erase(--end())--end()得到的是尾节点迭代器删除它不违反“不能删哨兵”的约束因为此时真正删的是尾节点不是头节点。这种复用的好处是所有正确性都集中到了 insert/erase 两个函数里push/pop 只是薄薄一层语法糖。4.4 拷贝构造和赋值运算符的深拷贝list 默认生成的拷贝构造函数是浅拷贝_head指针会被原封不动复制两个 list 对象共享同一套节点析构时二次释放直接崩溃。所以必须自己写深拷贝。list(const listT lt) { _head new node; _head-_next _head; _head-_prev _head; _size 0; for (auto it lt.begin(); it ! lt.end(); it) { push_back(*it); } }赋值运算符最稳妥的写法是“先拷贝再交换”void swap(listT lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } listT operator(const listT lt) { if (this ! lt) { listT tmp(lt); // 先做一份深拷贝 swap(tmp); // 再把当前对象和临时对象交换 } return *this; }operator的核心逻辑其实很简单既然要赋值的是一份全新的数据那就先构造一个临时 list深拷贝然后把当前对象的_head和_size跟临时对象整体交换。临时对象析构时带走的是原来属于当前对象的废旧节点完美避免内存泄漏。这种写法叫 copy-and-swap它自动处理了自赋值this和lt是同一个对象时拷贝一份一模一样的交换之后还是原来那套数据逻辑没有风险。5. 实测中的陷阱常见误用与性能对比5.1 list vs vector什么时候别用 listlist 的每个节点都额外携带两个指针。一个 int 数据 4 字节一个节点的实际开销至少 12 字节三指针对齐后可能是 16 或 24 字节内存利用率不到一半。再看访问方式list 的节点散落在堆内存的不同角落遍历时 CPU 缓存基本帮不上忙vector 的元素紧密排列缓存命中率极高。所以即使在某些操作上 list 理论复杂度占优实际跑起来未必快。场景推荐容器理由频繁随机访问vectorO(1) 下标访问list 做不到只在尾部插入删除vector尾部操作 O(1)缓存友好中间频繁插入删除list不用搬移元素O(1) 改指针元素体积大且需要中间插入list搬移大对象成本高移动节点成本低需要频繁按值查找都可以但应配合算法两者都是 O(n)一个比较反直觉的点是元素构造/拷贝成本极低时比如 int中间插入少量次数vector 甚至可能比 list 快。因为 vector 搬移 int 只是 memcpy 级别而 list 每次插入都要 new 一个节点、改多个指针new 本身就要消耗几十纳秒。性能选型永远要拿真实数据说话不要只看渐近复杂度。5.2 操作类接口splice、remove、unique、sort 的正确认识标准库 list 还提供了一批“操作类接口”经常被忽略但实际很有用。splice可以把另一个 list 的节点直接“嫁接”到当前 list不拷贝数据只改指针listint l1 { 1, 2, 3 }; listint l2 { 10, 20, 30 }; auto it l1.begin(); it; // 指向 2 l1.splice(it, l2); // 把 l2 全部节点拼接到 l1 的 it 之前 // l1: 1 10 20 30 2 3 // l2: 空splice是 O(1) 操作因为只是改指针一个元素都不搬。不过 splice 之后l2就空了如果你还以为 l2 里还留着那三个节点逻辑就会出错。remove是“删除所有等于指定值的节点”unique是“删除相邻重复的节点”注意是“相邻重复”。如果数据是1, 1, 2, 2, 1unique 会删成1, 2, 1而不是把所有 1 都删光。sort是 list 自己实现的成员函数l.sort(); // 升序排序 l.sort(greaterint()); // 降序排序为什么不能用std::sort(l.begin(), l.end())因为std::sort要求随机访问迭代器list 的迭代器是双向迭代器连it 5这种操作都不支持更别提快速排序需要的任意跳跃了。list 内部 sort 用的是归并排序的变体复杂度 O(n log n)但不用随机访问也能实现。5.3 手写 list 时最容易踩的三个坑第一个坑是节点内存泄漏。insert 里new nodeerase 里如果忘了delete cur删除操作就会泄漏一个节点的内存。写clear()时如果只用delete cur却忘了保存cur-_next一旦 delete 完成你再访问cur-_next就是野指针。正确写法先用临时变量记录 next再 delete 当前节点。第二个坑是 const 迭代器的类型混淆。const_iterator和iterator是不可以相互赋值的严格意义上的类型转换不存在但const_iterator可以由iterator隐式转换而来吗在我上面给出的模板实现里list_iteratorT, T, T*和list_iteratorT, const T, const T*是两个不同的类模板实例编译器不会自动做这个转换。标准库的处理方式是在迭代器类里加一个转换构造函数允许普通迭代器转 const 迭代器。如果不处理就会出现const_iterator it l.begin();编译失败的问题。第三个坑是--end()和erase(end())的边界。insert(end(), val)合法erase(end())非法。很多人记混淆写--end()错了因为 end() 返回的是头节点对它自减会走到尾节点这恰恰是我们想要的但 erase 头节点会把整个链表结构拆掉。一句话记法insert 是在 pos 之前插入pos 是 end() 没问题erase 是删掉 pos 指向的节点pos 必须指向有效数据节点。6. 模拟实现清单与进一步扩展方向6.1 完整接口覆盖检查模拟实现做到上面这些基本覆盖了 list 最高频的接口。把能力清单列一下分类已实现接口构造/析构默认构造、拷贝构造、析构、clear赋值operator、swap迭代器begin、end、const 版本容量size、empty元素访问front、back修改insert、erase、push_back、pop_back、push_front、pop_front区间操作assign 可用 clear insert 组合实现empty 可以直接返回_size 0也可以返回_head-_next _head两种写法等价。front 和 back 返回引用T front() { return _head-_next-_val; } T back() { return _head-_prev-_val; } const T front() const { return _head-_next-_val; }6.2 可以继续做的方向基础版模拟实现之后还有几个可以继续深入的方向。第一个是增加分配器支持标准库的 list 第二个模板参数本质上是内存分配策略自己实现时可以先用new和delete顶着深入后再研究池化分配。第二个是完善迭代器类型萃取让自写的 list 能配合std::distance、std::advance这类算法工作这需要给迭代器定义iterator_category、difference_type等内部类型。第三个是增加 rbegin/rend 反向迭代器反向迭代器本质上就是在普通迭代器上包了一层适配器把映射成普通迭代器的--。还有一个容易被追问的点list 的 sort 是怎么用“非随机访问迭代器”实现的答案是自底向上的归并排序逐步合并有序段不需要随机跳跃。如果你想进一步挑战自己可以不去调用标准库算法纯手写归并排序来操作 list 的节点指针那个过程对理解链表操作非常有帮助。最后说说我在实际使用中的体会list 这个容器平时存在感不高但一旦遇到“遍历中删除元素”“两个链表整体拼接”“元素拷贝成本很高”的场景它是不可替代的。面试里考 list 的模拟实现重点永远不在背代码而在于你能否说出“为什么带头节点”“为什么迭代器不能是原生指针”“为什么 erase 返回下一个迭代器”这三个为什么。把这些想通了其他容器map、set 等的节点式结构也就一通百通了。