C++ 手写 List 容器实战：从双向链表原理到完整功能落地，附源码与测试验证

🔥草莓熊Lotso：个人主页
❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受！

🎬 博主简介：

文章目录

• 前言：
• 一. 底层原理：List 容器的 “骨架”—— 带头双向循环链表
  • 1.1 结构组成与优势
  • 1.2 核心特性（对比 vector）
• 二. 模块实现：Lotso 命名空间下的 List 核心代码
  • 2.1 模块 1：链表节点（list_node）—— 容器的 “基本单元”
    • 2.1.1 代码实现（来自 list.h）
    • 2.1.2 核心解析
  • 2.2 模块 2：迭代器（list_iterator）—— 容器的 “导航工具”
    • 2.2.1 代码实现（来自 list.h）
    • 2.2.2 核心解析
  • 2.3 模块3：容器类（list）——List 功能的 “中枢”
    • 2.3.1 代码实现（来自 list.h）
    • 2.3.2 核心解析
• 三. 功能测试：用 test.cpp 验证 List 正确性
  • 3.1 测试用例1：基础构造与遍历(push_back+迭代器/范围for)
    • 3.1.1 代码实现(来自 test.cpp)
    • 3.1.2 测试结构与分析
  • 3.2 测试用例 2：头插、头删、尾删
    • 3.2.1 代码实现（来自 test.cpp）
    • 3.2.2 测试结果与分析
  • 3.3 测试用例 3：const 迭代器与拷贝构造
    • 3.3.1 代码实现（来自 test.cpp）
    • 3.3.2 测试结果与分析
  • 3.4 测试用例 4：insert、erase 与 clear
    • 3.4.1 代码实现（来自 test.cpp）
    • 3.4.2 测试结果与分析
• 结尾：

前言：

日常开发中，我们频繁调用std::list的push_back、erase等接口，却常忽略其 “为何插入删除高效”“迭代器为何只在删除时失效” 等核心问题。面试被要求手写 List 时卡壳、开发中因迭代器失效导致程序崩溃，根源都在对底层逻辑的不理解。

一. 底层原理：List 容器的 “骨架”—— 带头双向循环链表

要手写 List，先明确其底层结构 ——带头双向循环链表，这是所有接口高效实现的基础。

1.1 结构组成与优势

通过这种结构设计，List容器实现了任意位置插入/删除O(1)效率、遍历逻辑统一、边界处理简化三大核心优势，是区别于vector动态数组的关键设计。

1.2 核心特性（对比 vector）

通过对比可见：

• 若场景以 频繁插入/删除（尤其是中间位置） 为主，优先选择 List；
• 若场景以 频繁随机访问、尾端插入 为主，优先选择 vector。
• 补充： List虽然封装了成员sort（底层类似归并排序），但是效率是不如算法库里的，所以如果需要排序还是vector比较好

二. 模块实现：Lotso 命名空间下的 List 核心代码

还是和之前 string 实现博客的 “分模块 + 代码 + 解析” 风格一样，我们这里按 “节点→迭代器→容器类” 的依赖顺序来逐步实现 List。

2.1 模块 1：链表节点（list_node）—— 容器的 “基本单元”

节点是存储数据的载体，用模板类实现泛型支持，适配任意数据类型（如int、string）。

2.1.1 代码实现（来自 list.h）

#pragmaonce#include<iostream>#include<list>usingnamespace std;namespace Lotso {// 链表节点结构：存储数据与双向指针template<classT>structlist_node{ list_node<T>* _prev;// 前驱节点指针 list_node<T>* _next;// 后继节点指针 T _data;// 节点数据// 构造函数：默认值初始化，指针置空list_node(const T& x =T()):_prev(nullptr),_next(nullptr),_data(x){}};}

2.1.2 核心解析

• 模板参数T：支持任意数据类型，例如Lotso::list<int>存储整数，Lotso::list<string.>存储字符串，与 string 的泛型设计一致。
• 默认构造参数：T()确保内置类型（如int）默认初始化为 0，自定义类型自动调用其默认构造函数，兼容性强。
• 指针初始化：_prev与_next初始化为nullptr，避免野指针风险，后续由容器类统一管理指针链接。

2.2 模块 2：迭代器（list_iterator）—— 容器的 “导航工具”

List 的迭代器不是原生指针而是封装list_node*的类，通过运算符重载模拟指针行为，同时用 “三模板参数” 复用普通 /const 迭代器。

2.2.1 代码实现（来自 list.h）

namespace Lotso {// 迭代器类：T-数据类型，Ref-引用类型，Ptr-指针类型template<classT,classRef,classPtr>structlist_iterator{using Self = list_iterator<T, Ref, Ptr>;// 简化自身类型名using Node = list_node<T>;// 节点类型别名 Node* _node;// 迭代器指向的节点指针// 迭代器构造：接收节点指针初始化list_iterator(Node* node):_node(node){}// 1. 解引用运算符：返回数据引用（普通迭代器可修改，const不可） Ref operator*(){return _node->_data;}// 2. 箭头运算符：支持复杂类型成员访问（如struct.field） Ptr operator->(){return&_node->_data;}// 3. 前置++：向后移动（指向后继节点） Self&operator++(){ _node = _node->_next;return*this;}// 4. 后置++：先返回当前，再移动 Self operator++(int){ Self tmp(*this); _node = _node->_next;return tmp;}// 5. 前置--：向前移动（指向前驱节点） Self&operator--(){ _node = _node->_prev;return*this;}// 6. 后置--：先返回当前，再移动 Self operator--(int){ Self tmp(*this); _node = _node->_prev;return tmp;}// 7. 相等判断：比较节点指针booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};}

2.2.2 核心解析

• 三模板参数复用：参考 string 的 const 迭代器设计，Ref为T&时是普通迭代器（可修改数据），为const T&时是 const 迭代器（只读）；Ptr同理，避免单独定义 const 迭代器的代码冗余(单独定义一个的话和普通迭代器区别不大，所以比较浪费)。
• 运算符重载：完全模拟指针行为，遍历（++/--）、访问数据（*/->）的用法与原生指针一致，无需改变使用习惯。
• 无内存管理：迭代器仅作为 “导航工具”，不负责节点内存的创建与释放，避免与容器类的内存逻辑耦合。

2.3 模块3：容器类（list）——List 功能的 “中枢”

容器类整合节点与迭代器，提供构造，插入，删除，遍历等核心接口，底层通过调整指针实现高效的操作(参考 string 的"接口复用"思想，如 push_back 复用 insert)。

2.3.1 代码实现（来自 list.h）

namespace Lotso {template<classT>classlist{using Node = list_node<T>;// 节点类型别名public:// 类型重定义：普通/const迭代器（复用list_iterator）using iterator = list_iterator<T, T&, T*>;using const_iterator = list_iterator<T,const T&,const T*>;// -------------------------- 迭代器接口 -------------------------- iterator begin(){returniterator(_head->_next);} iterator end(){returniterator(_head);} const_iterator begin()const{returnconst_iterator(_head->_next);} const_iterator end()const{returnconst_iterator(_head);}// -------------------------- 初始化接口 --------------------------// 空链表初始化：创建哨兵头节点，形成自环voidempty_init(){ _head =new Node; _head->_prev = _head; _head->_next = _head;}// 默认构造list(){empty_init();}// 初始化列表构造（支持{1,2,3}形式）list(initializer_list<T> il){empty_init();for(auto& e : il)push_back(e);}// 范围构造（支持[first, last)区间）template<classInputIterator>list(InputIterator first, InputIterator last){empty_init();while(first != last){push_back(*first);++first;}}// 析构函数：释放所有节点，避免内存泄漏~list(){clear();// 先删除所有数据节点delete _head;// 再删除哨兵头节点 _head =nullptr;// 置空指针，避免野指针 _size =0;}// -------------------------- 插入删除接口 --------------------------// 尾插：复用insert，简化代码voidpush_back(const T& x){insert(end(), x);}// 头插：复用insertvoidpush_front(const T& x){insert(begin(), x);}// 尾删：复用erasevoidpop_back(){erase(--end());}// 头删：复用erasevoidpop_front(){erase(begin());}// 任意位置插入：调整指针实现O(1)插入voidinsert(iterator pos,const T& x){ Node* cur = pos._node;// pos指向的当前节点 Node* prev = cur->_prev;// 当前节点的前驱 Node* newnode =newNode(x);// 新建数据节点// 调整指针：prev <-> newnode <-> cur newnode->_prev = prev; newnode->_next = cur; prev->_next = newnode; cur->_prev = newnode;++_size;// 有效元素个数递增}// 任意位置删除：返回下一个有效迭代器，避免失效 iterator erase(iterator pos){ Node* cur = pos._node;// 待删除节点 Node* prev = cur->_prev;// 前驱节点 Node* next = cur->_next;// 后继节点// 调整指针：跳过cur节点，连接prev和next prev->_next = next; next->_prev = prev;delete cur;// 释放待删除节点内存--_size;// 有效元素个数递减returniterator(next);// 返回下一个有效迭代器}// 清空容器：保留哨兵头节点，便于后续复用voidclear(){ iterator it =begin();while(it !=end()) it =erase(it);}// -------------------------- 其他接口 --------------------------// 获取有效元素个数 size_t size()const{return _size;}private: Node* _head;// 哨兵头节点指针 size_t _size =0;// 有效数据节点个数};}

2.3.2 核心解析

• 空初始化empty_init()：参考string的reserve初始化逻辑，创建哨兵位头节点统一空链表和非空链表的操作逻辑，避免插入时还需额外判断是"否为头节点"。
• 接口复用：push_back/push_front复用insert，pop_back/pop_front复用erase，减少代码冗余，与 string 的+=复用push_back思路一致。
• 迭代器失效处理：erase返回下一个有效迭代器，用户可通过it=erase(it)更新迭代器，避免访问失效节点，解决List迭代器失效的核心痛点。
• 内存管理：析构函数先clear()删除所有数据节点，再释放哨兵位头节点，确保无内存泄漏；clear()进删除数据节点，保留头节点，便于容器后续复用。

三. 功能测试：用 test.cpp 验证 List 正确性

参考 string 实现博客的 “测试用例 + 结果分析” 风格，用你提供的test.cpp代码，覆盖构造、遍历、插入、删除等核心场景，验证容器功能。

3.1 测试用例1：基础构造与遍历(push_back+迭代器/范围for)

3.1.1 代码实现(来自 test.cpp)

#define_CRT_SECURE_NO_WARNINGS1#include"list.h"usingnamespace std;voidtest_list1(){ Lotso::list<int> lt;// 尾插4个元素 lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4);// 1. 迭代器遍历 Lotso::list<int>::iterator it = lt.begin();while(it != lt.end()){ cout <<*it <<" ";// 预期输出：1 2 3 4++it;} cout << endl;// 2. 范围for遍历（依赖begin()和end()）for(auto e : lt){ cout << e <<" ";// 预期输出：1 2 3 4} cout <<"\n"<< endl;}intmain(){test_list1();return0;}

3.1.2 测试结构与分析

结论：默认构造、尾插及两种遍历方式均正常工作，迭代器begin()/end()逻辑正确。

3.2 测试用例 2：头插、头删、尾删

3.2.1 代码实现（来自 test.cpp）

voidtest_list2(){ Lotso::list<int> lt;// 头插2个元素，尾插2个元素 lt.push_front(-2); lt.push_front(-1); lt.push_back(1); lt.push_back(2); cout <<"头插+尾插后：";for(auto e : lt) cout << e <<" ";// 预期输出：-1 -2 1 2 cout << endl;// 尾删2次，头删2次 lt.pop_back(); lt.pop_back(); lt.pop_front(); lt.pop_front(); cout <<"删除后size："<< lt.size()<< endl;// 预期输出：0 cout << endl;}intmain(){//test_list1();test_list2();return0;}

3.2.2 测试结果与分析

结论： 头插，头删，尾删功能正常，size()接口能正确反映有效元素个数

3.3 测试用例 3：const 迭代器与拷贝构造

3.3.1 代码实现（来自 test.cpp）

// 用const迭代器遍历的打印函数（验证只读特性）voidPrint(const Lotso::list<int>& lt){ Lotso::list<int>::const_iterator it = lt.begin();while(it != lt.end()){// *it = 10; // 编译报错：const迭代器不可修改数据 cout <<*it <<" ";++it;} cout << endl;}voidtest_list3(){// 初始化列表构造 Lotso::list<int> lt1 ={1,2,3,4,5,6};// 拷贝构造 Lotso::list<int>lt2(lt1); cout <<"lt2（拷贝lt1）：";for(auto e : lt2) cout << e <<" ";// 预期输出：1 2 3 4 5 6 cout << endl;// const迭代器遍历const Lotso::list<int>& clt = lt1; cout <<"const迭代器遍历lt1：";Print(clt);// 预期输出：1 2 3 4 5 6 cout << endl;}intmain(){//test_list1();//test_list2();test_list3();return0;}

3.3.2 测试结果与分析

结论：拷贝构造实现深拷贝（修改 lt1 不影响 lt2），const 迭代器仅支持只读访问，符合设计预期。

3.4 测试用例 4：insert、erase 与 clear

3.4.1 代码实现（来自 test.cpp）

voidtest_list4(){ Lotso::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4);// 任意位置插入：在第2个元素（2）前插入100auto it = lt.begin();++it; lt.insert(it,100); cout <<"插入100后：";for(auto e : lt) cout << e <<" ";// 预期输出：1 100 2 3 4 cout << endl;// 任意位置删除：删除100 it = lt.begin();++it; it = lt.erase(it); cout <<"删除100后：";for(auto e : lt) cout << e <<" ";// 预期输出：1 2 3 4 cout << endl;// 清空容器 lt.clear(); cout <<"clear后size："<< lt.size()<< endl;// 预期输出：0}intmain(){//test_list1();//test_list2();test_list3();//test_list4();return0;}

3.4.2 测试结果与分析

结论：任意位置插入 / 删除功能正常，clear()能正确清空数据节点，erase返回的迭代器有效。

结尾：

往期回顾：
《C++ STL list 完全指南：从基础操作到特性对比，解锁链表容器高效用法》
揭开 C++ vector 底层面纱：从三指针模型到手写完整实现
结语：至此，我们完成了从双向循环链表原理到 C++ List 容器的实战落地。从哨兵节点简化边界逻辑，到双向指针支撑迭代器操作，每一步都印证了 “底层结构决定容器特性”—— 正是链表的设计，让 List 在频繁插入删除场景中具备 O (1) 效率。手写 List 的核心价值，在于跳出 STL 黑盒，真正吃透迭代器失效、内存分配等细节，夯实指针操作与容器设计思维。后续可进一步探索 STL 源码优化，或尝试手写其他容器，在实践中持续深化 C++ 底层能力。

✨把这些内容吃透超牛的！放松下吧✨ʕ˘ᴥ˘ʔづきらど