List(模拟实现)

list模拟实现一、整体数据结构带头双向循环链表_head ──→[哨兵节点]←── _head ↕[节点1]←→[节点2]←→...←→[节点n]带头引入一个不存储有效数据的_head哨兵节点使得空链表时begin() end() _head无需额外判断是否为空。双向每个节点包含_prev前驱和_next后继指针支持从任意方向遍历实现和--的O(1)操作。循环尾节点的_next指向_head而_head-_prev指向最后一个有效节点形成闭环。这保证了遍历的自然终止条件。✅设计优势插入/删除操作无需处理头尾边界遍历逻辑统一避免空指针检查支持反向迭代器与正向迭代器共用同一套逻辑。二、节点结构list_nodeTtemplateclassTstructlist_node{T _data;list_nodeT*_next;list_nodeT*_prev;// 构造函数使用默认值初始化数据指针置为 nullptrlist_node(constTxT()):_data(x),_next(nullptr),_prev(nullptr){}}; 关键点解析_data存储实际元素_next指向下一个节点包括哨兵_prev指向前一个节点包括哨兵默认构造函数中T()是类型T的默认值如int为 0string为空串确保未显式赋值时不会出现未定义行为。⚠️ 注意在empty_init()中会将_next与_prev重设为指向自身构成自环。三、迭代器设计_list_iteratorT, X, Y实例化Xoperator*返回类型Yoperator-返回类型iteratorTT*const_iteratorconst Tconst T*3.1 为什么需要迭代器由于std::list的节点在内存中不连续不能像数组或vector那样通过指针算术访问元素。因此必须封装节点指针提供统一接口for(autoitlst.begin();it!lst.end();it){std::cout*it ;}迭代器的作用是封装底层指针提供operator*,operator-,operator,operator--等标准接口实现容器通用算法兼容性如std::sort,std::find。3.2 模板参数的巧妙运用运行符功能实现要点operator*()解引用返回 _node-_data返回类型由 X 决定operator-()成员访问返回 _node-_data返回类型由 Y 决定operator()前置_node _node-_next; return *this;operator(int)后置先保存 tmp再移动返回 tmp注意这里实际返回的是 Self 而非 Self是正确的operator--()前置–_node _node-_prev; return *this;operator--(int)后置–先保存 tmp再移动返回 tmpoperator! / operator比较直接比较底层 _node 指针templateclassT,classX,classYstruct_list_iterator{usingSelf_list_iteratorT,X,Y;usingNodelist_nodeT;Node*_node;_list_iterator(Node*node):_node(node){}// 运算符重载Xoperator*()const{return_node-_data;}Yoperator-()const{return_node-_data;}Selfoperator(){_node_node-_next;return*this;}Selfoperator(int){Self tmp*this;_node_node-_next;returntmp;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Self tmp*this;_node_node-_prev;returntmp;}booloperator!(constSelfother)const{return_node!other._node;}booloperator(constSelfother)const{return_nodeother._node;}};核心思想利用模板参数控制返回类型仅需一份代码即可同时支持可读写迭代器与只读迭代器避免重复编写两个几乎相同的类。❌ 反面教材被注释掉的struct_list_const_iterator{...};// 与 _list_iterator 几乎完全相同冗余四、list类主体实现详解4.1 类型定义别名typedef_list_iteratorT,T,T*iterator;typedef_list_iteratorT,constT,constT*const_iterator;iterator允许修改元素内容const_iterator只读访问用于const容器。4.2empty_init()—— 初始化核心voidempty_init(){_headnewlist_nodeT();_head-_next_head;_head-_prev_head;} 效果创建一个自环的哨兵节点形成如下结构_head ⇄ _head此时链表为空但begin()和end()相等所有插入/删除操作均可基于此统一逻辑进行不再需要对“空链表”做特殊处理。4.3begin()/end()接口iteratorbegin(){returniterator(_head-_next);}// 指向第一个有效节点iteratorend(){returniterator(_head);}// 指向哨兵节点尾后const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}✅ 设计哲学end()不指向最后一个节点而是指向哨兵节点循环条件it ! end()自然结束于所有有效节点之后与vector的end()行为一致符合标准库习惯。4.4insert()—— 核心插入操作iteratorinsert(iterator pos,constTval){Node*curpos._node;Node*newnodenewNode(val);Node*prevcur-_prev;// 四步连接prev → newnode → curprev-_nextnewnode;newnode-_nextcur;cur-_prevnewnode;newnode-_prevprev;_size;returniterator(newnode);} 图解在pos前插入新节点插入前: prev ←──→ cur 插入后: prev ←──→ newnode ←──→ cur✅ 优势无需判断是否为头/尾适用于任意位置插入复用性强push_front与push_back均可基于此实现。 复用示例voidpush_front(constTx){insert(begin(),x);}voidpush_back(constTx){insert(end(),x);// 在哨兵前插入 尾插}4.5erase()—— 核心删除操作iteratorerase(iterator pos){Node*curpos._node;Node*prevcur-_prev;Node*nextcur-_next;// 跳过当前节点prev → nextprev-_nextnext;next-_prevprev;deletecur;--_size;returniterator(next);// 返回下一个位置防止迭代器失效} 关键设计亮点删除后返回next让调用者可以继续安全遍历适用于clear()的循环删除voidclear(){while(_head-_next!_head){erase(begin());}}✅ 无需担心迭代器失效问题因为每次erase返回的是下一个合法位置。4.6 构造 / 拷贝 / 赋值 / 析构函数实现方式说明默认构造empty_init()创建自环哨兵拷贝构造empty_init() 循环 push_back深拷贝逐个尾插initializer_list 构造同上支持 list l {1,2,3}swap()std::swap(_head) std::swap(_size)交换头指针和大小O(1)赋值运算符 operator现代写法按值传参 swaplist lt 按值传入调用拷贝构造然后与 this 交换旧资源随 lt 析构自动释放析构clear() delete _headclear() 删所有有效节点再删哨兵clear()循环调用 erase(begin())利用 erase 返回下一个位置的特性逐个删除默认构造函数list(){empty_init();}创建自环哨兵节点初始大小为 0。拷贝构造函数深拷贝list(constlistlt){empty_init();// 初始化哨兵for(constautoe:lt){push_back(e);// 逐个尾插}}✅ 优点逻辑清晰易于理解✅ 缺点性能较低多次动态分配✅ 但可通过reserve()或预分配优化。initializer_list构造函数list(std::initializer_listTil){empty_init();for(constautoe:il){push_back(e);}}支持语法listintl{1,2,3,4};swap()函数交换成员voidswap(listother){std::swap(_head,other._head);std::swap(_size,other._size);}⏱️ 时间复杂度O(1)仅交换指针与整数✅ 用于现代赋值运算符优化。赋值运算符现代写法listToperator(listTlt){swap(lt);return*this;}✅ 优势分析按值传参触发拷贝构造生成临时副本swap交换当前对象与临时对象的资源自动释放旧资源临时对象析构时销毁原数据强异常安全性即使中间出错原对象仍保持不变自动处理自赋值a a无副作用。 传统写法对比已注释listToperator(constlistTlt){if(this!lt){clear();for(constautoe:lt)push_back(e);}return*this;}❌ 缺点若push_back抛异常则可能部分插入成功导致状态不一致必须手动判断自赋值性能差需逐个插入。析构函数~list(){clear();delete_head;}clear()删除所有有效节点最终删除哨兵节点。clear()函数voidclear(){while(_head-_next!_head){erase(begin());}}✅ 利用erase返回next特性实现简洁优雅的循环删除✅ 无需维护额外指针或计数器✅ 代码复用率高。五、设计亮点总结重点突出特性说明价值哨兵节点_head自环空链表时begin() end()消除边界判断统一逻辑双向循环链表支持前后移动O(1)插删高效支持任意位置操作模板参数复用迭代器X/Y控制返回类型一份代码支持iterator与const_iteratorinsert/erase复用所有增删操作基于这两个核心函数降低耦合减少错误现代赋值运算符按值传参 swap异常安全简洁高效erase返回next解决迭代器失效问题支持clear()的安全循环删除六、完整代码片段示例关键部分整合#includeiostream#includememorytemplateclassTstructlist_node{T _data;list_nodeT*_next;list_nodeT*_prev;list_node(constTxT()):_data(x),_next(nullptr),_prev(nullptr){}};templateclassT,classX,classYstruct_list_iterator{usingNodelist_nodeT;Node*_node;_list_iterator(Node*node):_node(node){}Xoperator*()const{return_node-_data;}Yoperator-()const{return_node-_data;}_list_iteratoroperator(){_node_node-_next;return*this;}_list_iteratoroperator(int){_list_iterator tmp*this;_node_node-_next;returntmp;}_list_iteratoroperator--(){_node_node-_prev;return*this;}_list_iteratoroperator--(int){_list_iterator tmp*this;_node_node-_prev;returntmp;}booloperator!(const_list_iteratorother)const{return_node!other._node;}booloperator(const_list_iteratorother)const{return_nodeother._node;}};templateclassTclasslist{public:typedef_list_iteratorT,T,T*iterator;typedef_list_iteratorT,constT,constT*const_iterator;private:list_nodeT*_head;size_t _size;voidempty_init(){_headnewlist_nodeT();_head-_next_head;_head-_prev_head;}public:list(){empty_init();}~list(){clear();delete_head;}voidclear(){while(_head-_next!_head){erase(begin());}}iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}voidpush_back(constTx){insert(end(),x);}voidpush_front(constTx){insert(begin(),x);}iteratorinsert(iterator pos,constTval){Node*curpos._node;Node*newnodenewlist_nodeT(val);Node*prevcur-_prev;prev-_nextnewnode;newnode-_nextcur;cur-_prevnewnode;newnode-_prevprev;_size;returniterator(newnode);}iteratorerase(iterator pos){Node*curpos._node;Node*prevcur-_prev;Node*nextcur-_next;prev-_nextnext;next-_prevprev;deletecur;--_size;returniterator(next);}listToperator(listTlt){swap(lt);return*this;}voidswap(listother){std::swap(_head,other._head);std::swap(_size,other._size);}};七、使用示例intmain(){listintlst{1,2,3};for(autoitlst.begin();it!lst.end();it){std::cout*it ;}std::cout\n;lst.push_front(0);lst.push_back(4);for(constautoe:lst){std::coute ;}std::cout\n;autoitlst.begin();it;lst.erase(it);// 移除 2for(autoe:lst){std::coute ;}std::cout\n;return0;}✅ 输出1 2 3 0 1 2 3 4 0 1 3 4✅ 总结本实现充分体现了现代 C的设计哲学零成本抽象Zero-cost abstractionRAII资源获取即初始化异常安全代码复用与泛型编程接口一致性与易用性。 该list实现不仅功能完备而且具备生产级可用性是学习标准库底层原理的理想范例。