一、初始化和各种构造

C++的list类使用的模型是带头双向循环链表：

所以今天我们也是基于这个模型来实现一个list。

1.1、准备工作

在定义链表类之前，我们先要定义链表的节点类：

// list节点类
template <class T>
struct ListNode {// 构造函数ListNode(const T& val = T()) {_val = val;_pre = nullptr;_next = nullptr;}T _val;ListNode<T>* _pre; // 指向前一个节点ListNode<T>* _next; // 指向后一个节点
};

然后就是list类了：

template <class T>
class list {typedef ListNode<T> Node;
public :
private :Node* _head;size_t _size;
};

因为我们所写的是带头链表，所以在list类里就只需要顶一个头节点和size即可。

1.2、各种构造和析构

有了链表类，我们就要先来实现各种构造和析构了。
空初始化
但在开始实现构造之前，我们必须先得实现一个“空初始化”，因为我们设计的链表是带头结点的，并且这个头结点是不算入有效数据的。
所以我们要先将这个头结点申请出来，这也就是空初始化要做的事情：

// 空初始化
void emptyInit() {// 开辟一个头节点Node* newHead = new Node();_head = newHead;_head->_next = _head;_head->_pre = _head;_size = 0;
}

无参构造
无参构造的作用就是只创建一个链表对象，其他什么都不做，所以我们直接调用空初始化即可：

// 无参构造函数
list() {emptyInit();
}

以n个相同值构造
这个其实我们可以直接复用后面写的尾插，直接一直追加即可。
在正式插入之前，我们还是先要处理头节点，即调用空初始化：

// 以n个相同值构造
list(int n, const T& val = T()) {// 先空初始化emptyInit();//  插入for (int i = 0; i < n; i++) {push_back(val);}
}

以一段迭代器区间初构造
这个其实也和其他容器是一样的：

// 以一段迭代器区间初始化
template <class Iterator>
list(Iterator first, Iterator last) {// 先空初始化emptyInit();while (first != last) {push_back(*first);first++;}
}

拷贝构造
对于其他容器而言，链表的拷贝构造我想是最简单的了，因为它的空间本身就不连续，也就不必申请新的一段连续的空间再拷贝数据了。
其实我们直接将两个链表的哨兵位节点交换即可。
所以我们可以先实现一个交换函数：

// 交换
void Swap(list<T>& lt) {swap(_head, lt._head);swap(_size, lt._size);
}

然后我们在构造函数中创建一个临时对象，再将这个对象与我们要构造的对象交换即可：

// 拷贝构造
list(const list<T>& lt) {// 先空初始化emptyInit();// 创建一个临时对象list<T> temp(lt.begin(), lt.end());// 交换即可Swap(temp);
}

析构函数
析构函数，我这里并不想使用以前的方法依次删除节点，我这里打算复用其他的函数。
我们先得要实现一个清数据的函数——只清理有效数据，不清理哨兵头节点：

// 清除数据
void clear() {iterator it = begin();while (it != end()) {it = erase(it);}
}

这里用到的迭代器后面后讲到。

然后在析构函数中，我们只需要调用一次clear然后再将哨兵头节点释放掉即可：

// 析构函数
~list() {clear();delete _head;
}

二、插入和删除

2.1、插入

尾插
尾插其实就和我们以前写的带头双向循环链表一模一样了：

	// 尾插
void push_back(const T& val) {Node* tail = _head->_pre;// 申请一个新节点Node* newNode = new Node(val);tail->_next = newNode;newNode->_pre = tail;newNode->_next = _head;_head->_pre = newNode;_size++;
}

头插

	// 头插void push_front(const T& val) {// 申请新的头节点Node* newHead = new Node(val);// 原来的头节点Node* head = _head->_next;_head->_next = newHead;newHead->_pre = _head;newHead->_next = head;head->_pre = newHead;_size++;}

随机插入
在pos位置之前插入一个新节点，并返回新节点的位置：

iterator insert(iterator pos, const T& val) {// 申请一个新节点Node* newNode = new Node(val);Node* Pre = pos._node->_pre;Node* Next = pos._node;Pre->_next = newNode;newNode->_pre = Pre;newNode->_next = Next;Next->_pre = newNode;_size++;return newNode;
}

2.2、删除

尾删

// 尾删
void pop_back() {assert(!empty());Node* tail = _head->_pre;Node* Pre = tail->_pre;// 释放尾节点delete tail;Pre->_next = _head;_head->_pre = Pre;_size--;
}

头删

// 头删
void pop_front() {assert(!empty());// 旧的头节点Node* head = _head->_next;// 新的头节点Node* newHead = head->_next;// 释放旧的头节点delete head;_head->_next = newHead;newHead->_pre = _head;_size--;
}

随机删除
删除pos位置的节点，并返回被删除节点的下一个节点的位置：

iterator erase(iterator pos) {assert(!empty());Node* cur = pos._node;Node* Pre = cur->_pre;Node* Next = cur->_next;// 释放原来的节点delete cur;Pre->_next = Next;Next->_pre = Pre;_size--;return Next;
}

三、迭代器

因为链表的哨兵头节点是私有的，并且链表也不支持随机访问(不能实现方括号重载)，所以我们遍历链表的方式就只剩一种——迭代器。

3.1、正向迭代器

因为链表的空间不是连续的，所以我们就不能直接用原生指针来模拟了。我们需要对原生指针再进行封装。
并且迭代器的++和–也要通过运算符重载的方式达到：

// list迭代器类
template <class T, class ref, class ptr>
struct ListIterator {typedef ListNode<T> Node;typedef ListIterator<T, ref, ptr> iterator;
public :// 构造函数ListIterator(Node* node = nullptr) {_node = node;}// 拷贝构造ListIterator(const iterator& it) {_node = it._node;}// 星号解引用运算符重载ref operator*() {return _node->_val;}// 箭头解引用运算符重载ptr operator->() {return &_node->_val;}// 前置++运算符重载iterator& operator++() {_node = _node->_next;return *this;}// 后置++运算符重载iterator& operator++(int) {iterator* temp = new iterator(this->_node);++(*this);return *temp;}// 前置--运算符重载iterator& operator--() {_node = _node->_pre;return *this;}// 后置--运算符重载iterator& operator--(int) {iterator* temp = new iterator(this->_node);--(*this);return *temp;}// 等于运算符重载bool operator==(const iterator& it) {return _node == it._node;}// 不等于运算符重载bool operator!=(const iterator& it) {return !((*this) == it);}
public :Node* _node;
};

3.2、反向迭代器

实现反向迭代器我们其实只需要适配正向迭代器即可，因为反向迭代器的逻辑几乎和正向迭代器是一样的，只是在对反向迭代器进行++和–的时候需要和正向迭代器相反：

// list反向迭代器类
template <class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{Iterator _it;typedef Reverse_iterator<Itertor, Ref, Ptr> Self;Reverse_iterator(Iterator it): _it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}
};

3.3、提供迭代器位置

// 正向const迭代器起始位置
const_iterator begin() const
{return const_iterator(_head->_next);
}
// 正向const迭代器结束位置
const_iterator end() const
{return const_iterator(_head);
}// 正向迭代器起始位置
iterator begin()
{return iterator(_head->_next);
}// 正向迭代器结束位置
iterator end()
{return iterator(_head);
}// 反向const迭代器起始位置
const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}// 反向const迭代器结束位置
const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
}// 反向迭代器起始位置
reverse_iterator rbegin()
{return reverse_iterator(end());
}// 反向迭代器结束位置
reverse_iterator rend()
{return reverse_iterator(begin());
}

四、其他一些接口

4.1、链表的长度和判空

// 返回长度size_t size() {return _size;}// 判断是否为空bool empty() {return _size == 0;}

4.2、返回链表的头尾结点

// 返回链表的头一个节点(第一个有效节点的值)T& front() {assert(!empty());return _head->_next->_val;}// const版本的头节点const T& front() const {assert(!empty());return _head->_next->_val;}// 返回链表的尾节点(最后一个有效节点的值)T& back() {assert(!empty());return _head->_pre->_val;}// const版本尾节点const T& back() const {assert(!empty());return _head->_pre->_val;}