C++ STL 完整入门笔记[6]:list 底层源码手写剖析：双向链表与迭代器设计全解

前言std::list是 STL 中典型双向循环链表容器和 vector 连续数组底层完全不同vector 随机访问 O (1)、中间插入删除 O (n)list 不支持随机访问但任意位置插入、删除仅 O (1)。本文结合手写简易版 list 源码拆解底层结构、迭代器区分、核心接口insert/erase/push_back、const 迭代器底层设计难点把手写 list 的所有核心知识点一次性梳理清楚。一、list 底层存储结构带哨兵头结点的双向循环链表1. 节点结构体_list_nodelist 每一个存储数据的节点都包含三部分数据、前驱指针、后继指针templateclass T struct _list_node { T _data; _list_node* _next; _list_node* _prev; };2. list 类本体哨兵头结点_headlist 内部只维护一个哨兵头结点_head链表形成双向循环_head-_next指向链表第一个有效节点begin()_head-_prev指向链表最后一个有效节点end()返回迭代器指向哨兵头结点本身哨兵节点优势链表为空 / 非空时insert、erase逻辑完全统一无需单独处理空链表边界。templateclass T class list { public: typedef _list_nodeT Node; private: Node* _head; // 哨兵头结点 };二、list 迭代器深度拆解普通迭代器 vs const 迭代器list 迭代器不是原生指针是封装链表节点指针的类因为链表节点不连续不能直接it跳转下一个元素。1. 迭代器模板设计核心难点迭代器模板接收两个模板参数T存储数据类型Ref引用类型普通迭代器传Tconst 迭代器传const Ttemplateclass T, class Ref struct _list_iterator { typedef _list_nodeT Node; typedef _list_iteratorT, Ref Self; Node* _node; // 构造绑定链表节点指针 _list_iterator(Node* node) :_node(node) {} // 解引用 *it Ref operator*() { return _node-_data; } // 箭头访问 it-xxx T* operator-() { return _node-_data; } // 前置 Self operator() { _node _node-_next; return *this; } // 前置-- Self operator--() { _node _node-_prev; return *this; } // 迭代器比较 bool operator!(const Self other) const { return _node ! other._node; } };2. 两种迭代器 typedef 区分在 list 类内部通过上面迭代器模板实例化出两种迭代器templateclass T class list { public: typedef _list_iteratorT, T iterator; typedef _list_iteratorT, const T const_iterator; // ... private: Node* _head; };关键区别普通迭代器 iteratorRefT*it返回数据引用可修改链表节点数据listint lt; listint::iterator it lt.begin(); *it 100; // 合法可修改const 迭代器 const_iteratorRefconst T*it返回 const 引用禁止修改节点数据void print(const listint lt) { listint::const_iterator it lt.begin(); // *it 100; 报错const迭代器不能修改数据 cout *it; }3. begin () /end () 接口实现// 普通迭代器begin iterator begin() { return iterator(_head-_next); } // const迭代器beginconst对象调用 const_iterator begin() const { return const_iterator(_head-_next); } // end永远返回哨兵头结点 iterator end() { return iterator(_head); } const_iterator end() const { return const_iterator(_head); }三、核心接口源码实现与图解1. 构造函数、析构函数构造初始化哨兵循环链表list() { _head new Node; _head-_next _head; _head-_prev _head; }析构循环销毁所有节点释放哨兵~list() { iterator it begin(); while(it ! end()) { it erase(it); // erase自动返回下一个有效迭代器 } delete _head; _head nullptr; }2. insert 任意位置插入O (1)逻辑图解pos 迭代器指向当前节点 cur新建 newnode 插入 cur 前面保存 cur 前驱 prev cur-_prevprev 后继指向 newnodenewnode 前驱指向 prev后继指向 curcur 前驱指向 newnodevoid insert(iterator pos, const T val) { Node* cur pos._node; Node* newnode new Node; newnode-_data val; Node* prev cur-_prev; prev-_next newnode; newnode-_prev prev; newnode-_next cur; cur-_prev newnode; }3. erase 删除指定迭代器位置O (1)逻辑图解删除 pos 指向 cur 节点连接前后节点返回下一个有效迭代器保存 cur 前驱 prev、后继 nextprev 后继改为 nextnext 前驱改为 prev释放 cur 节点内存返回迭代器绑定 next 节点iterator erase(iterator pos) { Node* cur pos._node; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; return iterator(next); }4. push_back /push_front 复用 insert底层直接调用 insert简化代码// 尾插在end()哨兵前插入 void push_back(const T x) { insert(end(), x); } // 头插在begin()第一个元素前插入 void push_front(const T x) { insert(begin(), x); }四、手写 list 核心易错点总结迭代器不能复用原生指针vector 迭代器本质是T*原生指针list 节点不连续必须封装节点指针实现迭代器。const 迭代器不能修改数据迭代器模板通过第二个模板参数区分引用类型const 迭代器解引用返回 const 引用拦截数据修改。哨兵头结点统一边界逻辑无论链表空还是有数据insert、erase 无需额外判空空链表begin()end()。erase 迭代器失效问题erase 传入的 pos 迭代器失效但返回值是下一个有效迭代器vector erase 会导致后续所有迭代器失效list 仅被删除迭代器失效。list 不支持随机访问没有重载[]运算符不能lt[0]访问元素遍历只能依靠迭代器循环。五、list vs vector 底层对比特性std::list双向链表std::vector连续数组底层存储离散节点双向循环链表连续堆内存数组随机访问 []不支持O (n) 遍历支持O (1)头部 / 中间插入删除O (1)仅修改指针O (n)需要挪动元素迭代器失效仅被 erase 的迭代器失效erase 后所有后续迭代器失效内存开销每个节点存 prev/next 双指针开销大仅存储数据内存紧凑六、完整简易版 list 全部源码#includeiostream using namespace std; templateclass T struct _list_node { T _data; _list_node* _next; _list_node* _prev; }; templateclass T, class Ref struct _list_iterator { typedef _list_nodeT Node; typedef _list_iteratorT, Ref Self; Node* _node; _list_iterator(Node* node) :_node(node) {} Ref operator*() { return _node-_data; } T* operator-() { return _node-_data; } Self operator() { _node _node-_next; return *this; } Self operator--() { _node _node-_prev; return *this; } bool operator!(const Self other) const { return _node ! other._node; } }; templateclass T class list { public: typedef _list_nodeT Node; typedef _list_iteratorT, T iterator; typedef _list_iteratorT, const T const_iterator; list() { _head new Node; _head-_next _head; _head-_prev _head; } ~list() { iterator it begin(); while(it ! end()) { it erase(it); } delete _head; _head nullptr; } iterator begin() { return iterator(_head-_next); } const_iterator begin() const { return const_iterator(_head-_next); } iterator end() { return iterator(_head); } const_iterator end() const { return const_iterator(_head); } void insert(iterator pos, const T val) { Node* cur pos._node; Node* newnode new Node; newnode-_data val; Node* prev cur-_prev; prev-_next newnode; newnode-_prev prev; newnode-_next cur; cur-_prev newnode; } iterator erase(iterator pos) { Node* cur pos._node; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; return iterator(next); } void push_back(const T x) { insert(end(), x); } void push_front(const T x) { insert(begin(), x); } }; // 测试打印函数 void print(const listint lt) { listint::const_iterator it lt.begin(); while(it ! lt.end()) { cout *it ; it; } cout endl; } int main() { listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_front(0); print(lt); listint::iterator it lt.begin(); it; lt.erase(it); print(lt); return 0; }结语手写 list 是吃透 STL 容器底层的经典案例重点掌握双向循环链表哨兵设计、模板迭代器区分普通 /const、insert/erase 指针修改逻辑三大核心。 对比 vector 底层实现后可以根据业务场景灵活选择容器频繁中间插入删除选 list随机访问、尾部扩容选 vector。