STL list：双向带头循环链表，原理与模拟，三层封装一次讲透

哈喽大家好，STL 系列接着更。前面聊完 string、容器适配器和模板进阶，这篇咱们手写一个list，也就是标准库里的双向带头循环链表。这篇也是想和大家一起见识一下封装的设计美。

list 看着简单，难点全在"迭代器怎么封装"上——为什么不能直接拿指针当迭代器？为什么一套模板能同时变出普通迭代器和 const 迭代器？这篇把三层结构拆开揉碎，配一份能直接编译的实现，还请放心食用~

目录

• 一、list 是什么：物理不连续的双向循环链表
• 二、三层封装总览
• 三、第二层：list_node 节点
• 四、第三层：迭代器封装（本篇重点）
  • 4.1 为什么非要封装一个迭代器类
  • 4.2 一套模板变出 iterator 和 const_iterator
  • 4.3 运算符重载逐个讲
• 五、第一层：list 类主体
  • 5.1 带头循环：empty_init 让头节点自环
  • 5.2 begin 与 end：左闭右开
  • 5.3 insert：四根指针重新连线
  • 5.4 erase：摘链并返回下一个位置
  • 5.5 头尾增删：全部复用 insert / erase
  • 5.6 构造、拷贝、clear 与析构
• 六、完整可编译实现
• 七、list 的性能特点与适用场景
• 八、总结

一、list 是什么：物理不连续的双向循环链表

std::list的底层就是一条双向带头循环链表：

• 双向：每个节点同时存前驱prev和后继next，前后都能走；
• 带头：额外设一个不存有效数据的"哨兵头节点"，让空链表和非空链表的插入删除逻辑统一；
• 循环：尾节点的 next 回头指向头，头节点的 prev 指向尾，首尾相接成环。

它和 vector 最大的区别是：物理空间不连续，节点靠指针彼此串联。这个特点直接决定了为什么需要"迭代器封装"，也是下一节的引子。

二、三层封装总览

手写 list 不是一坨代码，而是清晰的三层结构：

为什么要把迭代器单独抽成一层？因为链表物理不连续，用户不应该直接面对裸指针，而应该像用 vector 一样，写++it、*it就能遍历。这层封装把"指针的走法"翻译成"符合直觉的操作"。

三、第二层：list_node 节点

节点很简单，存一份数据和两个指针：

template<classT>structlist_node{T _data;list_node<T>*_next;list_node<T>*_prev;list_node(constT&data=T()):_data(data),_next(nullptr),_prev(nullptr){}};

构造函数给data一个缺省值T()，next、prev先置空，等插入时再由insert负责连指针。

四、第三层：迭代器封装（本篇重点）

4.1 为什么非要封装一个迭代器类

链表物理不连续，节点和节点之间隔着不知道多远的内存。但我们使用时主观上希望：

• 写++it就能走到下一个节点（而不是手动写it = it->_next）；
• 写*it就能只拿到节点里的data（而不是面对data/prev/next三个成员）；
• 写it1 != it2就能比较两个迭代器是否指向同一节点。

这些"符合直觉"的操作，本质都是对运算符做重载。而最适合承载这些重载的，就是迭代器类本身——它内部包着一个节点指针，对外只暴露优雅的操作。

4.2 一套模板变出 iterator 和 const_iterator

新手容易犯的错：分别写list_iterator（可读可写）和const_list_iterator（只读）两个类，结果两者除了"引用/指针是不是 const"之外几乎一模一样，重复劳动。

STL 源码的做法是：用三个模板参数，一套类同时出两种迭代器：

template<classT,classRef,classPtr>structlist_iterator{typedeflist_node<T>Node;typedeflist_iterator<T,Ref,Ptr>Self;Node*_node;list_iterator(Node*node):_node(node){}// Ref 决定解引用拿到的是 T& 还是 const T&Refoperator*(){return_node->_data;}// Ptr 决定箭头返回的是 T* 还是 const T*Ptroperator->(){return&_node->_data;}// ... 其余重载见下文};

然后在 list 里这样别名化：

typedeflist_iterator<T,T&,T*>iterator;typedeflist_iterator<T,constT&,constT*>const_iterator;

• 普通迭代器传Ref = T&、Ptr = T*，解引用可读写；
• const 迭代器传Ref = const T&、Ptr = const T*，只能读。

这就是模板"只靠传参类型不同就复用同一套代码"的典型魅力，也是源码里青睐的写法，避免维护两个高度雷同的类。

4.3 运算符重载逐个讲

前置 ++ / –（走一格，返回自身引用）：

Self&operator++(){_node=_node->_next;// 走到后继return*this;}Self&operator--(){_node=_node->_prev;// 走回前驱return*this;}

后置 ++ / –（带int形参区分，先保存旧值再走，返回旧值）：

Selfoperator++(int){Selftmp(*this);// 保存修改前的自己_node=_node->_next;returntmp;// 返回旧位置}Selfoperator--(int){Selftmp(*this);_node=_node->_prev;returntmp;}

相等比较（比较底层是不是同一个节点）：

booloperator!=(constSelf&s)const{return_node!=s._node;}booloperator==(constSelf&s)const{return_node==s._node;}

到这里，while (it != lt.end()) { cout << *it; ++it; }这种写法就成立了，用户完全感觉不到背后是链表指针。

五、第一层：list 类主体

5.1 带头循环：empty_init 让头节点自环

先准备一个私有初始化函数，创建头节点并让它的prev、next都指向自己（空环）：

voidempty_init(){_head=newNode;_head->_prev=_head;_head->_next=_head;_size=0;}

空链表时头节点自己接自己成环，这样后面任何插入删除都不用单独判断"是不是空"，逻辑统一。

5.2 begin 与 end：左闭右开

iteratorbegin(){returniterator(_head->_next);// 第一个有效节点}iteratorend(){returniterator(_head);// 哨兵头节点，尾后位置}

和标准库一致，区间是[begin, end)：begin()指向第一个有效节点，end()指向头节点本身（尾后），遍历到end()就停。

5.3 insert：四根指针重新连线

在pos前面插入新节点，经典四步改指针：

iteratorinsert(iterator pos,constT&x){Node*cur=pos._node;Node*prev=cur->_prev;Node*newnode=newNode(x);// 新节点双向连到 prev 和 curnewnode->_prev=prev;newnode->_next=cur;// 两边回头连新节点prev->_next=newnode;cur->_prev=newnode;++_size;returniterator(newnode);}

顺序不能乱：先把新节点挂好，再改两边的指针，否则容易断链。

5.4 erase：摘链并返回下一个位置

删除pos节点，把它的前驱和后继直接接起来，再释放：

iteratorerase(iterator pos){Node*cur=pos._node;Node*prev=cur->_prev;Node*next=cur->_next;prev->_next=next;next->_prev=prev;deletecur;--_size;returniterator(next);// 返回下一个节点，设计更优}

返回下一个节点的迭代器是个重要设计：这样在边遍历边删除时，不用自己先保存++it，直接接收返回值即可，避免迭代器失效问题。

5.5 头尾增删：全部复用 insert / erase

有了 insert 和 erase，头尾操作就是套壳：

voidpush_back(constT&x){insert(end(),x);}// 尾插 = 插到 end() 前voidpush_front(constT&x){insert(begin(),x);}// 头插 = 插到 begin() 前voidpop_back(){erase(--end());}// 尾删 = 删最后一个有效节点voidpop_front(){erase(begin());}// 头删 = 删第一个有效节点

把通用逻辑收敛到 insert/erase，外面只做位置包装，代码干净不容易错。

5.6 构造、拷贝、clear 与析构

// 默认构造list(){empty_init();}// initializer_list 构造，支持 list<int> lt = {1,2,3};list(initializer_list<T>il){empty_init();for(autoe:il)push_back(e);}// 拷贝构造：建新空环，再逐个尾插复制list(constlist<T>&lt){empty_init();for(auto&e:lt)push_back(e);}// 清空有效节点（保留头节点）voidclear(){iterator it=begin();while(it!=end())it=erase(it);}// 析构：先 clear 再删头节点~list(){clear();delete_head;_head=nullptr;}

注意：拷贝构造不能直接复制_head指针，否则两个对象指向同一条链表，析构会二次释放。必须重新建节点逐个拷贝。

六、完整可编译实现

把上面拼起来，就是一份精简但完整的手写 list：

#pragmaonce#include<assert.h>#include<initializer_list>#include<utility>namespaceDongKes{template<classT>structlist_node{T _data;list_node<T>*_next;list_node<T>*_prev;list_node(constT&data=T()):_data(data),_next(nullptr),_prev(nullptr){}};// 三参数模板：一套出 iterator 与 const_iteratortemplate<classT,classRef,classPtr>structlist_iterator{typedeflist_node<T>Node;typedeflist_iterator<T,Ref,Ptr>Self;Node*_node;list_iterator(Node*node):_node(node){}Refoperator*(){return_node->_data;}Ptroperator->(){return&_node->_data;}Self&operator++(){_node=_node->_next;return*this;}Self&operator--(){_node=_node->_prev;return*this;}Selfoperator++(int){Selftmp(*this);_node=_node->_next;returntmp;}Selfoperator--(int){Selftmp(*this);_node=_node->_prev;returntmp;}booloperator!=(constSelf&s)const{return_node!=s._node;}booloperator==(constSelf&s)const{return_node==s._node;}};template<classT>classlist{typedeflist_node<T>Node;public:typedeflist_iterator<T,T&,T*>iterator;typedeflist_iterator<T,constT&,constT*>const_iterator;list(){empty_init();}list(initializer_list<T>il){empty_init();for(autoe:il)push_back(e);}list(constlist<T>&lt){empty_init();for(auto&e:lt)push_back(e);}~list(){clear();delete_head;_head=nullptr;}voidclear(){iterator it=begin();while(it!=end())it=erase(it);}iteratorbegin(){returniterator(_head->_next);}iteratorend(){returniterator(_head);}iteratorinsert(iterator pos,constT&x){Node*cur=pos._node;Node*prev=cur->_prev;Node*newnode=newNode(x);newnode->_prev=prev;newnode->_next=cur;prev->_next=newnode;cur->_prev=newnode;++_size;returniterator(newnode);}iteratorerase(iterator pos){assert(_size>0);Node*cur=pos._node;Node*prev=cur->_prev;Node*next=cur->_next;prev->_next=next;next->_prev=prev;deletecur;--_size;returniterator(next);}voidpush_back(constT&x){insert(end(),x);}voidpush_front(constT&x){insert(begin(),x);}voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}T&front(){return_head->_next->_data;}T&back(){return_head->_prev->_data;}size_tsize()const{return_size;}boolempty()const{return_size==0;}private:voidempty_init(){_head=newNode;_head->_prev=_head;_head->_next=_head;_size=0;}Node*_head;size_t _size=0;};}

测试代码：

#include<iostream>#include"list"usingnamespacestd;intmain(){DongKes::list<int>lt={1,2,3,4};for(autoe:lt)cout<<e<<" ";cout<<endl;// 1 2 3 4lt.push_back(5);lt.push_front(0);for(autoe:lt)cout<<e<<" ";cout<<endl;// 0 1 2 3 4 5return0;}

七、list 的性能特点与适用场景

结合手写实现，回头理解标准库 list 的优劣就很自然了：

优点：

• 任意位置插入、删除都是 O(1)（已知位置时只需改指针，不挪动数据）；
• 按需申请节点空间，不用像 vector 那样扩容，也没有空间浪费。

缺点：

• 不支持下标随机访问，只能++/--顺序走，访问第 n 个元素是 O(N)；
• 物理不连续，缓存利用率低；
• 每个节点额外存 prev/next 两个指针，有空间开销。

选型建议：需要频繁在中间插入删除、又不需要随机访问时用 list；只是尾插尾删、要快速下标访问时，vector 通常更划算。

八、总结

1. 三层封装：list 大结构（_head + _size）→ list_node 节点（data/prev/next）→ list_iterator 迭代器。
2. 迭代器是灵魂：链表物理不连续，靠重载*、->、++、--、==、!=把裸指针翻译成直觉操作。
3. 三参数模板复用：<T, Ref, Ptr>一套类，传T&/T*得普通迭代器，传const T&/const T*得 const 迭代器，不重复写两个类。
4. 带头循环：头节点自环统一空/非空逻辑，[begin, end)左闭右开。
5. insert 四指针连线、erase 摘链返回 next，头尾增删全部复用这两个核心。

把这份实现自己敲一遍、画几幅指针连接图，list 这一关就吃透了。当然这篇是模拟库里的实现，库中的设计更为绝妙。

写完这篇STL：List，STL的基础讲解就搞一段落了
如果这篇对你有帮助，别忘了点赞收藏关注三连~ 咱们下篇见！

参考：std::list 双向带头循环链表实现与迭代器设计