如果你跟我一样，学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::list<int> 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::list<int> tasks; tasks.push_back(1); tasks.push_front(0); int first = tasks.front(); // 0 tasks.pop_front(); // 删除0，不返回size()的复杂度在 C++11 以后保证是 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、unique：list的独门武器list里有一批成员函数是vector没有的，这是它作为链表天然的优势。splice可以把另一个list的一整段结点直接拼接到当前链表，整个过程只改指针，不复制数据，耗时 O(1)。例如把src的全部元素剪切到dst.begin()之前：std::list<int> dst = {1, 2}; std::list<int> src = {3, 4}; dst.splice(dst.begin(), src); // dst变为3,4,1,2，src变空unique把相邻重复元素移除，注意它只处理“相邻重复”，所以数据必须先排序才能做到全局去重。sort是链表的归并排序版，参数上可以直接传greater<int>()实现降序。remove删除所有值等于给定值的元素，remove_if则按谓词删除。我用一个“活跃用户淘汰”例子把这些串起来：维护一个按活跃度排序的用户ID列表，周末把活跃度不到阈值的人全部移除，并将前两名活跃用户剪切到队首。用list写出来非常直观，代码量比vector小一半还不止。std::list<int> 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::list<std::pair<int, 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：从零实现一个可用的双向链表现在进入正题。这个是整篇内容的灵魂部分，也是面试最容易让你现场写代码的考点。我会实现一个MyList<T>，包含结点结构、双向迭代器、常用接口和拷贝控制。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 = ListIterator<T>; using const_iterator = ListIterator<const 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() { MyList<int> 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); MyList<int> copy = lst; // 拷贝构造 assert(copy.size() == 3); assert(copy.back() == 2); MyList<int> 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）能帮你把隐性内存错误暴露出来：编译加-fsanitize=address -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-check=full ./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()一直返回旧值。调试了一整晚才发现是顺序问题。链表代码最重要的不是“会写”，而是“时刻清楚每个指针指向哪里”。画图永远是调试链表的最快方式，没有之一。遇到指针发懵时，别硬看代码，拿笔画一遍结点和箭头的走动，立刻茅塞顿开。
如果你跟我一样，学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::list<int> 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::list<int> tasks; tasks.push_back(1); tasks.push_front(0); int first = tasks.front(); // 0 tasks.pop_front(); // 删除0，不返回size()的复杂度在 C++11 以后保证是 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、unique：list的独门武器list里有一批成员函数是vector没有的，这是它作为链表天然的优势。splice可以把另一个list的一整段结点直接拼接到当前链表，整个过程只改指针，不复制数据，耗时 O(1)。例如把src的全部元素剪切到dst.begin()之前：std::list<int> dst = {1, 2}; std::list<int> src = {3, 4}; dst.splice(dst.begin(), src); // dst变为3,4,1,2，src变空unique把相邻重复元素移除，注意它只处理“相邻重复”，所以数据必须先排序才能做到全局去重。sort是链表的归并排序版，参数上可以直接传greater<int>()实现降序。remove删除所有值等于给定值的元素，remove_if则按谓词删除。我用一个“活跃用户淘汰”例子把这些串起来：维护一个按活跃度排序的用户ID列表，周末把活跃度不到阈值的人全部移除，并将前两名活跃用户剪切到队首。用list写出来非常直观，代码量比vector小一半还不止。std::list<int> 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::list<std::pair<int, 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：从零实现一个可用的双向链表现在进入正题。这个是整篇内容的灵魂部分，也是面试最容易让你现场写代码的考点。我会实现一个MyList<T>，包含结点结构、双向迭代器、常用接口和拷贝控制。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 = ListIterator<T>; using const_iterator = ListIterator<const 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() { MyList<int> 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); MyList<int> copy = lst; // 拷贝构造 assert(copy.size() == 3); assert(copy.back() == 2); MyList<int> 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）能帮你把隐性内存错误暴露出来：编译加-fsanitize=address -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-check=full ./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()一直返回旧值。调试了一整晚才发现是顺序问题。链表代码最重要的不是“会写”，而是“时刻清楚每个指针指向哪里”。画图永远是调试链表的最快方式，没有之一。遇到指针发懵时，别硬看代码，拿笔画一遍结点和箭头的走动，立刻茅塞顿开。