前言std::list是标准库里的双向链表容器。它的接口看起来和std::vector差不多push_back、insert、erase、迭代器遍历。但底层完全是另一套结构每个元素单独分配一个节点节点之间用前后指针串起来容器本身只持有头尾的入口。理解这套结构最好的方式是照着标准容器的接口自己实现一个简化版。自己实现一遍能回答几个平时容易含糊的问题为什么list的迭代器不能像vector那样用裸指针为什么insert不会让已有迭代器失效而erase只让被删的那个失效为什么list明明「插入 O(1)」遍历却不快为什么标准要求std::list的size()在 C11 之后必须是 O(1)需要先说明本文实现的边界为了把篇幅集中在节点、迭代器和指针操作上这个版本省略了const_iterator、allocator、异常安全的全套保证、splice/merge/sort等成员也不追求与std::list的接口完全一致。它是一个教学实现用来观察机制不应当直接替换标准容器。代码以 C17 为基准本机没有 C/C 工具链未经过编译和运行正确性依据标准语义与逐行推演。一、节点与哨兵循环双向链表双向链表最直接的写法是让头指针和尾指针分别指向首尾节点空链表时两者都为nullptr。这种写法在每个操作里都要处理「链表为空」「只有一个节点」「操作的是首节点」「操作的是尾节点」等分支代码很快变得臃肿。标准实现通常采用带哨兵的循环链表容器内嵌一个不存数据的头节点sentinel它的next指向第一个元素prev指向最后一个元素第一个元素的prev和最后一个元素的next都指回哨兵。空链表时哨兵的next和prev都指向自己。这样一来「首」「尾」「空」都不再是特殊情况——插入和删除只需要改四个指针不需要判空。节点的类型设计有一个细节哨兵不需要存储T如果让哨兵也是Node就要求T可默认构造这对ListNoDefaultCtor是硬性限制。解决办法是把指针部分抽成基类// 适用于 C17struct NodeBase {NodeBase* prev nullptr;NodeBase* next nullptr;};template typename Tstruct Node : NodeBase {T value;explicit Node(const T v) : value(v) {}explicit Node(T v) : value(std::move(v)) {}};NodeBase只含两个指针哨兵用NodeBase类型真正的元素节点是Node。从NodeBase*转回Node*用static_cast向下转换前提是这个指针确实指向Node而不是哨兵——解引用end()本来就是未定义行为这条前提自然成立。二、迭代器为什么不能是裸指针std::vector的迭代器在多数实现里就是裸指针因为元素连续存放就是地址加一个元素大小。list不行节点是分散分配的必须沿着next指针跳转*it必须先找到节点再取value。因此迭代器要封装一个NodeBase*并重载解引用、自增、自减和比较运算符。// 适用于 C17class iterator {public:explicit iterator(NodeBase* p nullptr) : p_(p) {}T operator*() const { return static_castNode*(p_)-value; }T* operator-() const { return static_castNode*(p_)-value; }iterator operator() { p_ p_-next; return *this; }iterator operator(int) { iterator old(*this); (*this); return old; }iterator operator--() { p_ p_-prev; return *this; }iterator operator--(int) { iterator old(*this); --(*this); return old; }bool operator(const iterator rhs) const { return p_ rhs.p_; }bool operator!(const iterator rhs) const { return p_ ! rhs.p_; }NodeBase* node() const { return p_; }private:NodeBase* p_;};几个设计点。第一operator*返回T而不是T否则*it x改的是临时副本operator-返回T*让it-member能工作。第二后置必须返回旧值的副本所以先拷贝再前进前置返回引用避免多余拷贝。第三node()暴露内部指针是给容器用的insert/erase需要标准实现通常用友元这里用公有访问器换取代码简短。这个迭代器满足双向迭代器的基本要求可复制、可前后移动、可比较、可解引用。它不满足随机访问迭代器的要求——不能it n不能比较大小这也是std::sort不能直接用于list的原因std::sort要求随机访问迭代器编译期就会拒绝。end()返回的是指向哨兵的迭代器。对end()解引用是未定义行为对end()执行--是合法的会得到最后一个元素空链表时--end()仍是end()再解引用同样是 UB。三、插入与删除四个指针的顺序在pos之前插入一个节点需要改四个指针新节点的prev/next、前驱的next、pos的prev。顺序很重要先把新节点自己的指针设好再让它接入链表这样即使中间没有异常也不会出现链表断裂的瞬间如果先改前驱的next再设新节点的字段任何中断都会留下一个指向未初始化节点的链。// 适用于 C17iterator insert(iterator pos, const T value) {NodeBase* cur pos.node();Node* node new Node(value); // 先分配失败则链表不变node-prev cur-prev;node-next cur;cur-prev-next node;cur-prev node;size_;return iterator(node);}erase则相反先把前后节点接起来再释放当前节点最后返回下一个位置。返回iterator而不是void是为了支持it list.erase(it)这种遍历中删除的写法。// 适用于 C17iterator erase(iterator pos) {NodeBase* cur pos.node();NodeBase* next cur-next;cur-prev-next cur-next;cur-next-prev cur-prev;delete static_castNode*(cur);--size_;return iterator(next);}insert不使任何已有迭代器失效因为节点地址没有变只是指针被重新连接erase只使指向被删节点的迭代器失效其他迭代器仍然有效。这与vector形成鲜明对比vector一旦扩容所有迭代器、指针、引用全部失效。选择容器时这条规则往往比「插入是 O(1) 还是 O(n)」更影响正确性。四、特殊成员函数析构、拷贝与移动链表的析构必须逐个delete节点不能只释放哨兵。clear()负责这件事并在结束后把哨兵恢复成自环// 适用于 C17void clear() noexcept {NodeBase* cur head_.next;while (cur ! head_) {NodeBase* next cur-next;delete static_castNode*(cur);cur next;}head_.next head_;head_.prev head_;size_ 0;}拷贝构造要深拷贝如果只复制哨兵指针两个List会共享同一串节点析构时就会重复释放double free这是最危险的错误之一。移动构造则可以「偷」把源链表的整串节点接到目标哨兵上再把源哨兵恢复为空全程不发生元素拷贝。下面的完整实现把节点、迭代器、插入删除和特殊成员函数放在一起。为了异常安全拷贝构造先在一个临时List上构建成功后再接管如果中途new抛异常临时对象的析构会清理已分配的节点。// 适用于 C17#include cstddef#include iostream#include utilitytemplate typename Tclass List {struct NodeBase {NodeBase* prev nullptr;NodeBase* next nullptr;};struct Node : NodeBase {T value;explicit Node(const T v) : value(v) {}explicit Node(T v) : value(std::move(v)) {}};public:class iterator {public:explicit iterator(NodeBase* p nullptr) : p_(p) {}T operator*() const { return static_castNode*(p_)-value; }T* operator-() const { return static_castNode*(p_)-value; }iterator operator() { p_ p_-next; return *this; }iterator operator(int) { iterator old(*this); (*this); return old; }iterator operator--() { p_ p_-prev; return *this; }iterator operator--(int) { iterator old(*this); --(*this); return old; }bool operator(const iterator rhs) const { return p_ rhs.p_; }bool operator!(const iterator rhs) const { return p_ ! rhs.p_; }NodeBase* node() const { return p_; }private:NodeBase* p_;};List() {head_.next head_;head_.prev head_;}~List() { clear(); }List(const List other) : List() {List tmp;for (NodeBase* p other.head_.next; p ! other.head_; p p-next) {tmp.push_back(static_castNode*(p)-value);}steal(tmp);}List operator(const List other) {if (this ! other) {List tmp(other); // 先完成拷贝失败则 *this 不变clear();steal(tmp);}return *this;}List(List other) noexcept : List() {steal(other);}List operator(List other) noexcept {if (this ! other) {clear();steal(other);}return *this;}iterator begin() { return iterator(head_.next); }iterator end() { return iterator(head_); }bool empty() const { return head_.next head_; }std::size_t size() const { return size_; }T front() { return static_castNode*(head_.next)-value; }const T front() const { return static_castNode*(head_.next)-value; }T back() { return static_castNode*(head_.prev)-value; }const T back() const { return static_castNode*(head_.prev)-value; }void push_back(const T v) { insert(end(), v); }void push_back(T v) { insert(end(), std::move(v)); }void push_front(const T v) { insert(begin(), v); }iterator insert(iterator pos, const T value) {NodeBase* cur pos.node();Node* node new Node(value);node-prev cur-prev;node-next cur;cur-prev-next node;cur-prev node;size_;return iterator(node);}iterator insert(iterator pos, T value) {NodeBase* cur pos.node();Node* node new Node(std::move(value));node-prev cur-prev;node-next cur;cur-prev-next node;cur-prev node;size_;return iterator(node);}iterator erase(iterator pos) {NodeBase* cur pos.node();NodeBase* next cur-next;cur-prev-next cur-next;cur-next-prev cur-prev;delete static_castNode*(cur);--size_;return iterator(next);}void clear() noexcept {NodeBase* cur head_.next;while (cur ! head_) {NodeBase* next cur-next;delete static_castNode*(cur);cur next;}head_.next head_;head_.prev head_;size_ 0;}private:// 把 other 的整串节点接到空的 *this 上other 变为空void steal(List other) noexcept {if (other.head_.next other.head_) return;NodeBase* first other.head_.next;NodeBase* last other.head_.prev;first-prev head_;last-next head_;head_.next first;head_.prev last;size_ other.size_;other.head_.next other.head_;other.head_.prev other.head_;other.size_ 0;}NodeBase head_;std::size_t size_ 0;};int main() {Listint a;a.push_back(1);a.push_back(2);a.push_back(3);a.push_front(0);auto it a.begin();it;a.insert(it, 99); // 在 1 之后插入for (int v : a) {std::cout v ;}std::cout \n;Listint b a; // 深拷贝b.erase(b.begin());std::cout b.size() a.size() \n;Listint c std::move(b); // 移动b 变为空std::cout c.size() b.size() \n;c.clear();std::cout c.empty() \n;return 0;}steal的前提是目标为空调用点都满足移动构造时目标刚构造完移动赋值时先clear()。steal里先判断源是否为空避免把哨兵当成节点接到目标上。常见坑点❌ 拷贝构造只复制头指针导致两个链表共享节点。✅ 逐个节点深拷贝析构时各自释放避免 double free。❌ 让哨兵也使用Node类型要求T可默认构造。✅ 把指针部分拆成NodeBase哨兵只要NodeBase。❌erase后继续使用指向被删节点的迭代器。✅erase只保证其他迭代器有效用返回值接收下一个位置。❌ 认为list的insert会让迭代器失效。✅ 节点地址不变插入不影响已有迭代器失效只发生在被删节点上。❌ 对list调用std::sort。✅ 它要求随机访问迭代器编译不通过用成员sort()本实现未提供。❌ 在析构函数里只delete哨兵或忘记恢复哨兵的自环。✅ 逐个释放节点再把head_.next/head_.prev指回自己。❌ 移动之后继续读取源链表的元素。✅ 被移动对象处于有效但未指定状态本实现把它清空但不要依赖具体内容。❌ 解引用end()或对空链表取front()/back()。✅ 这些操作是 UB使用前用empty()判断。总结主题std::list的做法本实现的对应存储分散的节点双向指针NodeBaseNode边界哨兵节点空表自环内嵌head_迭代器类类型双向移动封装NodeBase*插入改四个指针O(1)insert先分配后连接删除先摘链再释放返回下一个erase失效规则插入不失效删除只失效被删者同左拷贝/移动深拷贝 / 偷节点临时对象构建 steal与 vector 对比插入稳定但缓存不友好遍历需逐节点跳转list的核心不是「链表」两个字而是哨兵带来的边界统一、迭代器对指针的封装以及插入删除时那四个指针的固定顺序。把这三件事写对size、拷贝、移动都只是在这套结构上做加减法。真正使用时仍应优先考虑std::vector除非确实需要「插入不失效」或频繁在中间增删否则链表的缓存局部性劣势往往更明显。
