在模拟实现了vector以后，下一个我们应该学习的就是C++ 中自带的链表结构 list 了。在我们实现vector的时候，发现vector的实现和传统的顺序表还是有差别的。那么我们今天要实现的list也会和以前实现的链表有很大的差别吗？本篇博客将从头开始实现List 的核心成员函数。
list 在STL库中实现的是一个双向带头循环链表，这样可以多提供很多操作。
1. 节点
链表最基础的结构就是节点了，是先有的节点，然后才有的链表。所以首先，我们要先从节点入手。既然是双向带头循环链表，所以我们的节点应该是三个成员变量，两个指针指向前面和后面，还有一个存储数据的变量。
同样，我们在自己实现 list 的时候也要记得把自己实现的list放在一个单独的命名空间内，防止和STL的 list 混淆。
构建好节点类的时候不要忘记给节点类写一个构造函数。
namespace my_list
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& data = T())
:_data(data)
,_next(nullptr)
,_prev(nullptr)
{}
};
}2. 迭代器
在实现完节点类以后，还是先从迭代器开始实现。但是 list 的迭代器和其他类类型的迭代器不一样。其他类型的迭代器我们只需要对它进行 ++ / -- 就可以拿到下一个位置的值，但是 list 不可以。list 是链表结构，我们知道链表结构在内存空间里是不一定连续的，所以我们没办法通过类似于++ / -- 的这种方式获取到下一个位置的节点。所以这里我们要实现迭代器就不能只是一个单纯的指针，而要对这个迭代器进行封装，并且重载它的运算符。
如果我们要封装一个迭代器，并且让自己实现的list类能够访问它，那么最好的方法就是创建一个结构体，因为结构体的成员默认都是公有的，这样实现起来很比较方便。当然，这里用类实现并且将成员设为公有也是可以的。
在正式实现迭代器之前，我们要先思考一个问题。我们为了让类中对数据更好的进行读写，我们希望对迭代器解引用的时候可以对该节点进行读写，那么我们对运算符进行重载的时候就应该返回该节点的引用。但是由于我们要实现普通迭代器和 const 迭代器两种类型，我们在给运算符重载写返回值的时候就会出现冗余的代码。也就是除了这个重载以外，剩下的重载都是一模一样的。由此我们可以在类模板中多加入一个参数，用于表示函数的引用，在写返回值的时候用这个新的参数来写，就可以不用多写那么冗余的代码。下面看例子可以更好的理解这一点。
我们写构造函数的时候
//这里我们对这个模板设置两个参数 并且设置一个重载
//我们传const迭代器的时候就会返回const迭代器的版本
//传普通迭代器的时候就会传普通的版本
template<class T, class Ref>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
// Ref就是T类型的引用
Ref operator*()
{
return _node->_data;
}
//迭代器++就是找下一个节点
Self& operator++()
{
_node = _node->_next;
return *this;
}
//迭代器--就是找上一个节点
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//前置++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
//前置--
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
//判断节点是否相等
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
}3. list 类实现
3.1 默认成员函数
在实现函数之前，先把前面写的迭代器和节点类 typedef 一下 ，方便后面写起来比较简单。
成员变量只需要一个头节点的指针和一个长度就足够了。
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&> iterator;
typedef list_iterator<T, const T&> const_iterator;
private:
Node* _head;
size_t _size;
}3.1.1 构造函数
默认成员函数里我们就先来实现构造函数，由于 list 是一个带头双向循环链表，所以我们的构造函数肯定是要构造出一个头节点。不止是构造函数要用，后面的拷贝构造等都需要这个函数，所以我们单独把这个函数写出来。
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}3.1.2 析构函数
析构函数就是需要我们把每一个节点都释放掉，最后再释放头节点。
~list()
{
auto it = begin(); // begin 和 end 后面实现
while (it != end())
{
it = erase(it);//erase 也放到后面实现
}
delete _head;
_head = nullptr;
}3.1.3 拷贝构造函数
拷贝构造只需要先创建一个头节点，然后将节点依次遍历加进去就可以了。
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e); //后面实现push_back
}
}3.1.4 赋值重载
赋值重载依旧是用老方法，这里的swap我们只需要交换头节点和大小就可以了。
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}3.2 迭代器相关函数
这里我们直接返回成员变量，通过隐式类型转换就会转成迭代器。
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}3.3 修改list的函数
3.3.1 insert
在pos位置前插入一个新节点我们应该很熟悉了，先创建一个新节点，并且记录下当前节点和前一个节点。先把新节点的链接到两个节点上，再把两个节点的一前一后指针指向新的节点。先链接新节点是为了不会丢失以前的节点。
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
return newnode;
}3.3.2 push_back 和 push_front
这两个函数其实就是在头节点的一前一后插入数据，所以我们可以复用insert。
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}3.3.3 erase
删除节点想必大家也不会陌生，就是先记录被删除节点的前后两个节点，然后让这两个节点连接上，最后再释放被删除的节点就好了。
iterator erase(iterator pos)
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}3.3.4 pop_back 和 pop_front
头删和尾删也还是头节点的前后两个节点删除，所以我们可以复用erase
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}