【STL list】双向带头循环链表，原理与模拟，三层封装一次讲透-北京尧图网络

STL list双向带头循环链表原理与模拟三层封装一次讲透哈喽大家好STL 系列接着更。前面聊完 string、容器适配器和模板进阶这篇咱们手写一个list也就是标准库里的双向带头循环链表。这篇也是想和大家一起见识一下封装的设计美。list 看着简单难点全在迭代器怎么封装上——为什么不能直接拿指针当迭代器为什么一套模板能同时变出普通迭代器和 const 迭代器这篇把三层结构拆开揉碎配一份能直接编译的实现还请放心食用~目录一、list 是什么物理不连续的双向循环链表二、三层封装总览三、第二层list_node 节点四、第三层迭代器封装本篇重点4.1 为什么非要封装一个迭代器类4.2 一套模板变出 iterator 和 const_iterator4.3 运算符重载逐个讲五、第一层list 类主体5.1 带头循环empty_init 让头节点自环5.2 begin 与 end左闭右开5.3 insert四根指针重新连线5.4 erase摘链并返回下一个位置5.5 头尾增删全部复用 insert / erase5.6 构造、拷贝、clear 与析构六、完整可编译实现七、list 的性能特点与适用场景八、总结一、list 是什么物理不连续的双向循环链表std::list的底层就是一条双向带头循环链表双向每个节点同时存前驱prev和后继next前后都能走带头额外设一个不存有效数据的哨兵头节点让空链表和非空链表的插入删除逻辑统一循环尾节点的 next 回头指向头头节点的 prev 指向尾首尾相接成环。它和 vector 最大的区别是物理空间不连续节点靠指针彼此串联。这个特点直接决定了为什么需要迭代器封装也是下一节的引子。二、三层封装总览手写 list 不是一坨代码而是清晰的三层结构层级角色包含内容第一层list大结构_head头节点指针、_size元素个数第二层list_node单个节点_data、_next、_prev第三层list_iterator迭代器封装指针重载*、-、、--、、!为什么要把迭代器单独抽成一层因为链表物理不连续用户不应该直接面对裸指针而应该像用 vector 一样写it、*it就能遍历。这层封装把指针的走法翻译成符合直觉的操作。三、第二层list_node 节点节点很简单存一份数据和两个指针templateclassTstructlist_node{T _data;list_nodeT*_next;list_nodeT*_prev;list_node(constTdataT()):_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 源码的做法是用三个模板参数一套类同时出两种迭代器templateclassT,classRef,classPtrstructlist_iterator{typedeflist_nodeTNode;typedeflist_iteratorT,Ref,PtrSelf;Node*_node;list_iterator(Node*node):_node(node){}// Ref 决定解引用拿到的是 T 还是 const TRefoperator*(){return_node-_data;}// Ptr 决定箭头返回的是 T* 还是 const T*Ptroperator-(){return_node-_data;}// ... 其余重载见下文};然后在 list 里这样别名化typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;普通迭代器传Ref T、Ptr T*解引用可读写const 迭代器传Ref const T、Ptr const T*只能读。这就是模板只靠传参类型不同就复用同一套代码的典型魅力也是源码里青睐的写法避免维护两个高度雷同的类。4.3 运算符重载逐个讲前置 / –走一格返回自身引用Selfoperator(){_node_node-_next;// 走到后继return*this;}Selfoperator--(){_node_node-_prev;// 走回前驱return*this;}后置 / –带int形参区分先保存旧值再走返回旧值Selfoperator(int){Selftmp(*this);// 保存修改前的自己_node_node-_next;returntmp;// 返回旧位置}Selfoperator--(int){Selftmp(*this);_node_node-_prev;returntmp;}相等比较比较底层是不是同一个节点booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}到这里while (it ! lt.end()) { cout *it; it; }这种写法就成立了用户完全感觉不到背后是链表指针。五、第一层list 类主体5.1 带头循环empty_init 让头节点自环先准备一个私有初始化函数创建头节点并让它的prev、next都指向自己空环voidempty_init(){_headnewNode;_head-_prev_head;_head-_next_head;_size0;}空链表时头节点自己接自己成环这样后面任何插入删除都不用单独判断是不是空逻辑统一。5.2 begin 与 end左闭右开iteratorbegin(){returniterator(_head-_next);// 第一个有效节点}iteratorend(){returniterator(_head);// 哨兵头节点尾后位置}和标准库一致区间是[begin, end)begin()指向第一个有效节点end()指向头节点本身尾后遍历到end()就停。5.3 insert四根指针重新连线在pos前面插入新节点经典四步改指针iteratorinsert(iterator pos,constTx){Node*curpos._node;Node*prevcur-_prev;Node*newnodenewNode(x);// 新节点双向连到 prev 和 curnewnode-_prevprev;newnode-_nextcur;// 两边回头连新节点prev-_nextnewnode;cur-_prevnewnode;_size;returniterator(newnode);}顺序不能乱先把新节点挂好再改两边的指针否则容易断链。5.4 erase摘链并返回下一个位置删除pos节点把它的前驱和后继直接接起来再释放iteratorerase(iterator pos){Node*curpos._node;Node*prevcur-_prev;Node*nextcur-_next;prev-_nextnext;next-_prevprev;deletecur;--_size;returniterator(next);// 返回下一个节点设计更优}返回下一个节点的迭代器是个重要设计这样在边遍历边删除时不用自己先保存it直接接收返回值即可避免迭代器失效问题。5.5 头尾增删全部复用 insert / erase有了 insert 和 erase头尾操作就是套壳voidpush_back(constTx){insert(end(),x);}// 尾插插到 end() 前voidpush_front(constTx){insert(begin(),x);}// 头插插到 begin() 前voidpop_back(){erase(--end());}// 尾删删最后一个有效节点voidpop_front(){erase(begin());}// 头删删第一个有效节点把通用逻辑收敛到 insert/erase外面只做位置包装代码干净不容易错。5.6 构造、拷贝、clear 与析构// 默认构造list(){empty_init();}// initializer_list 构造支持 listint lt {1,2,3};list(initializer_listTil){empty_init();for(autoe:il)push_back(e);}// 拷贝构造建新空环再逐个尾插复制list(constlistTlt){empty_init();for(autoe:lt)push_back(e);}// 清空有效节点保留头节点voidclear(){iterator itbegin();while(it!end())iterase(it);}// 析构先 clear 再删头节点~list(){clear();delete_head;_headnullptr;}注意拷贝构造不能直接复制_head指针否则两个对象指向同一条链表析构会二次释放。必须重新建节点逐个拷贝。六、完整可编译实现把上面拼起来就是一份精简但完整的手写 list#pragmaonce#includeassert.h#includeinitializer_list#includeutilitynamespaceDongKes{templateclassTstructlist_node{T _data;list_nodeT*_next;list_nodeT*_prev;list_node(constTdataT()):_data(data),_next(nullptr),_prev(nullptr){}};// 三参数模板一套出 iterator 与 const_iteratortemplateclassT,classRef,classPtrstructlist_iterator{typedeflist_nodeTNode;typedeflist_iteratorT,Ref,PtrSelf;Node*_node;list_iterator(Node*node):_node(node){}Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}Selfoperator(){_node_node-_next;return*this;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}Selfoperator--(int){Selftmp(*this);_node_node-_prev;returntmp;}booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}};templateclassTclasslist{typedeflist_nodeTNode;public:typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;list(){empty_init();}list(initializer_listTil){empty_init();for(autoe:il)push_back(e);}list(constlistTlt){empty_init();for(autoe:lt)push_back(e);}~list(){clear();delete_head;_headnullptr;}voidclear(){iterator itbegin();while(it!end())iterase(it);}iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}iteratorinsert(iterator pos,constTx){Node*curpos._node;Node*prevcur-_prev;Node*newnodenewNode(x);newnode-_prevprev;newnode-_nextcur;prev-_nextnewnode;cur-_prevnewnode;_size;returniterator(newnode);}iteratorerase(iterator pos){assert(_size0);Node*curpos._node;Node*prevcur-_prev;Node*nextcur-_next;prev-_nextnext;next-_prevprev;deletecur;--_size;returniterator(next);}voidpush_back(constTx){insert(end(),x);}voidpush_front(constTx){insert(begin(),x);}voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}Tfront(){return_head-_next-_data;}Tback(){return_head-_prev-_data;}size_tsize()const{return_size;}boolempty()const{return_size0;}private:voidempty_init(){_headnewNode;_head-_prev_head;_head-_next_head;_size0;}Node*_head;size_t _size0;};}测试代码#includeiostream#includelistusingnamespacestd;intmain(){DongKes::listintlt{1,2,3,4};for(autoe:lt)coute ;coutendl;// 1 2 3 4lt.push_back(5);lt.push_front(0);for(autoe:lt)coute ;coutendl;// 0 1 2 3 4 5return0;}七、list 的性能特点与适用场景结合手写实现回头理解标准库 list 的优劣就很自然了优点任意位置插入、删除都是 O(1)已知位置时只需改指针不挪动数据按需申请节点空间不用像 vector 那样扩容也没有空间浪费。缺点不支持下标随机访问只能/--顺序走访问第 n 个元素是 O(N)物理不连续缓存利用率低每个节点额外存 prev/next 两个指针有空间开销。选型建议需要频繁在中间插入删除、又不需要随机访问时用 list只是尾插尾删、要快速下标访问时vector 通常更划算。八、总结三层封装list 大结构_head _size→ list_node 节点data/prev/next→ list_iterator 迭代器。迭代器是灵魂链表物理不连续靠重载*、-、、--、、!把裸指针翻译成直觉操作。三参数模板复用T, Ref, Ptr一套类传T/T*得普通迭代器传const T/const T*得 const 迭代器不重复写两个类。带头循环头节点自环统一空/非空逻辑[begin, end)左闭右开。insert 四指针连线、erase 摘链返回 next头尾增删全部复用这两个核心。把这份实现自己敲一遍、画几幅指针连接图list 这一关就吃透了。当然这篇是模拟库里的实现库中的设计更为绝妙。写完这篇STLListSTL的基础讲解就搞一段落了如果这篇对你有帮助别忘了点赞收藏关注三连~ 咱们下篇见参考std::list 双向带头循环链表实现与迭代器设计

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

相关推荐

融合 CGA 老年综合评估的老年照护实训室建设方案

高温车间风冷液压冷却器为什么老是散热不够？真实原因和改进办法

ZXing 二维码倾斜校正：90° 与 45° 两级旋转让歪图也能扫

更多资讯

Android Gradle 依赖治理：Version Catalogs 四层协同实践

大模型API成本控制与企业级解决方案优化实践

知网与维普AIGC检测机制对比及优化策略

10款AI工具提升论文写作效率实测报告

Ansible自动化运维：核心原理与实战技巧

AI渲染庭院桌椅常见问题与专业解决方案

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？