如果你跟我一样学C初期只会拿vector怼一切数据存储等真遇到“在中间位置频繁插入删除”的需求时评测工具跑出的耗时能让你怀疑人生。这正是 STL 里list双向链表存在的理由它在任意位置插入和删除都是常数时间并且插入元素后所有迭代器都不会失效。这篇内容我会先讲清楚list的底层机制和常用接口再带手撕一个简化版双向链表把结点、迭代器、增删改查这些核心代码一步步写出来。这是给刚学完类与对象、想深入理解 STL 的读者准备的。你不需要提前会链表只需要见过vector、知道构造函数和析构函数的基本规则就行。手撕部分我会刻意写得比标准库简单很多但保留双向链表最核心的骨架让你看完能自己敲一遍也敢说“我确实理解list了”。1. 当vector不够用list的存在理由1.1 数组和链表的不同节奏先想象一下电影院前面的连排座位。vector就像这种固定连排座位每个座位有编号你走到 5 号座位直接坐就行所以按下标访问是 O(1)。但如果你想在第 3 个人和第 4 个人之间插一个座位麻烦就来了后面所有人都得往右挪一位。这就是vector在中间插入的代价——平均要把后半段元素整体搬移O(n) 的时间跑不掉。list不一样它像一条用绳子串起来的挂卡。每个卡片知道前一张是谁、后一张是谁你在任意两张卡片之间插入一张新卡片只需要解开两处绳结再重新系上其他卡片完全不用动。插入操作的时间复杂度自然就是 O(1)。代价则是你没法直接走到第 5 张卡片必须从第一张开始顺着绳子一张张数过去。所以这两种容器没有谁绝对更好只有谁更匹配场景。如果你主要按下标随机访问数据读多写少vector就是正确答案如果你需要在头部、尾部、或者任意已知位置高频插入删除list才能让你免受元素搬移的折磨。1.2 list与vector、deque的定位对比很多入门教程喜欢直接列一个容器对比表但如果不结合真实使用场景背下来也很快就忘了。我给你一个更好用的记忆方式先把容器按“底层布局”分成三类再按使用场景去套。容器底层布局随机访问中间插入/删除头尾插入适用场景vector连续内存数组O(1) 极快O(n) 低效尾部 O(1)头部 O(n)频繁按下标读、尾部追加deque分段连续内存O(1) 快O(n) 低效头尾都是 O(1)双端队列、头尾都有插入list双向链表不存在O(1) 只需改指针O(1)需保留迭代器并频繁中间增删forward_list单向链表不存在O(1) 知道前驱时头部 O(1)极度省内存的链表场景有个细节值得注意list中间插入虽快但“找到插入位置”这一步本身可能是 O(n)。所以它的完整价值是“一旦你持有了某个位置的迭代器后续所有插入删除都极其廉价”。这在实现 LRU 缓存、任务调度器、维护有序但经常小范围调整的数据时是vector完全给不了的。1.3 入门阶段最容易踩的list使用误区list的误用比很多人想象中频繁。第一个误区试图用下标访问list[3]这是编译错误因为它没有operator[]。你只能用迭代器或者std::advance移动过去。第二个误区排序调用std::sort这也是编译错误——std::sort要求随机访问迭代器而list的迭代器是双向迭代器只能和--。必须调用list.sort()这个成员函数它内部对链表结构做了特定排序优化。第三个误区写循环删除时习惯性地it之后又在循环体里用it结果迭代器已经失效。下面这段代码就是典型std::listint nums {1, 2, 3, 4, 5}; for (auto it nums.begin(); it ! nums.end(); it) { if (*it % 2 0) { nums.erase(it); // it已经失效循环体里却还想继续it } }正确写法是it nums.erase(it);因为erase会返回被删除元素的下一个迭代器。这个模式在map、set里也类似但vector的erase返回的也是下一个迭代器这里规则反而一致了很多人就是因为懒得多想一步才踩坑。2. 双向链表的底层机制迭代器为什么不会失效2.1 结点、头和哨兵一个结点怎么串起整条链双向链表的每个元素都不是裸数据而是包在一个“结点”Node里。一个结点有三个部分prev指针指向前一个结点next指针指向后一个结点外加一个data存放实际值。真正写代码时还会看到头尾哨兵sentinel的设计标准库list内部通常会有一个不存数据的头结点让begin、end、空链表判断都更统一。用生活里的例子理解这就像一条火车每节车厢连接着前厢和后厢。你想在中间拆掉一节车厢只需要把两边的挂钩打开再把前后车厢直接挂上剩下的车厢完全不受影响。这就是链表“插入和删除只动局部指针”的本质。空链表长什么样标准库里头和哨兵结点指向同一个位置整个结构是自洽的。我手撕版本会简化成head和tail都为空指针这样判断empty就是head nullptr。虽然少了一些标准库的优雅但逻辑更直白。2.2 迭代器本质上就是“结点的位置”list的迭代器不能简单理解成一个下标它本质上是指向结点的指针。begin()返回指向第一个有效结点的迭代器end()返回指向最后一个结点之后位置的迭代器。对于双向链表end()最自然的表示是空指针或者是指向哨兵结点。当你执行it时迭代器内部做的事情是把当前指针移动到current-next指向的结点。执行--it时则移动到current-prev。所以链表迭代器的“前进”不是内存地址加一而是顺着指针跳转到下一站。这也是为什么链表迭代器只能单向或双向移动不能it 5直接跳五格因为它没有“下标”的概念。2.3 插入和删除分别让谁失效这是面试常问、实战也极重要的一节。vector插入可能导致所有迭代器失效因为底层数组可能整体搬移删除会使被删位置之后的所有迭代器失效因为元素前移了。list完全反过来。在list中插入一个新结点只是把新结点的prev、next和相邻两个结点的指针改了已经存在的结点地址一个都没变所以任何指向已有元素的迭代器依然有效。删除一个结点时只有指向被删结点的迭代器失效其他迭代器依然有效。这个特性非常宝贵你可以拿着一个迭代器做大量插入删除操作不用担心其他位置的迭代器悄悄“坏掉”。我用一个实际例子说明这个价值。假设你要维护一个有顺序的任务队列某任务执行失败后要把它移到队尾重试其他任务顺序保持不变。用list实现时你先保存每个任务的迭代器失败时直接erase再push_back其他任务迭代器完全不受影响。而用vector就得重建整个索引或者用“惰性标记”绕来绕去。3. list接口实战这些操作和vector差得远3.1 基础增删查push、pop、front、backlist的基础操作和deque更像头尾都能高效操作。push_back、push_front在尾部、头部插入pop_back、pop_front在尾部、头部删除front()、back()分别取首尾元素引用。注意pop系列没有返回值想拿元素得先front()或back()保存一份再pop。这是很多人的第一处不解原因很简单拷贝返回值会导致潜在开销而异常安全也不好处理。std::listint tasks; tasks.push_back(1); tasks.push_front(0); int first tasks.front(); // 0 tasks.pop_front(); // 删除0不返回size()的复杂度在 C11 以后保证是 O(1)早期标准允许 O(n)现在完全不用纠结。empty()用来判空比size() 0更推荐因为有些容器如单链表的size()可能是 O(n) 的empty()永远 O(1)。3.2 insert与erase的位置语义先让迭代器说话list的插入删除都围绕迭代器展开这也是新手最容易不适应的点。insert(pos, value)表示在pos指向的结点之前插入新结点erase(pos)删除pos指向的结点并返回下一个结点的迭代器。删除一片区间可以用erase(first, last)删除[first, last)。如果把begin()到end()传进去相当于清空。没有迭代器时你甚至没法表达“在下标3处插入”这种操作因为链表根本不存在下标。正确姿势是先auto it nums.begin(); std::advance(it, 3);让迭代器走三步再插入。我建议你把所有增删操作都写成“先定位迭代器再做操作”的习惯。这样写出来的代码切换到map、set时也能无缝迁移思路。3.3 splice、sort、uniquelist的独门武器list里有一批成员函数是vector没有的这是它作为链表天然的优势。splice可以把另一个list的一整段结点直接拼接到当前链表整个过程只改指针不复制数据耗时 O(1)。例如把src的全部元素剪切到dst.begin()之前std::listint dst {1, 2}; std::listint src {3, 4}; dst.splice(dst.begin(), src); // dst变为3,4,1,2src变空unique把相邻重复元素移除注意它只处理“相邻重复”所以数据必须先排序才能做到全局去重。sort是链表的归并排序版参数上可以直接传greaterint()实现降序。remove删除所有值等于给定值的元素remove_if则按谓词删除。我用一个“活跃用户淘汰”例子把这些串起来维护一个按活跃度排序的用户ID列表周末把活跃度不到阈值的人全部移除并将前两名活跃用户剪切到队首。用list写出来非常直观代码量比vector小一半还不止。std::listint activeUsers {101, 102, 103, 104, 105}; activeUsers.sort(); // 便于展示unique等操作 activeUsers.unique(); activeUsers.remove_if([](int id) { return id % 2 0; });3.4 一个综合例子任务队列的优先级调整实际开发里list最经典的使用场景就是“需要持有迭代器做位置调整”的队列。下面这段模拟一个简单任务调度器每个任务有一个整数优先级普通任务从队尾进入紧急任务直接插到队首。#include list #include iostream int main() { std::liststd::pairint, std::string tasks; auto normal [](const std::string name) { tasks.push_back({0, name}); }; auto urgent [](const std::string name) { tasks.push_front({1, name}); }; normal(写周报); normal(读文档); urgent(修线上故障); urgent(处理客户投诉); for (auto task : tasks) { std::cout task.second std::endl; } return 0; }输出顺序是“处理客户投诉、修线上故障、写周报、读文档”。用push_front实现紧急插队用push_back实现普通排队这个模型直接可以扩展到后续要讲的deque、优先级队列的思路。4. 手撕list从零实现一个可用的双向链表现在进入正题。这个是整篇内容的灵魂部分也是面试最容易让你现场写代码的考点。我会实现一个MyListT包含结点结构、双向迭代器、常用接口和拷贝控制。4.1 结点设计与基本架子结点用内部结构体表示data存放值prev和next指向相邻结点。为了简化内存和逻辑我采用head指向第一个有效结点、tail指向最后一个有效结点、空链表为空的方案。template typename T class MyList { private: struct Node { T data; Node* prev; Node* next; Node(const T value) : data(value), prev(nullptr), next(nullptr) {} }; Node* head; Node* tail; size_t count; public: MyList() : head(nullptr), tail(nullptr), count(0) {} ~MyList() { clear(); } bool empty() const { return head nullptr; } size_t size() const { return count; } void clear() { Node* cur head; while (cur) { Node* next cur-next; delete cur; cur next; } head tail nullptr; count 0; } };这里clear()是所有析构和弹出操作的地基。你可能会问为什么不直接循环pop_front()因为pop_front()还要维护head、tail、count三个成员而clear()本身只需要关心逐个释放。分离职责后pop_front就能直接调用它。4.2 push_back和push_front先连新结点尾部插入的步骤创建新结点若链表为空则head和tail都指向它否则让tail-next指向新结点新结点的prev指向tail最后更新tail。void push_back(const T value) { Node* node new Node(value); if (tail nullptr) { head tail node; } else { tail-next node; node-prev tail; tail node; } count; } void push_front(const T value) { Node* node new Node(value); if (head nullptr) { head tail node; } else { head-prev node; node-next head; head node; } count; }这段代码的坑在于空链表和非空链表必须分开处理。不少初学者写链表时只考虑“链表非空”的情况一调用push_back在空链表上程序直接崩溃因为tail-next访问了空指针。你在自己实现时所有涉及head或tail的操作都要问一句“如果链表为空这段代码还成立吗”4.3 迭代器实现完成最关键的封装写完结点和基础接口就要让MyList能像标准容器一样用范围 for 遍历。C 要求一个容器拥有begin()和end()且返回的迭代器支持operator*、operator范围 for 才能工作。这里必须定义一个迭代器类。template typename T class MyList { private: template typename U class ListIterator { public: using iterator_category std::bidirectional_iterator_tag; using value_type U; using difference_type std::ptrdiff_t; using pointer U*; using reference U; ListIterator(Node* ptr) : node(ptr) {} reference operator*() const { return node-data; } pointer operator-() const { return node-data; } ListIterator operator() { node node-next; return *this; } ListIterator operator(int) { ListIterator tmp *this; node node-next; return tmp; } ListIterator operator--() { node node-prev; return *this; } ListIterator operator--(int) { ListIterator tmp *this; node node-prev; return tmp; } bool operator(const ListIterator other) const { return node other.node; } bool operator!(const ListIterator other) const { return node ! other.node; } private: Node* node; }; public: using iterator ListIteratorT; using const_iterator ListIteratorconst T; iterator begin() { return iterator(head); } iterator end() { return iterator(nullptr); } const_iterator begin() const { return const_iterator(head); } const_iterator end() const { return const_iterator(nullptr); } };注意end()用空指针nullptr表示当一直走到最后一个结点的next空指针时得到的恰好就是end()。这样写if (it ! myList.end())天然成立。迭代器的五个类型别名不是摆设标准算法库依赖iterator_category判断迭代器类型并选择最优算法比如std::advance会为双向迭代器逐格移动。没有这些别名很多 STL 算法直接编译失败。4.4 insert与erase链表的灵魂操作insert(pos, value)是实现在pos之前插入。实现时需要区分三种情况插入位置在头部pos begin()、链表为空、正常中间插入。为了统一先处理pos nullptr即end()此时等价于push_back。iterator insert(iterator pos, const T value) { if (pos end()) { push_back(value); return iterator(tail); } if (pos begin()) { push_front(value); return iterator(head); } Node* cur pos.node; Node* prevNode cur-prev; Node* node new Node(value); prevNode-next node; node-prev prevNode; node-next cur; cur-prev node; count; return iterator(node); }这里pos.node因为迭代器类里把node设为private而外层类可以访问内层类的私有成员吗答案是C 中外层类不自动拥有访问内层类私有成员的权限必须把外层类声明为友元或者把内层成员设为公开。我前面的写法里Node*是MyList的私有成员而ListIterator又是MyList的私有内部类让MyList访问迭代器的node成员有一个前置条件把friend class MyList;加在ListIterator内部。你写的时候一定记得补上否则编译会报“无法访问私有成员”。erase(pos)返回被删除结点的下一个迭代器这是标准库的约定方便循环删除。iterator erase(iterator pos) { Node* cur pos.node; if (cur nullptr) { return pos; } Node* prevNode cur-prev; Node* nextNode cur-next; if (prevNode nullptr) { head nextNode; } else { prevNode-next nextNode; } if (nextNode nullptr) { tail prevNode; } else { nextNode-prev prevNode; } delete cur; --count; return iterator(nextNode); }为什么erase要返回迭代器而不是void因为调用者在删除一个元素后往往要继续遍历如果没有返回下一个位置你就得在删除前先保存next非常麻烦。标准库在这里做了一个体贴的设计我们手撕时也照做。4.5 析构、拷贝构造与赋值内存安全的最后屏障这是手撕链表时最容易被忽略、却最容易出事的部分。默认的拷贝构造会把head、tail、count逐个复制导致两个对象指向同一串结点析构时二次释放。所以必须写深拷贝。拷贝构造的基础写法先置空所有成员再遍历原链表逐个push_back。MyList(const MyList other) : head(nullptr), tail(nullptr), count(0) { for (const T value : other) { push_back(value); } } MyList operator(const MyList other) { if (this other) { return *this; } clear(); for (const T value : other) { push_back(value); } return *this; }赋值运算符还有一个更高阶的“拷贝交换”写法MyList operator(MyList other) { swap(other); return *this; }它利用传值的临时对象做深拷贝再用swap交换到当前对象天然规避了自赋值问题而且异常安全。缺点是要求swap实现但这里swap很直观void swap(MyList other) noexcept { std::swap(head, other.head); std::swap(tail, other.tail); std::swap(count, other.count); }我建议你先把拷贝构造和赋值运算符的基础版本写稳再去考虑拷贝交换。毕竟手撕的主要目的是理解内存管理不是为了炫技。4.6 补全front、back和pop系列最后补上访问和弹出接口让MyList基本可用。注意front()和back()返回引用这样可以像标准库一样修改元素。T front() { return head-data; } const T front() const { return head-data; } T back() { return tail-data; } const T back() const { return tail-data; } void pop_front() { if (head nullptr) return; Node* next head-next; delete head; head next; if (head nullptr) { tail nullptr; } else { head-prev nullptr; } --count; } void pop_back() { if (tail nullptr) return; Node* prev tail-prev; delete tail; tail prev; if (tail nullptr) { head nullptr; } else { tail-next nullptr; } --count; }pop系列一定要处理“删除最后一个结点后另一个指针也要置空”的边界。删除唯一结点时head和tail都会变成空指针漏掉任何一边后续调用empty()都可能出错。5. 验证、调试与更深一层手写容器值不值5.1 用与std::list一致的接口写测试写完代码不能只是“看着对”要真跑。最直接的测试思路把MyList换成std::list跑同一套操作看行为是否一致。这里给一个参考测试插入、删除、遍历、拷贝构造、赋值五件事全测一遍。#include iostream #include cassert int main() { MyListint lst; lst.push_back(1); lst.push_back(2); lst.push_front(0); assert(lst.front() 0); assert(lst.back() 2); assert(lst.size() 3); auto it lst.begin(); it; // 指向1 lst.insert(it, 99); // 在1之前插入列表变为0,99,1,2 assert(lst.size() 4); it lst.begin(); it; // 指向99 it lst.erase(it); // 删除99 assert(*it 1); assert(lst.size() 3); MyListint copy lst; // 拷贝构造 assert(copy.size() 3); assert(copy.back() 2); MyListint assigned; assigned copy; // 赋值 assigned.pop_back(); assert(assigned.size() 2); assert(copy.size() 3); // 赋值后源对象不受影响 for (int x : lst) { std::cout x ; } std::cout std::endl; return 0; }这个测试覆盖了大多数核心路径。没有测试框架也没关系assert就够了。跑测试时打开地址消毒器AddressSanitizer能帮你把隐性内存错误暴露出来编译加-fsanitizeaddress -g运行后如果出现堆溢出、重复释放、野指针访问会直接报错并指出代码行。5.2 常见坑位自赋值、迭代器悬挂与空指针第一处坑是自赋值。假如你写lst lst;基础版本的赋值运算符先clear()再遍历而other就是当前对象clear()之后源对象已经空了于是得到一个空链表。这就是为什么赋值运算符开头必须有if (this other) return *this;或者用拷贝交换法。第二处坑是迭代器悬挂。erase(it)之后it指向的内存已经被释放任何访问都是未定义行为。我在手撕代码里让erase返回下一个迭代器就是提示你“旧的别用了新的给你”。你如果不注意保存返回值后面it就会在已释放的Node上操作程序连崩两次才能发现问题。第三处坑在空链表上调用front()和back()。我的实现直接head-data空链表时head是空指针访问必然崩溃。标准库对此是未定义行为推荐先判断empty()再访问。很多新手把标准库的“未定义行为”理解成“总是报错”其实不然未定义意味着你可能偶尔正常、偶尔崩这种不确定最折磨人。5.3 内存检查与性能简测手撕完应该怎么验证在 Linux 环境下valgrind --leak-checkfull ./my_test是查内存泄漏的经典手段。输出里如果出现definitely lost说明有new出来的结点没被删除通常是你漏了析构函数或者clear()逻辑不完整。如果出现Invalid read/write则说明有野指针或者越界访问。我自己的经验是写完手撕链表先跑一次 valgrind比在编辑器里盯十遍代码都有效。性能上不用过度期待手写链表超过标准库。标准库版本经过大量优化还有内存分配器、哨兵结点、异常安全等设计手撕版本能保持语义正确就已经不错了。你如果真的需要高性能链表优先用标准库但如果你想理解它为什么快、为什么安全手撕这个简化版就是最好的学习路径。5.4 手写容器的真正价值不是替代是理解有人会质疑现在工程上几乎不自己写链表为什么还要花力气手撕我的体会是手写一遍容器能带来的收益有三个层次。第一层是面试刚需现场让你实现链表时你至少不会被边界条件难倒。第二层是读源码能力当你再看 STL 或开源代码里那些封装精密的容器时一眼就能认出“哦这里是在处理头尾边界”“这个迭代器别名是给算法用的”。第三层最宝贵你真正理解了“昂贵”和“廉价”在哪里。比如vector的随机访问为什么便宜、list的连续大量小对象为什么内存碎片严重这些经验靠背结论永远学不牢亲手敲一遍才内化得彻底。我个人建议你在手撕完这份代码后自己尝试添加两个扩展实现const_iterator完整版、或者把清除逻辑改成“先断链再释放”的细节优化。每加一个功能你都会更深刻地理解链表和 STL 容器设计者的取舍。6. 手撕之后我剩下的几个小提醒如果你按前面的代码走了一遍现在应该已经拥有一个能编译、能跑、能通过基础测试的MyList。还剩几件事想单独拎出来说。第一写容器时不要把inline和模板实现分开到不同的.h和.cpp。模板只有在实例化时才知道具体类型所以你的MyList需要把实现全部写在头文件里。这个坑很多初学者踩过头文件里放声明.cpp里放实现链接时报一堆未定义引用错误。记住一个口诀模板实现即定义都放头文件。第二ListIterator的operator--在begin()上调用是标准库允许的未定义行为但在手写版本里它会让node变成head-prev也就是nullptr这不会立刻崩但之后你把它当合法迭代器用就会出问题。在代码里加注释提醒自己不要在begin()之前做--。第三如果以后你要给MyList加上“在任意位置连续插入 N 个值”的接口构造结点的参数要使用std::initializer_list还是可变模板这些是进阶话题。但万变不离其宗任何批量操作本质都是循环调用你已经写好的insert或push_back只要边界条件和指针更新正确上层怎么装饰都不会触碰底层核心。最后分享一个我自己刚学链表时的愚蠢错误。我把head和tail的更新写反了导致push_back后tail没更新back()一直返回旧值。调试了一整晚才发现是顺序问题。链表代码最重要的不是“会写”而是“时刻清楚每个指针指向哪里”。画图永远是调试链表的最快方式没有之一。遇到指针发懵时别硬看代码拿笔画一遍结点和箭头的走动立刻茅塞顿开。