一、list模拟实现思路
list链表的模拟实现，与前面的string和vector相比，略复杂一点：
（1）由于链表节点本身就是一个结构体，包含数据域、指针域。 将节点的相关操作放入节点类进行处理，逻辑更清晰
（2）string和vector的元素在空间上是连续分布的，迭代器++就能指向下一个元素，但list的迭代器不行，它的每个元素在空间上都不连续，要访问下一个节点必须找到当前节点的next，因此list的迭代器必须重写
链表主要模拟实现以下功能：
为了和库里面的list区分开，使用命名空间delia将 list类和库里list隔离开
1. namespace delia 2. { 3. }
二、节点类的实现
节点类的成员变量有3个：
（1）节点值_val
（2）指向前一个节点的指针_prev
（3）指向后一个节点的指针_next
节点无需拷贝构造、赋值运算符重载，由于没有额外申请空间，因此也不需要析构
1. template<class T> 2. struct _list_node 3. { 4. //3个成员变量 5. T _val; 6. _list_node<T>* _next; 7. _list_node<T>* _prev; 8. 9. //构造函数 10. _list_node(const T& val = T()) 11. :_val(val) 12. , _prev(nullptr) 13. , _next(nullptr) 14. {}; 15. };
三、list迭代器的实现
由于节点的指针原生行为不满足迭代器定义，在这里，迭代器通过类来封装节点的指针重载运算符，如operator*、operator->、operator++等。用迭代器封装节点指针的思路不关心容器底层结构是数组、链表还是树等数据结构，都封装隐藏了底层细节，可以用一种统一的方式去访问、修改容器。
迭代器分为普通迭代器和const迭代器，对于_list_iterator类要实现两个版本，一个是普通的_list_iterator，另一个是const版本的_list_const_iterator，区别在于：对于两个类中的部分函数有普通函数和const函数之分（如begin( )和end( )），其他并无区别。因为这两个类的大部分代码相似，会造成代码冗余，如何解决呢？
对于T&，类模板实例化出两个类，一个是T&类，一个是const T&类，同理，T*也一样。使用
template<class T,class Ref,class Ptr>
类模板就会实例化出来两个类，一个是普通的不带const的T，T&， T*，另一个是带const的T，const T&， const T*，其中Ref是引用，Ptr是指针，该类模板实例化了以下这两个类模板：
1. template _list_iterator<T, T&, T*> _iterator; 2. template _list_iterator<T, const T&, const T*> const_iterator;
这就解决了需要写两个类的问题。
1._list_iterator类
迭代链表的节点，只需要一个成员变量即节点
1. template<class T,class Ref,class Ptr> 2. struct _list_iterator//使用_list_iterator类来封装node* 3. { 4. typedef _list_node<T> node; 5. typedef _list_iterator<T,Ref,Ptr> self; 6. 7. node* _pnode;//成员变量 8. }
2.构造函数
只需要初始化节点即可
1. //构造函数 2. _list_iterator(node* pnode) 3. :_pnode(pnode) 4. {}
拷贝构造、赋值运算符重载、析构函数，编译器默认生成即可
3.operator* 运算符重载
1. //解引用，返回左值，是拷贝，因此要用传引用返回 2. Ref operator*() 3. { 4. return _pnode->_val; 5. }
4.operator-> 运算符重载
1. //结构体指针解引用，返回节点值的指针 2. Ptr operator->() 3. { 4. return &_pnode->_val; 5. }
5.operator!= 运算符重载
1. //!=重载 2. bool operator!=(const self& s) const 3. { 4. return _pnode != s._pnode; 5. }
6.operator==运算符重载
1. //==重载 2. bool operator==(const self& s) const 3. { 4. return _pnode == s._pnode; 5. }
7.前置++
让迭代器走到下一个节点
1. //前置++ it.operator(&it) 2. self& operator++() 3. { 4. _pnode = _pnode->next; 5. return *this; 6. }
8.后置++
1. //后置++ 返回++之前的值 it.operator(&it,0) 2. self operator++(int)//需构造临时对象，临时对象不能用引用返回，所以self没有加& 3. { 4. self tmp(*this); 5. _pnode = _pnode->_next; 6. return tmp; 7. }
9.前置--
让迭代器走到前一个节点
1. //前置-- it.operator(&it) 2. self& operator--() 3. { 4. _pnode = _pnode->prev; 5. return *this; 6. }
10.后置--
1. //后置-- 返回--之前的值 it.operator(&it,0) 2. self operator--(int)//需构造临时对象，临时对象不能用引用返回，所以self没有加& 3. { 4. self tmp(*this); 5. _pnode = _pnode->_prev; 6. return tmp; 7. }
四、list类的实现
1.list类
list的成员只需要一个头节点，通过迭代器访问其他节点元素
1. template<class T> 2. class list 3. { 4. typedef _list_node<T> node; 5. public: 6. typedef _list_iterator<T,T&,T*> iterator;//重命名迭代器 7. typedef _list_iterator<T, const T&, const T*> const_iterator;//重命名const迭代器 8. private: 9. node* _head; 10. };
2.构造函数
1. list() 2. { 3. _head = new node;//会调_list_node的构造函数 4. _head->_next = _head;//整个链表只有头节点，先构造一个没有实际节点的链表 5. _head->_prev = _head;//整个链表只有头节点，先构造一个没有实际节点的链表 6. }
3.拷贝构造
创建一个空链表，再把参数链表节点的值一个一个尾插进去
1. //拷贝构造 lt1(lt) 2. list(const list<T>& lt) 3. { 4. //1.先构造一个只有头节点的空list：创建头节点，头节点的前一个是自己，头节点的后一个是自己 5. _head = new node; 6. _head->_next = _head; 7. _head->_prev = _head; 8. 9. //2.将lt的元素全部尾插到新链表 10. for (const auto& e : lt) 11. { 12. push_back(e); 13. } 14. }
4.赋值运算符重载
（1）传统的赋值运算符重载
1. //赋值运算符重载 lt1 = lt 传统写法 2. list<T> operator=(const list<T>& lt) 3. { 4. //链表已存在，只需将节点尾插进去即可 5. if(this != lt) 6. { 7. for (auto& e : lt) 8. { 9. push_back(e); 10. } 11. } 12. }
（2）现代的赋值运算符重载
1. list<T> operator=(list<T>& lt) 2. { 3. swap(_head, lt->_head); 4. return *this; 5. }
其中，swap( )函数的执行过程如下：
1. template <class T> void swap ( T& a, T& b ) 2. { 3. T c(a); a=b; b=c; 4. }
在执行赋值运算符重载时，会调用拷贝构造函数执行深拷贝，然后再交换两个链表头节点的指针，把this要释放的资源交给临时对象，临时对象出了swap的函数作用域就被this要释放的资源也会被同时释放。
5.析构
（1）清除所有节点内容
（2）删除头节点，链表就销毁了
1. //析构 2. ~list() 3. { 4. clear();//先清除所有节点内容 5. delete _head;//再删除头节点 6. _head = nullptr; 7. }
6.迭代器
（1）普通迭代器
1. iterator begin() 2. { 3. return iterator(_head->_next);//头节点不存数据 4. } 5. 6. iterator end() 7. { 8. return iterator(_head);//尾节点的下一个节点位置即头节点 9. }
（2）const迭代器
1. const_iterator begin() const 2. { 3. return const_iterator(_head->_next);//头节点不存数据 4. } 5. 6. const_iterator end() const 7. { 8. return const_iterator(_head);//尾节点的下一个节点位置即头节点 9. }
7.insert( )
（1）构造节点
（2）双向带头循环链表插入节点
1. //插入节点 2. void insert(iterator pos, const T& x) 3. { 4. assert(pos._pnode); 5. node* newnode = new node(x);//构造节点 6. 7. node* prev = pos._pnode->_prev;//为方便后续操作，给插入位置的前一个节点起了个名字，pos是迭代器对象 8. 9. //插入节点 10. newnode->_next = pos._pnode; 11. pos._pnode->_prev = newnode; 12. prev->_next = newnode; 13. newnode->_prev = prev; 14. 15. }
8.erase( )
（1）删除节点
（2）更新指针指向
1. //删除节点 2. iterator erase(iterator pos) 3. { 4. assert(pos._pnode);//判断该位置节点是否存在 5. assert(pos != end());//end()是最后一个节点的下一个节点位置，也就是头节点，头节点不能删，需要断言 6. 7. node* prev = pos._pnode->_prev;//pos位置节点的前一个节点 8. node* next = pos._pnode->_next;//pos位置节点的后一个节点 9. 10. //删除节点 11. delete pos._pnode; 12. prev->_next = next; 13. next->_prev = prev; 14. 15. return iterator(next);//删除之后pos失效，把下一个位置的迭代器给它 16. }
