摘要：List就像幼儿园里手拉手的小朋友们，每个小朋友（节点）都牵着前一个和后一个的手，这样就形成了一条长长的队伍。想加个新朋友？只要让旁边的两个小朋友松开手，拉上新朋友再重新牵上就行！vector更像军训时的方阵，大家排得整整齐齐，每个人都有自己固定的位置编号。想
话说 C++ 里的 List，本质上就是一个带头节点的双向循环链表，听着是不是有点绕？
很多朋友刚开始学List的时候，搞不懂它和vector的区别...大家请看这张图
图：带头节点的双向循环链表，头节点像个小队长，两边都指向自己
想象一下：
List就像幼儿园里手拉手的小朋友们，每个小朋友（节点）都牵着前一个和后一个的手，这样就形成了一条长长的队伍。想加个新朋友？只要让旁边的两个小朋友松开手，拉上新朋友再重新牵上就行！vector更像军训时的方阵，大家排得整整齐齐，每个人都有自己固定的位置编号。想插个队？后面的所有人都要集体往后挪一步！将数据进行链式存储，不像vector那样"住在一起"，而是"各住各家"，通过"电话线"（指针）联系！
（2）链表本质list是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。就像你家的连锁店，每家店地理位置不挨着，但都通过内部系统连成一个整体！
（3）链表组成链表由一系列结点（节点）组成，每个节点都是独立个体！
（4）节点结构一部分是存数据的，叫数据域，就像小朋友兜里揣的糖果；另一部分是存下一个结点地址的，叫指针域，相当于小朋友知道下一个人在哪。
list采用动态存储分配，不会造成内存浪费和溢出。执行插入和删除操作只需修改指针即可，不需要移动大量元素。这就像租房，想加人就加间房，不用所有人挤一挤！
（8）缺点也得说说
灵活是灵活，但指针域占空间，遍历起来也费时间，这就跟带了一堆行李出门，方便是方便，就是沉了点。
（9）重要性质
插入和删除操作不会让原来的迭代器失效，这点 Vector 可做不到，Vector 动一下，迭代器可能就废了。
专注Linux C/C++技术讲解~
// 节点 结构体templatestruct ListNode { ListNode* _next; // 指向下一个节点的指针 ListNode* _prev; // 指向前一个节点的指针 T _data; // 节点存储的数据 // 构造函数使用初始化列表（推荐但非必须） Listnode(T x = T) : _next(nullptr), _prev(nullptr), _data(x) {} /* // 等效的构造函数写法（不使用初始化列表） ListNode(T x = T) { _next = nullptr; _prev = nullptr; _data = x; } */ // 析构函数：避免野指针出现，将指针赋值为nullptr就可以了 ~ListNode { _next = nullptr; _prev = nullptr; } };使用模板来适配更多数据类型，这才是STL的通用做法！每个节点包含三个核心成员：_next、_prev和_data提供了构造函数（使用初始化列表是推荐做法，但不是必须的）析构函数虽然简单，但能有效避免野指针问题思考：构造函数使用初始化列表是必须的吗？
templateclass list { public: // 设置适配的节点类型别名（方便后续使用） typedef ListNodeNode; // 空初始化：创建头节点并形成循环 void empty_init { _head = new Node; // 创建头节点（哨兵节点） _head->_next = _head; // 头节点的next指向自己 _head->_prev = _head; // 头节点的prev也指向自己 _size = 0; // 初始大小为0 } // 构造函数 list : _head(nullptr) { empty_init; // 调用初始化函数 } private: Node* _head; // 头指针（实际上是哨兵节点） size_t _size; // 链表大小 };为什么要有哨兵节点？因为它让"空链表"和"非空链表"的操作逻辑完全一致，无需特殊处理头尾边界！
答案当然是不能！
// 这里的模板可以再次升级 先简单写一下templateNode; typedef ListIteratorSelf; Node* _node; // 指向当前节点的指针 // 构造函数 Listiterator(Node* x) : _node(x) {} // 前置++ ( ++it ) Self& operator++ // 注意返回引用，支持连续操作如++++it { _node = _node->_next; // 移动到下一个节点 return *this; // 返回当前迭代器引用 } // 后置++ ( it++ ) Self operator++(int) // int参数仅用于区分前置和后置 { Self tmp(*this); // 保存当前状态（浅拷贝即可） _node = _node->_next; // 移动到下一个节点 return tmp; // 返回移动前的状态 } // 前置-- ( --it ) Self& operator-- { _node = _node->_prev; // 移动到前一个节点 return *this; } // 后置-- ( it-- ) Self operator--(int) { Self tmp(*this); // 保存当前状态 _node = _node->_prev; // 移动到前一个节点 return tmp; } // 判断是否相等（比较指针地址是否相同） bool operator!=(const Self& it) const // 加上const更规范 { return _node != it._node; } // 判断是否相等 bool operator==(const Self& it) const { return _node == it._node; } // 解引用操作（*it）返回节点数据的引用（可以进行修改） T& operator* { return _node->_data; } // ->操作符重载（因为指针才能使用->，所以要返回地址/指针） T* operator-> // 编译器会进行省略-> { return &_node->_data; } };解析：
++it / it++：让迭代器指向下一个节点（不再是内存地址+1！）--it / it--：让迭代器指向前一个节点it：解引用获取当前节点的数据（返回引用，支持修改）it->：访问当前节点数据的成员（编译器会自动处理）== / !=：比较两个迭代器是否指向同一个节点关键点：前置++返回引用，后置++返回临时对象！这是C++迭代器的标准做法！
一般我们的迭代器应该还要支持const，不然我们传入一个不可修改的链表（const list）时，就会发生报错！那么我们还要书写一份const版的迭代器。如果每样都写一遍，那大部分代码都重复了（++、--、==、!=都是一样的），只有operator*和operator->返回值不一致：
普通迭代器：可以修改数据，返回 T& 和 T*const迭代器：数据只读，返回 const T& 和 const T*解决方案：使用模板参数技巧，让编译器帮我们处理类型差异！
// 升级版迭代器模板（三个参数：数据类型、引用类型、指针类型）templateSelf; Node* _node; ListIterator(Node* x) : _node(x) {} // 移动操作（++/--）保持不变 Self& operator++ { _node = _node->_next; return *this; } Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } Self& operator-- { _node = _node->_prev; return *this; } Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } // 比较操作保持不变 bool operator!=(const Self& it) const { return _node != it._node; } bool operator==(const Self& it) const { return _node == it._node; } // 关键点：使用模板参数Ref和Ptr来处理返回值类型差异 Ref operator* { return _node->_data; } Ptr operator-> { return &_node->_data; } };使用方式：
// 在list类中定义迭代器类型别名typedef ListIteratoriterator; // 普通迭代器 typedef ListIteratorconst_iterator; // const迭代器到此，我们实现了STL风格链表的三大核心组件：节点存储结构、容器主体框架、安全遍历机制，是不是很简单？
3.1、begin 与 end：迭代器的起点与终点迭代器的起始和结束位置得整明白。begin 就是头结点的下一个，end 直接就是头结点本身。为啥呢？因为遍历的时候，一圈下来最后就回到头结点了，所以判断是不是头结点就能知道该不该停。// 普通迭代器typedef ListIteratoriterator; // 常迭代器 typedef ListIteratorconst_iterator; iterator begin { return _head->_next; } iterator end { return _head; } const_iterator begin const { return _head->_next; } const_iterator end const { return _head; }代码解析：
begin：返回指向第一个实际数据节点的迭代器（即头节点的下一个节点）end：返回指向哨兵节点（头节点）的迭代器，这就是遍历的终点！为什么end是头节点？因为我们的链表是双向循环的，遍历完最后一个节点后，它的next就是头节点！const重载：为const list对象提供只读访问能力核心思想：利用哨兵节点作为统一的"终点标志"，让空链表和非空链表的遍历逻辑完全一致！空链表时，begin也等于end（都指向头节点）
void push_back(const T& x = T){ // 1. 创建新节点 Node* node = new Node(x); // 2. 找尾（头节点的前一个就是尾节点） Node* tail = _head->_prev; // 3. 进行插入操作（修改四个指针） node->_next = _head; // 新节点的next指向头节点 node->_prev = tail; // 新节点的prev指向原尾节点 tail->_next = node; // 原尾节点的next指向新节点 _head->_prev = node; // 头节点的prev也指向新节点 // 4. 更新大小 _size++;}插入逻辑可视化：
原尾节点(tail) 新节点(node) 头节点(_head) | | | | | | V V V[prev] ---> [next] [prev] ---> [next] [prev] ---> [next] ^ ^ ^ | | | | | | 原尾节点的前驱 原尾节点 新节点的后续void insert(iterator pos = begin, T x = T){ // 1. 创建新节点 Node* node = new Node(x); // 2. 找到插入位置的前后节点 Node* prev = pos._node->_prev; // pos前一个节点 Node* next = pos._node; // pos节点本身 // 3. 处理新节点的指针 node->_prev = prev; // 新节点前驱指向pos前一个节点 node->_next = next; // 新节点后继指向pos节点 // 4. 处理前后节点的指针 prev->_next = node; // pos前一个节点的后继指向新节点 next->_prev = node; // pos节点的前驱指向新节点 // 5. 更新大小 _size++;}核心思想：通过调整四个指针完成插入，不需要移动任何已有元素
void push_front(const T& x = T){ insert(begin, x); // 直接复用insert接口，在begin位置插入}头插其实就是"在第一个位置插入"，完全可以用insert(begin, x)实现，避免重复代码！3.3、删除操作：从链表中移除节点尾删操作 pop_backvoid pop_back{ // 1. 找到尾节点（头节点的前一个） Node* tail = _head->_prev; // 2. 找到尾节点的前一个节点（新的尾节点） Node* prev = tail->_prev; // 3. 调整指针：绕过tail节点 prev->_next = _head; // 新尾节点的next指向头节点 _head->_prev = prev; // 头节点的prev指向新尾节点 // 4. 释放内存（重要！避免内存泄漏） delete tail; // 5. 更新大小 _size--;}void pop_front{ // 1. 找到头节点的下一个（第一个实际节点） Node* head = _head->_next; // 2. 找到第二个节点（新的头节点） Node* next = head->_next; // 3. 调整指针：绕过head节点 _head->_next = next; // 头节点的next指向第二个节点 next->_prev = _head; // 第二个节点的prev指向头节点 // 4. 释放内存 delete head; // 5. 更新大小 _size--;}iterator erase(iterator pos){ // 1. 获取要删除的节点及其前后节点 Node* cur = pos._node; // 当前要删除的节点 Node* prev = cur->_prev; // 当前节点的前一个节点 Node* next = cur->_next; // 当前节点的后一个节点 // 2. 调整指针：绕过cur节点 prev->_next = next; // 前一个节点的next指向后一个节点 next->_prev = prev; // 后一个节点的prev指向前一个节点 // 3. 释放内存 delete cur; // 4. 更新大小 _size--; // 5. 返回下一个节点的迭代器（重要！） return iterator(next);}list(const list& l) { empty_init; // 先初始化一个空链表（创建哨兵节点） // 遍历原链表，逐个插入数据 iterator it = l.begin; while (it != l.end) { push_back(*it); // 复制数据到新链表 it++; } }如果追求更高性能，可以实现移动构造函数，避免不必要的数据拷贝！
void clear{ // 依次释放所有数据节点 iterator it = begin; while (it != end) { it = erase(it); // erase会返回下一个有效迭代器 }}~list{ clear; // 先清除所有数据节点 // 单独释放头结点空间 delete _head; _head = nullptr; // 避免野指针}维护一个_size成员变量，让获取大小的操作是O(1)时间复杂度，而不是遍历计算！
判断链表是否为空
bool empty{ return _size == 0; // 直接检查_size是最可靠的方式}虽然也可以通过判断begin == end来判断是否为空，但直接检查_size更直观高效！清空链表数据void clear{ iterator it = begin; while (it != end) { it = erase(it); // 循环删除所有数据节点 }}复用性： 与析构函数中的clear复用，保持代码一致性！
3.7、赋值运算符重载：支持深拷贝与移动语义
在C++中，如果你不显式定义赋值运算符，编译器会生成一个默认的版本，但对于管理资源的类（如我们的list），默认的赋值运算符只是简单地按成员拷贝指针，这会导致多个对象共享同一块内存，最终可能引发双重释放的严重问题！
拷贝赋值运算符（深拷贝版本）
& operator=(const list& other) { // 1. 防止自赋值（非常重要！） if (this != &other) { // 2. 先清空当前链表 clear; // 3. 再深拷贝other链表的数据 iterator it = other.begin; while (it != other.end) { push_back(*it); // 逐个添加元素 it++; } } // 4. 返回当前对象的引用以支持链式赋值 return *this; }移动赋值运算符（C++11 引入的高效版本）
& operator=(list&& other) noexcept { // 1. 防止自赋值 if (this != &other) { // 2. 先清理当前链表的资源 clear; // 3. 直接"窃取"other的资源（高效转移所有权） _head = other._head; _size = other._size; // 4. 将other置于有效但空的状态（符合移动语义约定） other._head = nullptr; other._size = 0; } return *this; }在我们前面的实现中，除了被删除节点的迭代器外，其他迭代器在插入和删除操作后仍然有效！这是list相比vector的一大优势！
特别注意：当调用 erase(iterator pos) 时，被删除节点的迭代器pos会失效，但函数返回的是下一个有效节点的迭代器，这正是STL的标准做法！
// 我们之前的erase实现已经考虑了这一点iterator erase(iterator pos){ // ... [指针调整和内存释放代码同前] ... // 关键点：返回下一个节点的迭代器，保证迭代器连续性 return iterator(next); // 用户可以安全地继续使用返回的迭代器}// 典型安全使用模式：iterator it = myList.begin;while (it != myList.end){ if (需要删除当前元素的条件) { // erase会返回下一个有效迭代器，直接赋值给it即可 it = myList.erase(it); // ✅ 安全！ } else { // 只是不删除时才递增迭代器 ++it; // ✅ 安全！ }}// 在指定迭代器位置前插入元素（与现有insert保持一致的语义）// 我们的现有insert实际上是在pos位置前插入（STL标准做法）// 所以此函数可以作为别名或明确文档说明iterator insert_before(iterator pos, const T& x){ return insert(pos, x); // 复用现有实现}// 尾部插入的另一种表示（与push_back完全一样，仅为接口丰富性）void emplace_back(const T& x){ push_back(x); // 当前简单实现，后续可扩展为原地构造}// 头部插入的另一种表示（与push_front完全一样，仅为接口丰富性）void emplace_front(const T& x){ push_front(x); // 当前简单实现，后续可扩展为原地构造}// 查找元素（线性搜索，返回第一个匹配元素的迭代器）iterator find(const T& x){ iterator it = begin; while (it != end) { if (*it == x) // 假设T类型支持==操作符 { return it; } ++it; } return end; // 未找到返回end}理解底层原理比单纯使用API更重要，当你自己实现过list，以后用STL的list就会更加得心应手！来源：小茵说科技