往期内容回顾
前言
在 C++ 标准模板库（STL）中，std::list 是一个基于 双向链表（doubly linked list） 的容器，适用于频繁的插入、删除操作，且对元素的位置操作较多的场景。
相比于 vector 的连续内存存储，list 的节点是分散存储的，这带来了 插入/删除 O(1) 的优势，但随机访问性能较差（O(n)）。
学习 list 的最佳方式，不仅是掌握它的 基本使用，要学会它的底层逻辑实现，自己实现一遍，这可以加深对链表结构、内存管理以及 STL 设计思想的理解。
今天，我们就从头构建一个自己的 mylist 类型，并逐步实现其核心功能。
主要内容介绍
本篇将围绕以下几个方面展开：
1、list 的数据结构设计
2、构造与析构
3、迭代器的实现
4、常用接口实现（push_back、push_front、insert、erase 等）
5、拷贝构造与赋值运算符
6、迭代器失效问题与注意事项
7、简单的测试与总结
一、list 的数据结构设计
1.1 节点结构（Node）
和 vector 不同，list 的元素不是连续存储的，每个节点都有三个部分：
template<typename T> struct ListNode { T _data; ListNode* _prev; ListNode* _next; ListNode(const T& val = T()) : _data(val), _prev(nullptr), _next(nullptr) {} };
_data 存储元素
_prev 指向前一个节点
_next 指向后一个节点
1.2 带哨兵位（sentinel）的链表设计
为了简化插入、删除的边界处理，我们使用一个 头结点（head） 作为哨兵：
空链表时：head->_next = head，head->_prev = head
非空时：头尾节点之间循环连接
template<typename T> class mylist { public: mylist() { _head = new ListNode<T>(); _head->_next = _head; _head->_prev = _head; } ~mylist() { clear(); delete _head; } void clear() { ListNode<T>* cur = _head->_next; while (cur != _head) { ListNode<T>* next = cur->_next; delete cur; cur = next; } _head->_next = _head; _head->_prev = _head; } private: ListNode<T>* _head; };
构造函数初始化哨兵节点
析构函数中调用 clear() 释放节点内存
二、迭代器的实现
迭代器本质上是一个包装了指针的类，使得我们的 list 能像 STL 一样用 begin()、end() 遍历。
template<typename T> struct list_iterator { typedef ListNode<T> Node; Node* _node; list_iterator(Node* node = nullptr) : _node(node) {} T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } list_iterator& operator++() { _node = _node->_next; return *this; } list_iterator operator++(int) { list_iterator tmp = *this; _node = _node->_next; return tmp; } bool operator!=(const list_iterator& other) const { return _node != other._node; } };
mylist 中提供：
list_iterator<T> begin() { return list_iterator<T>(_head->_next); }
list_iterator<T> end() { return list_iterator<T>(_head); }
三、常用接口实现
3.1 push_back
void push_back(const T& val) { insert(end(), val); }
3.2 push_front
void push_front(const T& val) { insert(begin(), val); }
3.3 insert
list_iterator<T> insert(list_iterator<T> pos, const T& val) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newNode = new Node(val); prev->_next = newNode; newNode->_prev = prev; newNode->_next = cur; cur->_prev = newNode; return list_iterator<T>(newNode); }
3.4 erase
list_iterator<T> erase(list_iterator<T> pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return list_iterator<T>(next); }
四、拷贝构造与赋值运算符
mylist(const mylist& other) : mylist() { for (auto& e : other) { push_back(e); } } mylist& operator=(mylist other) { swap(other); return *this; } void swap(mylist& other) { std::swap(_head, other._head); }注意：深浅拷贝问题！！！
六、注意事项（迭代器失效）
list 的插入、删除不会使已有迭代器失效（指向被删除节点的迭代器除外）
vector 不同：在扩容时所有迭代器失效
string 同 vector，连续存储结构中迭代器更容易失效
七、总结
通过手写一个简易版 list，我们可以直观感受到：
string、vector 依赖连续内存，适合随机访问
list 依赖节点链式存储，适合频繁插入/删除
不同容器在 性能、内存管理、迭代器失效规则 上有很大区别
自己实现一次 STL 容器，可以更深刻地理解 C++ 的内存管理与数据结构设
如果你已经能手写 vector 和 list，基本就能理解 STL 容器的核心思想，并且在实际开发中能做出更合理的容器选择。
【面试题】
1、vector个list的区别？
特性 |
vector |
list |
|---|---|---|
内存布局 |
连续内存 |
节点链表（双向链表） |
随机访问 |
支持 O(1) |
不支持，需要遍历 O(n) |
插入/删除 |
中间操作 O(n)；尾部 O(1) 均摊 |
已知位置插入/删除 O(1) |
缓存局部性 |
高，遍历快 |
较差，遍历慢 |
内存开销 |
小 |
每个节点多两个指针（前驱/后继） |
迭代器/指针稳定性 |
扩容或中间插入删除会失效 |
除被删元素外通常稳定 |
使用场景 |
主要是顺序访问、随机访问、多遍历 |
插入删除频繁、需要稳定迭代器/引用 |
2、vector和list的底层是如何实现？
vector：
本质是 动态数组。
内存连续存储，每次扩容时申请更大的连续内存，并把原有元素拷贝/移动过去。
支持随机访问（通过指针运算）。list：
list：
- 本质是 双向链表。
- 每个元素包装成节点，节点存放元素 + 前驱/后继指针。
- 内存不连续，插入/删除通过修改指针连接完成，随机访问需遍历。
3. vector 是如何进行增容的
当 vector 空间不足时，会触发 扩容：
申请 更大连续内存（通常是原容量的 1.5~2 倍）。
将原数组元素 拷贝或移动 到新内存。
释放旧内存。
扩容的复杂度：
单次扩容是 O(n)
均摊成本是 O(1)（因为扩容次数相对较少，摊销到每次插入）。
4、什么是迭代器失效？
迭代器失效指的是 迭代器、指针或引用指向的对象在容器修改后不再有效。
不同容器的失效规则不同：
vector：
扩容 → 所有迭代器失效
中间插入/删除 → 被移动的元素迭代器失效
尾部 push_back/pop_back → 扩容时失效，否则尾部迭代器失效
list：
插入 → 现有元素迭代器通常有效
删除 → 被删元素迭代器失效，其他仍有效。
string（连续内存）与 vector 类似
简单理解：迭代器失效就是“原来的指针或引用不再安全使用了”。