基本结构
首先明确一个问题，list是带头双向循环链表，既然是链表，那么我们就需要定义一个节点的结构体，然后既然是list的模拟实现，就需要定义一个list的类，根据带头双向循环链表的特点，还需要一个头节点，所以list的成员变量中必有一个头节点
下面是基本结构
namespace bit
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _Date;ListNode(const T x=T()){_next=nullptr;_prev=nullptr;_Date=x;}};template<class T>calss list{public:list(){_head=new Node;_head->_next=_head;_head->_prev=_head;}private:typedef ListNode<T> Node;Node* _head;};}上面有一个问题，上面的那个定义节点要用struct,而不用class,原因就是上面的节点里面的任何元素随时都需要访问， 而struct里面的是默认共有的，当然在这里你也可以用calss,只是需要把所有的元素置成公有的
push_back()
向节点的尾部添加一个节点，基本的思路就是找到尾节点，申请新的节点，然后将新的节点连接就行了
void push_back(const T x)
{Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;
}迭代器
今天的这个迭代器会有一点特别，以前在string,vector里面的模拟实现里面，定义一个迭代器都是都是直接typedef一个int*,或者一个char*,让后直接对迭代器进行++或者--，但是，今天的这个是链表，结构在物理上都不是连续的，如何进行++或者--操作，这是不行的，唯一的方法就是对定义一个迭代器的类，然后对++或者--进行操作符的重载
template<class T>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> self;Node* _node;public:ListIterator(Node* node):_node(node){}self&operator++(){_node = _node->_next;return *this;}self operator++(int){self temp(_node);_node = _node->_next;return temp;}self&operator--(){_node = _node->_prev;return *this;}self operator--(int){self temp(_node);_node = _node->_prev;return temp;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}T& operator*(){return _node->_Date;}T* operator->(){return &(_node->_Date);}};这样就可以对链表进行遍历了，当然了，这里的的begin()和end()函数还没有实现，可以在下面完整代码的list里面去查看
上面代码还有一个问题，你迭代器里面去重载一个—>有什么用
主要是为下面的情况做准备的
上面又又同学问了，啊，->这个操作符得出不是pos的地址吗，你这个怎么好直接就能去的出pos里面的成员变量的，其实上面的写法和被注释掉的代码是一样的，这里编译器是为了增强代码的可读性和美观性才这样省略出这样的，
const迭代器
const迭代器和非const迭代器其实是相差不大的，有人可能认为，在iterator前面加上一个const让他变成const iterator不就成为const迭代器了吗，那你就大错特错了
const迭代器是什么？是迭代器里面指向的内容不能被修改，直接加const不久变成迭代器不能被修改了，这里其实代码和非const迭代器是差不多的，唯一有一个地方需要改的就是限制解引用的返回值，让他变成const
template<class T>
class ListConstIterator
{typedef ListNode<T> Node;typedef ListConstIterator<T> self;Node* _node;public:ListConstIterator(Node* node):_node(node){}self&operator++(){_node = _node->_next;return *this;}self operator++(int){self temp(_node);_node = _node->_next;return temp;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s) //记得参数里面加const，如果不加，会出现权限的放大问题{return _node != s._node;}const T& operator*() //加const{return _node->_Date;}const T* operator->() //加const{return &(_node->_Date);}};
两个迭代器合一块
两个迭代器写一块，那不是太麻烦了一点，能不能写一个模板？答案是可以的
只需要在模板参数里面添加两个参数
然后下面函数的返回值稍微改动一下
最后关键的一步来了
在list定义迭代器里面的时候给不同的模板参数就行了
析构函数
~list(){list<T>::iterator it = begin();while (it != end()){it = erase(it);}delete _head;_head = nullptr;}拷贝构造和赋值重载
void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}list<T>& operator=(const list<T> l1)
{empty_init(); //这里记着要初始化swap(_head, l1._head);return *this;
}上面的赋值运算符重载设计得很巧妙，首先明确的一个问题是要使用传值传参，后面直接交换两个_head的指向，因为传值传参会引发拷贝构造函数，后面把_head的指向给l1的拷贝构造了之后函数结束直接析构，这里就有点像让你干活，最后把你给杀了
list(const list<T>& l1)
{empty_init();for (const auto &e : l1){push_back(e);}}这里记得拷贝构造函数需要使用深拷贝，如果你不写拷贝构造函数得话，编译器生成的默认构造函数默认的是浅拷贝，函数调用结束了之后会发生同一块空间析构两次的问题，导致程序崩溃
写代码时的一个易错点
这里写代码的时候老是出现下面的问题：函数匹配问题，这一般都是由于权限的放大缩小问题
还有就是写范围for的时候尽量写引用，因为范围for实际上时赋值给e,赋值的话会拷贝产生一个临时对象，如果auto是自定义类型的话，拷贝量太大了，效率比较低
常规函数
void erase(iterator pos) //迭代器失效，因为被释放了
{Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;pos._node = nullptr;
}void insert(iterator&pos, T x) //迭代器没有失效
{Node* newnode = new Node(x);Node* prev = pos._node->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = pos._node;pos._node->_prev = newnode;
}void pop_back()
{Node* cur = _head->_prev;Node* prev = cur->_prev;prev->_next = _head;_head->_prev = prev;delete cur;
}完整代码
#include<iostream>
using namespace std;
namespace bit
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _Date;ListNode(const T date = T()):_Date(date),_prev(nullptr),_next(nullptr){}};template<class T,class ref,class ptr>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T,ref,ptr> self;public:Node* _node;public:ListIterator(Node* node):_node(node){}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self temp(_node);_node = _node->_next;return temp;}self& operator--(){_node = _node->_prev;return *this;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}ref&operator*(){return _node->_Date;}ptr operator->(){return &(_node->_Date);}};/*template<class T>class ListConstIterator{typedef ListNode<T> Node;typedef ListConstIterator<T> self;Node* _node;public:ListConstIterator(Node* node):_node(node){}self&operator++(){_node = _node->_next;return *this;}self operator++(int){self temp(_node);_node = _node->_next;return temp;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}const T& operator*(){return _node->_Date;}T* operator->(){return &(_node->_Date);}};*/template<class T>class list{public:typedef ListIterator<T, T&,T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//typedef ListConstIterator<T> const_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}iterator end(){return iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list<T>& operator=(const list<T> l1){empty_init();swap(_head, l1._head);return *this;}list(){empty_init();}void push_back(const T x){Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}iterator erase(iterator pos){Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;pos._node = nullptr;return iterator(next);}list(const list<T>& l1){empty_init();for (const auto &e : l1){push_back(e);}}~list(){list<T>::iterator it = begin();while (it != end()){it = erase(it);}delete _head;_head = nullptr;}bool empty(){return _head->_next == _head;}void insert(iterator&pos, T x){Node* newnode = new Node(x);Node* prev = pos._node->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = pos._node;pos._node->_prev = newnode;}void pop_back(){Node* cur = _head->_prev;Node* prev = cur->_prev;prev->_next = _head;_head->_prev = prev;delete cur;}private:typedef ListNode<T> Node;Node* _head;};void test01(){list<int> l1;l1.push_back(10);l1.push_back(20);l1.push_back(30);l1.push_back(40);l1.push_back(50);l1.push_back(60);list<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";it++;}cout << endl;}void func(const list<int>&s){list<int>::const_iterator it = s.begin();while (it != s.end()){//(*it)++;cout << *it << " ";it++;}}void test02(){list<int> l1;l1.push_back(10);l1.push_back(20);l1.push_back(30);l1.push_back(40);func(l1);}struct pos{int _x;int _y;pos(int x=0,int y=0):_x(x),_y(y){}};void test03(){list<pos> p;p.push_back(pos(1,2));p.push_back(pos(3,4));p.push_back(pos(5,6));list<pos>::iterator it = p.begin();//cout << it.operator->()->_x << " " << it.operator->()->_y << endl;cout << it->_x << " " << it->_y << endl;}void test04(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);for (auto &e : l1){cout << e << " ";}cout << endl;list<int> l2 = l1;for (auto& e : l2){cout << e << " ";}cout << endl;}void test05(){list<int> l1;l1.push_back(10);l1.push_back(20);l1.push_back(30);l1.push_back(40);}
}
