单链表
我们日常接触最多的就是单链表。
其优点很明显，增删改很方便。
但非连续存储的方式，导致了我们随机访问第i个元素的时候必须从头遍历，时间复杂度为O(N)
所以单链表比较合适于以下频繁的场景：
- 插入/删除
- 遍历
但不适用于随机访问频繁的场景。
list的实现——基于双向循环链表
这个我们之前也提及过：
添加链接描述
我们之前说list列表基于双向链表实现，但没说细节，我们首先来看一下node的情况：既然是双向链表，很明显会有前后两个指针和一个val值。
template <class T>
struct __list_node {
__list_node<T>* next; // 前驱节点指针
__list_node<T>* prev; // 后继节点指针
T data; //存储数据
};
我们之前还说指针迭代器的问题，我们来看一下迭代器具体怎么实现的：
template<typename T>
struct __list_iterator{
typedef __list_iterator<T> self;
typedef __list_node<T>* link_type;
link_type ptr; //成员
__list_iterator(link_type p = nullptr):ptr(p){}
}
T& operator *(){return ptr->data;}
T* operator ->(){return &(operator*());}
// 类似 ++x 返回next节点
self& operator++(){
ptr = ptr->next;
return *this;
}
// 类似 x++ 返回当前节点
self operator++(int){
self tmp = *this;
++*this;
return tmp;
}
// 类似 --x 返回prev节点
self& operator--(){
ptr = ptr->prev;
return *this;
}
// 类似 x-- 返回当前节点
self operator--(int){
self tmp = *this;
--*this;
return tmp;
}
bool operator==(const __list_iterator& rhs){
return ptr == rhs.ptr;
}
bool operator!=(const __list_iterator& rhs){
return !(*this==rhs);
}
注意重载++和–的时候，默认是后置，如果要重载前置需要添加&符号。
后置返回的都是先保存当前节点，改变this指针后返回当前节点。
而前置只需要移动当前指针而后返回即可。
我们可以看见迭代器，主要是对ptr这个成员变量进行处理。
具体实现list：
template<typename T>
class list{
protected:
typedef __list_node<T> list_node; // 显示定义list_node类型
typedef allocator<list_node> nodeAllocator; // 定义allocator类型
public:
typedef T value_type;
typedef T& reference;
typedef value_type* pointer;
typedef list_node* link_type;
typedef const value_type* const_pointer;
typedef size_t size_type;
public:
typedef __list_iterator<value_type> iterator; // 迭代器类型重写
private:
link_type node; // 只要一个指针，便可表示整个环状双向链表
// ......
}
我们看private里的node指针，我们知道在单链表里，我们习惯用dummy node来表示一个虚拟的头部，这里我们用虚拟节点node来标识循环链表的首位连接点,其pre为最后一个节点，其next为第一个节点。
初始化的时候，只会有一个node节点，其pre和next都指向自己。
list的初始化/插入/删除
初始化：包含一个虚拟的节点node，其首尾都指向自己
void empty_initialize() {
node = get_node(0);
node->next = node; // next 指针指向自身
node->prev = node; // prev 指针指向自身
}
link_type get_node() { return list_node_allocator:allocate(); }
insert函数：传参需要两个，一个val和一个迭代器以表明插入位置：
这需要做到：
- 创建一个临时节点temp
- 使temp的pre&next正确指向
- 使原来pre的next指向temp，使原来next的pre指向temp
iterator insert(iterator position, const T& x) {
lik_type tmp = create_node(x); // 创建一个临时节点
tmp->next = position.node; // 将该节点的后继指针指向当前位置的节点
tmp->prev = position.node->prev; // 将该节点的前驱指针指向当前位置的前驱节点
(link_type(position.node->prev))->next = tmp; // 将前驱节点本来指向当前节点的后继指针改为指向该临时节点
position.node->prev = tmp; // 同样，当前位置的前驱指针也要修改为指向该临时节点
return tmp;
}
这在我们刷题的时候也经常用到：
穿针引线法：
注意一定要先把新节点的指针指上去之后，再把旧节点的指针指过来
我们再看删除erase：
iterator erase(iterator position) {
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(position.node);
return iterator(next_node);
}
先将前后节点连在一块儿，再释放待删除节点。
有了Insert和erase，我们可以用这两个函数以及begin&end这两个迭代器，实现pop_front/pop_back/push_back，思路是在指定位置进行insert/erase
（注意begin节点指向虚拟节点的next，即第一个node。而end指向虚拟节点，即最后一个node的next）
比如：
void pop_front() {erase(begin())};
void pop_back() {
iterator temp=end();
erase(--temp);//注意要先--temp，因为end指向虚拟节点，并不是最后一个node
}
push_back(const T&x) {insert(end(),x);}
注意pop_back()要先–temp，因为end指向虚拟节点，并不是最后一个node