送给大家一句话：
若结局非你所愿，就在尘埃落定前奋力一搏。—— 《夏目友人帐》
手搓 list 容器
1 前言
List是C++标准模板库(STL)中的一个成员，其本质为带头双向循环链表。不同于连续的、紧密排列的数组容器Vector，List容器的内部是由双向链表构成的，使得它在插入和删除操作上，就如同行云流水一般顺畅，不需移动其它元素。
1.1 底层结构
List容器的底层结构，是一个经典的带头双向循环链表。每个节点包含：
- 数据
- 指向前一个节点的指针
- 指向后一个节点的指针。
这种结构赋予了List灵动的特性：它能够轻松地在任意位置增加或移除元素，而这种操作几乎是与容器大小无关的，体现了时间复杂度上的优势。但这种优势的代价是，与数组相比，List在访问元素时的速度会较慢，因为它需要从头开始遍历。这也决定了list的更适合频繁插入的动态数据。
来看STL源码中的节点结构：
template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data; };
1.2 使用场景
List最适合的场景是那些需要频繁进行插入和删除操作的场合。
例如，如果你正在管理一个动态变化的列表，如任务调度、人员排队等场景，List的特性将大放异彩。但是如果你的应用场景更多地需要随机访问元素，那么向量（Vector）或者数组可能是更佳的选择。因为List的顺序访问性能相比之下会显得有些力不从心。
- 所以如果需要频繁随机的访问数据，那么选择vector容器
- 如果需要频繁插入删除数据，那么选择list容器
- 排序不要选择list ！！！其删除节点的过程就决定了其速度不会太快。
1.3 功能简介
功能简介我们可以参考STL官方库 :list文档介绍
- 插入与删除：List的插入和删除操作非常高效，它可以在任意位置快速地添加或移除元素，而不需要像连续内存容器那样进行大量元素的移动。
- 多种构造：类都应该包含多种构造函数
- 支持迭代器：迭代器是C++重要的特性，我们写的list 也一定要支持迭代器。
2 框架搭建
现在我们开始实现list 容器，首先先要思考一下框架结构：
- 首先我们需要一个节点结构体（类似源码中的节点）
- 其次我们的list 类要带一个头结点，让我们更方便进行插入删除操作
基本就是这样，现在我们开始手搓
2.1 节点类
// 节点 结构体 template<class T> struct 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; //} ~ListNode() { _next = nullptr; _prev = nullptr; } };
这里使用模版来适配更多的情景，然后基本的数据，前后指针都很简单。在编写一个构造函数，==构造函数使用初始化列表，并不是必须使用。析构函数避免野指针出现，将指针赋值为nullptr就可以了。
2.2 list 类
我们先进行简单的框架书写，构造函数需要创建一个头结点，因为我们要创建双向循环链表，所以头尾都要指向头结点本身。 _size赋初值。
template<class T> class list { public: //设置适配的节点 typedef ListNode<T> Node; //空初始化 void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } //构造函数 list() : _head(nullptr) { empty_init(); } private: Node* _head; size_t _size; };
接下来我们来逐步完成功能书写，由于我们还没有进行迭代器的书写
2.3 迭代器类
我们思考一下这里能不能使用原生指针来完成迭代器的操作（++ == != --）当然是不能的，因为链表的物理地址并不是连续的，对原生指针的++或–操作是没有意义的，所以我们需要自行编写迭代器类，对原生指针进行封装，来满足我们特殊的++和–操作。
//这里的模板可以再次升级 先简单写一下 template<class T> class ListIterator { public: //重命名方便书写 typedef ListNode<T> Node; typedef ListIterator<T> Self; Node* _node; ListIterator(Node* x ): _node(x) {} //操作符重载 前置++ 与 后置++的区别是参数是否带（int） //++t Self operator++() { _node = _node->_next; return *this; } //t++ Self operator++(int) { Self tmp(*this);//浅拷贝即可 _node = _node->_next; return tmp; } //--t Self operator--() { _node = _node->_prev; return *this; } //t-- Self operator--(int) { Self tmp(*this);//浅拷贝即可 _node = _node->_prev; return tmp; } //判断是否相等 比较指针地址是否相同即可 bool operator!=(const Self& it) { return _node != it._node; } //判断是否相等 比较指针地址是否相同即可 bool operator==(const Self& it) { return _node == it._node; } // 解引用操作 *it 返回节点数据的引用 可以进行修改 T& operator*() { return _node->_data; } //因为指针才能使用-> 所以->要返回地址（指针） T* operator->()//编译器会进行省略-> { return &_node->_data; } };
这样迭代器类就大致写好了，那么一般我们的迭代器应该还要支持const，不然我们传入一个不可修改的链表（const list l）,就会反生报错，那么我们还要书写一份const版的迭代器。如果进行编写，那么是不是会有大部分与刚才我们书写的迭代器重复（++ -- == != 都是一样的），只有operator*()和operator->()返回值不一致：
- 因为是常迭代器，使用场景是对const list l进行操作，那么节点数据不可改变，所以不影响++ -- == != 这些操作，受影响的是operator*()和operator->()返回值（该情况下链表本身是只读的，又因为不能将权限进行扩大，所以返回值应该也是只读的（const））。
- 那这样就发现了不同常迭代器应该为 const T& operator*() 和 const T* operator->() ,所以有没有一种办法可以简单解决呢，当然有了，我们设置一个新模版（带有三个参数），创建的时候就传入对应参数
我们将模版修改为这样，
//reference 引用 pointer 指针 template<class T , class Ref ,class Ptr>
对应返回值也改变：
Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; }
那么类实例化的时候传入对应参数就好了：
typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator;
这样就实现了迭代器的创建，是不是就非常简洁了呢
3 功能实现
3.1 begin() 与 end()
使用迭代器即可，注意end()是头结点，因为遍历过程中，全部遍历后会回到头结点，所以直接判断是
否为头结点就能控制结束位置。
//普通迭代器 typedef ListIterator<T, T&, T*> iterator; //常迭代器 typedef ListIterator<T, const T&, const T*> const_iterator; iterator begin() { return _head->_next; } iterator end() { return _head; } const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; }
3.2 插入操作
插入操作我们很熟悉，步骤是创建一个新节点，然后通过改变指针指向来完成插入操作：
来看尾插操作，
void push_back(const T& x = T()) { //创建新节点 Node* node = new Node(x); //找尾 Node* tail = _head->_prev; //进行插入 node->_next = _head; node->_prev = tail; tail->_next = node; _head->_prev = node; //别忘记大小++ _size++; }
任意位置插入，操作思路依然是对前后节点与新节点的指针指向进行操作，来完成插入。
void insert(iterator pos = begin(), T x = T()) { //创建新节点 Node* node = new Node(x); //前节点 后节点 Node* prev = pos._node->_prev; Node* next = pos._node; //处理新节点 node->_prev = prev; node->_next = next; //出现前后节点 prev->_next = node; next->_prev = node; //别忘记大小++ _size++; }
头插，直接干脆调用insert就可以了
void push_front(const T& x = T()) { insert(begin(), x); }
3.3 删除操作
删除操作，同样是使用指针操作，来达到删除的效果。注意要对删除的节点进行释放空间操作（delete），不然会发生内存泄漏！！！
尾删 void pop_back() { Node* tail = _head->_prev; Node* prev = tail->_prev; prev->_next = _head; _head->_prev = prev; delete tail; _size--; } //头删 void pop_front() { Node* head = _head->_next; Node* next = head->_next; _head->_next = next; next->_prev = _head; delete head; _size--; } //任意位置删除 iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; _size--; return iterator(next); }
需要注意的是，任意位置删除因为使用了迭代器，删除后会造成迭代器失效，所以需要更新迭代器，返回被删除节点的下一个节点的迭代器即可。
3.4 拷贝构造
拷贝构造直接将数据一个一个插入到该链表中即可：
list(const list<T>& l) { empty_init(); iterator it = l.begin(); while (it != l.end()) { push_back(*it); it++; } }
这样十分方便快捷！！！
3.5 析构函数
void clear() { //依次释放 iterator it = begin(); while (it != end()) { it = erase(it); } } ~list() { clear(); //需要单独释放头结点空间 delete _head; _head = nullptr; }
3.6 其他函数
返回大小：
size_t size() const { return _size; }
判断是否为空：
bool empty() { return _size == 0; }
清空数据：
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
4 总结
本文我们实现了STL库中重要的list 的模拟实现，其中最重要莫过于迭代器的封装类的书写，这是前所未有的操作（对于我来说，我是第一次使用这种结构）。通过list 的模拟实现也帮我们巩固了类与对象的知识，也强化了指针操作的思路。欢迎大家讨论分析。
