很多人学C学到list要么是上课背了几个接口要么是看源码看得云里雾里。真正面试或做项目的时候被问一句“list的迭代器为什么不是指针”“如果让你自己实现一个list节点和迭代器你会怎么设计”就卡住了。我自己的看法是list这个容器特别适合做一次手动模拟实现——它不像vector那样靠连续内存就能解释大半也不像map那样涉及红黑树的高深平衡逻辑它的核心其实就是节点指针的排列组合以及一个“为了统一边界而生”的哨兵节点。把list亲手实现一遍你能一次性打通几个重要技能模板编程、指针操作、迭代器模式、资源管理、深拷贝与赋值重载。这篇文章我会按照我自己实现时的思路走一遍先拆底层结构再写节点和迭代器接着把insert/erase这些核心接口写出来然后专门讲几个翻车率极高的细节最后给一份能跑的代码和测试思路。目标只有一个让你看完之后能自己从头写一个能用的list而不是只会背接口。1. list的底层结构双向循环链表与哨兵节点1.1 每个节点的样子list的底层是一个双向链表这是绝大多数人都知道的。每个节点至少要有三样东西一个存数据的成员一个指向下一个节点的指针一个指向上一个节点的指针。用C写出来结构体大概长这样template class T struct ListNode { ListNodeT* _next; ListNodeT* _prev; T _data; ListNode(const T val T()) : _next(nullptr) , _prev(nullptr) , _data(val) {} };这个结构本身没有太多玄机但有一个细节值得注意我们给构造参数一个默认值T()这样无论是new ListNodeint还是后面做哨兵节点时不需要显式传数据都能正常工作。对于自定义类型T()会调用其默认构造函数这也是STL容器里一种常见的“值初始化”写法。1.2 为什么一定要有哨兵节点很多第一次手写链表的人一开始会设计一个head指针指向第一个节点空链表时head为nullptr。这样做不是不行但代码会变得很难看在头部插入要判断head是否为空删除最后一个节点也要判断遍历也要小心空指针。所有边界情况都要单独写分支指针操作一旦复杂出bug的概率直线上升。list真正聪明的地方是引入了一个哨兵节点header node并且把链表做成循环的。这个哨兵节点不存业务数据它只是一个“标志位”_head-_next指向第一个有效节点_head-_prev指向最后一个有效节点空链表时两者都指向它自己。有了这个节点之后一切边界条件都被抹平了插入第一个节点不需要判断链表是否为空操作方式跟插入到中间一模一样。删除到只剩最后一个节点也不会出现nullptr解引用的问题。遍历的终止条件统一为“迭代器走到哨兵节点”。我用一个类比来帮助理解哨兵节点就像环形跑道上的终点线。你比赛遍历的时候不需要知道跑了多少圈只要看到终点线就知道该停了。如果没有终点线你就得额外记住“我到底跑了几圈”维护成本完全不一样。1.3 和vector、deque的定位对比写模拟实现之前还得先想明白list和vector、deque的核心差异不然你可能会在接口设计上照搬vector的思路写出来的东西四不像。维度vectordequelist底层结构连续内存数组分段连续缓冲区双向循环链表随机访问O(1)支持operator[]O(1)O(n)不支持operator[]头部插入O(n)要搬移元素O(1)O(1)尾部插入均摊O(1)扩容时会搬移O(1)O(1)中间插入O(n)搬移后续元素O(n)O(1)只改指针插入时迭代器失效所有迭代器失效部分失效其他迭代器不失效缓存友好度高中低节点分散在堆上一句话总结list牺牲了随机访问和缓存性能换来的是“任意位置插入删除都不搬移元素且插入不影响已有迭代器”。所以它最典型的应用场景是频繁在中间插入删除、元素本身很大拷移动成本高、或者需要稳定的节点地址来保存指针或引用。还有一点面试常考vector的插入可能导致整体搬迁因此所有迭代器失效deque插入可能导致中控指针变动部分迭代器失效但list的insert不会让任何已有迭代器失效只有被erase掉的这个迭代器本身失效。这一点后面实现erase的时候还要专门回来照顾它的返回值设计。2. 模拟实现的地基节点定义与迭代器封装2.1 节点结构体就这么简单节点定义上面已经给了就不再重复。这里要补充的是节点里维护的是“原始指针”但用户拿到的迭代器绝对不应该是一个裸指针。为什么因为裸指针的操作在C语义里就是地址加一个元素大小对于连续内存的vector这正好是下一个元素但对链表来说p只会把指针挪到当前节点内存的下一个地址那根本不是链表里的下一个节点。所以迭代器本质上是一个“包装了节点指针、并重载了运算符”的类对象。它内部保存Node*然后通过重载operator让指针走到_node-_next通过重载operator*返回节点里存放的数据。这样用户和算法库都能用统一的“类似指针”的语法来操作容器。这也解释了为什么std::sort不接收list的迭代器sort要求随机访问迭代器也就是支持it n这种一步跨到任意位置的写法而list的迭代器只能一步一步走。2.2 迭代器类的设计一个初版迭代器可以这样写template class T struct ListIterator { typedef ListNodeT Node; typedef ListIteratorT Self; Node* _node; ListIterator(Node* node nullptr) : _node(node) {} T operator*() { return _node-_data; } T* operator-() { return (operator*()); } 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 it) const { return _node it._node; } bool operator!(const Self it) const { return _node ! it._node; } };这里有一个经验前置返回引用后置返回值。前置版本不需要拷贝临时对象性能更好后置版本先保存一份旧状态再自增返回旧迭代器。虽然list场景下这点性能差异几乎可以忽略但这是C迭代器约定俗成的规范STL算法会依赖这些语义。operator-的返回值是T*这样写it-first的时候编译器会把它解析成it.operator-()-first效果等价于(*it).first。对自定义类型来说这个接口特别常用。2.3 一个迭代器类两份类型用模板参数区分const上面这个版本的迭代器有个问题没有办法区分普通迭代器和const迭代器。const listT对象调用begin返回的应该是const迭代器operator*返回const T不允许通过迭代器修改元素。如果只用一个迭代器类const对象的遍历会拿到T那const就形同虚设。解决办法是用两个模板参数Ref和Ptr来控制引用类型和指针类型template class T, class Ref, class Ptr struct ListIterator { typedef ListNodeT Node; typedef ListIteratorT, Ref, Ptr Self; Node* _node; ListIterator(Node* node nullptr) : _node(node) {} Ref operator*() { return _node-_data; } Ptr operator-() { return (operator*()); } // 其余运算符重载这里省略与前面版本完全一致 };然后在list类里定义两个迭代器类型typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator;这样一来普通迭代器的operator*返回Tconst迭代器的operator*返回const T。模板代码本身只有一份却生成了两种行为这就是模板参数控制语义的经典用法。这里有个细节很多人会忽略operator-里的(operator*())当Ref是const T时取地址得到的自然是const T*正好匹配Ptr。如果你在const版本里手动写return _node-_data;也能编译但上面的写法更通用能保证operator*和operator-的行为始终一致。3. 主体接口实现构造、析构、insert、erase与深拷贝3.1 初始化哨兵节点空的链表也要有“骨架”list类的成员很简单只需要一个Node* _head指向哨兵节点。构造函数里要做的事情不是把指针置空而是老老实实new一个哨兵节点并让它自成环list() { _head new Node; _head-_next _head; _head-_prev _head; }这一步别偷懒。如果只是把_head初始化为nullptr后面所有接口都得多写一堆判空逻辑。环一旦形成begin就是iterator(_head-_next)end就是iterator(_head)。空链表时begin和end指向同一个节点这跟标准库的[begin, end)左闭右开区间语义完全一致。3.2 insert是真正的万能入口list最核心的插入函数是在指定位置之前插入节点。我建议先实现insert再让push_back和push_front都复用它这样代码只有一份出bug的概率也低。iterator insert(iterator pos, const T val) { Node* cur pos._node; Node* prev cur-_prev; Node* new_node new Node(val); prev-_next new_node; new_node-_prev prev; new_node-_next cur; cur-_prev new_node; return iterator(new_node); }四行指针操作顺序很重要。我的经验是“先处理新节点两边的prev/next再去改前驱后继节点里的指针”。想象有前后两个节点夹着一个空位新节点要先自己站进去也就是先让new_node的_prev指向前驱、_next指向后继然后再让前驱的_next指向new_node、后继的_prev指向new_node。只要前两步先完成后面两步的顺序其实无所谓数据不会丢。有了insert之后void push_back(const T val) { insert(end(), val); } void push_front(const T val) { insert(begin(), val); }注意push_back传的是end()也就是在哨兵节点之前插入新节点会成为哨兵的前驱也就是链表最后一个节点。而push_front在第一个有效节点之前插入新节点成为哨兵的后继也就是第一个节点。这一个接口就把前后插入都覆盖了非常优雅。3.3 erase为什么返回“下一个节点”删除的代码也不复杂iterator erase(iterator pos) { assert(pos ! end()); Node* cur pos._node; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; return iterator(next); }这里的关键决策是返回值。我把next返回给调用者而不是返回void。为什么因为删除之后cur的内存已经释放你手里那个迭代器再用就是访问野指针。返回下一个节点调用者可以直接接着遍历while (it ! l.end()) { if (条件) { it l.erase(it); } else { it; } }如果erase返回void遍历删除就得先保存下一个节点的迭代器再删当前的写法会绕很多。这个设计考虑本质上就是为了照顾迭代器失效语义list的erase只让当前迭代器失效其他迭代器不受影响。返回下一个节点正好让使用者无缝衔接继续遍历。3.4 拷贝构造与赋值深拷贝的两个常见姿势list默认的拷贝构造是浅拷贝会把_head指针原样复制一份结果两个对象指向同一个链表析构时double free跑不掉。所以必须自己实现深拷贝。最简单的深拷贝姿势是用已有的接口先把哨兵节点建好然后遍历源链表逐个push_backlist(const list l) { _head new Node; _head-_next _head; _head-_prev _head; const_iterator it l.begin(); while (it ! l.end()) { push_back(*it); it; } }赋值运算符我推荐用“拷贝并交换”的思路参数直接按值传这样一份代码同时处理了自赋值和异常安全void swap(list l) { std::swap(_head, l._head); } list operator(list l) { swap(l); return *this; }传参时调用拷贝构造生成临时对象然后交换两个链表的头指针。临时对象在函数结束时析构顺手把原来链表的内存释放掉。整个过程不需要判断this l因为即使是自赋值也会先做一次完整的拷贝。这是C里非常经典的现代写法比传统的“先释放再分配新内存”安全得多。析构函数则要分两步先清空有效节点再释放哨兵节点void clear() { iterator it begin(); while (it ! end()) { it erase(it); } } ~list() { clear(); delete _head; }这里有个很容易被忽略的点clear之后_head的_next和_prev会重新指向它自己因为erase一圈会把哨兵两边的指针重新接回它本身。这样处理完哪怕析构前又调用了push_back链表依然能正常工作。4. 模拟实现最容易翻车的几个细节4.1 普通迭代器到const迭代器的转换标准库支持这样的写法listint l; listint::const_iterator it l.begin();但按照前面2.3节的迭代器定义iterator和const_iterator是同一个类模板的两个不同实例它们之间没有自动转换关系上面这段代码编译不过去。解决办法是在迭代器类里加一个模板构造函数template class T1, class Ref1, class Ptr1 ListIterator(const ListIteratorT1, Ref1, Ptr1 it) : _node(it._node) {}这个构造函数允许iterator隐式转换为const_iterator。但这里藏着一个小瑕疵它同时也允许const_iterator转换成iterator因为构造函数本身没有做权限限制。标准库为了做到真正的类型安全会让迭代器内部保存的节点指针区分Node*和const Node*const版本保存的是const Node*这样反过来转换就会被编译期拦截。我们教学版为了简洁统一用Node*这个类型安全漏洞是存在的。我个人的建议是日常写代码时把它当成一个已知简化面试时如果能主动说出“标准库这里其实更严格会用const Node*来防止反向转换”一定会是加分项。4.2 为什么std::sort接不住list很多人写demo的时候会顺手写下std::sort(l.begin(), l.end())然后编译直接报错。原因前面说过sort要求随机访问迭代器list的迭代器连it 3都做不到怎么可能支持快排里的mid first (last - first) / 2这种操作。list自己也提供了l.sort()它的底层通常是归并排序因为归并排序的核心操作是合并两个有序链表只需要不断比较头节点并移动指针非常契合链表的特性。如果你是为了练手完全可以自己实现list的sort成员函数用迭代器改写归并逻辑这对理解“算法与数据结构怎么适配容器”非常有帮助。顺带一提list还有一个很特别的接口splice它能在常数时间内把另一个list的一段节点“嫁接”过来。因为是改指针而不是拷贝数据所以即使数据量很大也不会搬移元素。这个是list独有的优势模拟实现到后面可以加上去。4.3 模板代码里那几类经典编译错误模拟实现list的过程中最常见的编译错误我总结成三个一是忘写typename。在类模板外部写typename listT::iterator这种类型时必须加typename关键字因为编译器在模板实例化之前无法确定listT::iterator到底是个类型还是个静态成员变量。这个报错信息很长很绕本质就是一个typename的事。二是内部类型不完整。你在list类里用typedef ListNodeT Node;如果ListNode只是向前声明而没定义完整结构很多地方编译会报“使用未定义的类型”。解决办法就是保证节点定义在list类之前并且是一个完整结构。三是迭代器里访问另一个模板实例的私有成员。如果你把迭代器写成class并让_node私有那么普通迭代器和const迭代器这两个不同实例之间是无法互相访问_node的模板构造函数的写法会直接编译失败。我建议要么用struct让成员公开要么在迭代器类里加一句template class, class, class friend struct ListIterator;4.4 迭代器失效与空表操作边界list的insert不会让已有迭代器失效erase只让当前迭代器失效。这个规则听着简单但使用上的坑主要在“空表边界”。比如pop_back我写的实现是erase(--end())如果链表为空end()指向哨兵--end()会走到哨兵的下一个节点。在循环链表里空表的哨兵-next还是哨兵自己所以--end()的结果还是哨兵erase会断言失败。这正好暴露问题空表不能执行pop操作。另一个容易出问题的是写while (it ! l.end())然后循环里l.erase(it);但不接收返回值。第一次erase之后it指向的节点已经释放继续it就是野指针操作。正确的做法是用返回值更新it或者保存next it;再删。前者更直观后者在旧式代码里也很常见。调试时如果发现程序卡死八成是链表成环断了。比如某次插入操作顺序写错前驱和后继的指向互相矛盾遍历就会永远走不到哨兵。这时候我通常会在纸上把两个指针的指向画出来跟着代码走一遍比在IDE里盲目打断点快得多。5. 完整可运行的迷你list与测试用例5.1 拼接前文的代码把2.1节的ListNode、2.3节的ListIterator模板、3.1到3.4节的list类拼在一起再补上#include cassert、#include utility和#include iostream就是一个可编译运行的迷你list了。注意list类里还需要一个size方法方便测试我的做法是写一个O(n)的遍历版本size_t size() const { size_t n 0; const_iterator it begin(); while (it ! end()) { n; it; } return n; }这里要说明一下标准库在C11之后要求size是O(1)但那是靠额外维护一个节点计数器实现的。教学版为了保持思路简单没有加计数器遍历计数就够用了。如果你要在面试里谈这个一定要能说出“标准库的size是常数时间我这里是遍历如果要模拟得更像标准库应该加计数器”。5.2 测试用例把每个接口都“打”一遍写测试时我习惯从基础功能到边界情况一层层往上加int main() { // push_back 遍历 listint l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_front(0); for (auto it l.begin(); it ! l.end(); it) { std::cout *it ; } std::cout \n; assert(l.size() 4); // insert 中间位置 auto it l.begin(); it; it; l.insert(it, 99); assert(l.size() 5); // erase 中间位置 it l.begin(); it; l.erase(it); assert(l.size() 4); // 拷贝构造 listint copy(l); assert(copy.size() l.size()); l.push_back(100); assert(copy.size() ! l.size()); // 赋值运算符 listint assign; assign copy; assert(assign.size() copy.size()); // const迭代器 const listint const_ref copy; int sum 0; for (auto it const_ref.begin(); it ! const_ref.end(); it) { sum *it; } assert(sum 0); // 清空后再使用 copy.clear(); assert(copy.empty()); copy.push_back(42); assert(copy.size() 1); std::cout all tests passed std::endl; return 0; }这里有一个小经验测试完成后一定要在输出里打印all tests passed而不是什么都不输出。没有输出会让程序“看起来像正常退出”出了问题你也很难判断是走到最后了还是中途崩了。加一个显式打印跑一次就知道整体链路是通的。5.3 调试心得内存问题怎么快速定位list是链式结构最能折磨人的内存问题基本就是两个内存泄漏和无效访问。我的排查顺序是这样的。先看析构。用_CrtDumpMemoryLeaks()Windows/VS环境或valgrindLinux环境跑一遍如果有泄漏定位到具体哪里new了没delete。最容易漏的是写构造或赋值时忘了初始化哨兵节点比如赋值运算符里如果直接把_head指向临时对象临时对象析构时会把哨兵也释放掉后面访问就是野指针。再看无效访问。最典型的就是erase之后继续用旧迭代器。如果在遍历删除时程序随机崩八成就是这里。我习惯在erase里加一句assert(pos ! end());这样至少能拦住“试图删除哨兵”的情况。至于删除后继续使用这属于使用方的问题靠接口规范很难自动拦住。还要养成一个习惯每写完一个接口立刻编译运行一次而不是把所有代码写完再调试。我见过很多初学者一口气写完几百行然后面对一堆报错不知道从哪里下手。分步验证的痛苦会小得多。写insert测insert写拷贝构造测拷贝构造。积累出一套完整的测试用例返回来跑会安心很多。6. 模拟实现之后我对list乃至STL的看法6.1 这个练习帮我打通了什么亲手写完list之后最大的收获不是复述代码而是理解了一个容器类“为什么长成这样”。哨兵节点不是拍脑袋想出来的是被边界条件逼出来的迭代器的封装不是过度设计是裸指针真的没法表达链表遍历insert返回迭代器也不是可有可无是为了支持统一的接口语义。有了这个底子你再回头去看STL其他容器的实现或者看相关的八股题会轻松很多。比如你看到一个算法要求ForwardIterator你会自动想到list看到RandomAccessIterator你会想到vector和deque迭代器失效规则也不再是死记硬背而是能从底层结构推出来。这就是模拟实现带来的“迁移能力”。6.2 还想再进一步这些方向值得做如果练完这篇的基础版还想继续我建议往这几个方向扩展给迭代器加operator--的后置版本已经实现了可以再尝试用std::reverse_iterator包装普通迭代器直接得到反向迭代器接口。给list加splice、merge、remove_if、sort这几个成员函数它们最能体现链表的算法特性。把节点类型改成区分NodeT和const NodeT进一步逼近标准库的const类型安全。给类模板增加Allocator参数把节点内存分配改成传入的分配器。每做一步你都会对STL又多一层理解。等有一天你不看这篇文章也能从头写出来那list这个知识点就真正是你的了。