目录
1.list的概述
list的底层是
双向链表结构
，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指
针指向其前一个元素和后一个元素。它的优点是每次插入或删除一个元素，就配置或释放一个元素的空间。所以对于空间的管理比较精准，一点也不浪费。而且对于任何的元素插入或删除，它的
时间复杂度为O（1）
，非常高效。
2.list的节点
list本身与list的节点是不同的结构，需要分开设计。
template<class T>
struct _list_node//定义节点
{
_list_node(const T& val=T())
:_val(val)
,_prev(nullptr)
,_next(nullptr)
{
}
T _val;//存储数据
_list_node<T>* _next;//存储下一个节点的地址
_list_node<T>* _prev;//存储上一个节点的地址
};
?显然这是一个双向链表
3.list的迭代器
list不能够像vector一样以普通指针作为迭代器，因为它的节点不能保证在空间上的地址是连续存在的，迭代器的特点是需要能够像指针一样递增，递减，取值等操作，所以我们设计list迭代器需要用一个类来进行包装设计。
以下是list迭代器的主要设计：
//定义三个模板参数是为了让下面的list链表对const和非const实例化出两种不同类型的迭代器
template<class T,class Ref,class Ptr>
struct _list_iterator
{
typedef _list_node<T>node;//将_list_node<T>类型起一个node的名字
typedef _list_iterator<T,Ref,Ptr> self;
node* _pnode;//指向list节点的指针
_list_iterator(node* pnode)//迭代器的构造函数
:_pnode(pnode)
{
}
//拷贝构造、operator、析构我们不写，编译器生成可以用
Ref operator* ()//迭代器取值，取得是节点内的值
{
return _pnode->_val;
}
Ptr operator->()
{
return &_pnode->_val;
}
bool operator !=(const self& s)const//判断节点的地址不相等
{
return _pnode != s._pnode;
}
bool operator ==(const self& s)const//判断节点的地址相等
{
return _pnode == s._pnode;
}
self operator++()//对迭代器进行加1，前进一个节点
{
_pnode = _pnode->_next;
return _pnode;
}
self operator++(int)//后置加加
{
self tmp(this->_pnode);
_pnode = _pnode->_next;
return tmp;
}
self operator--()//对迭代器进行减1，后退一个节点
{
_pnode = _pnode->_prev;
return _pnode;
}
self operator--(int)//后置减减
{
self tmp(this->_pnode);
_pnode = _pnode->_prev;
return tmp;
}
};?4.list的数据结构
接下来我要设计的list结构不仅是双向链表，而且是带头双向循环链表
什么是带头双向循环链表？
首先链表分为：单/双， 循环不循环，带头/不带头，上面可以两两组合，所以总共有8种链表，所以我们来看每种特殊链表是怎样的。
双向链表：每个节点可以存储两个地址，使链表看起来具有双向结构
?
?循环链表：最后一个节点存储第一个节点的地址，使链表成一个循环结构
?带头链表：
带头节点就是多一个哨兵位节点，这个节点不是用来存储数据，是用来存储第一个节点的地址。
?带头双向循环链表：
?结合上面的节点和迭代器的设计，list的实现如下：
template<class T>
class list
{
public:
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;//命名
typedef _list_node<T> node;
list()//链表的构造函数，创建一个哨兵位节点出来
{
//_head = new node(T());
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list(const list<T>& lt)//拷贝构造函数
{
_head = new node;//创建一个新的哨兵为节点
_head->_next = _head;
_head->_prev = _head;
for (auto& e : lt)//取出lt链表中的值,然后插入到新链表中
{
push_back(e);
}
}
//链表t是由拷贝构造函数构造出来的临时变量，
//与原本链表的哨兵位节点进行交换即交换整个链表
//离开函数后，t的生命周期就结束，就会去调用析构函数销毁掉
list<T> operator=(list<T> t)
{
swap(_head, t._head);
return *this;
}
iterator begin() //返回的链表中第一个节点的地址
{
return iterator(_head->_next);
}
const_iterator begin()const //const类型的迭代器
{
return const_iterator(_head->_next);
}
iterator end()//返回哨兵位节点的地址
{
return iterator(_head);
}
const_iterator end()const//const类型的迭代器
{
return const_iterator(_head);
}
void clear()//清掉所有节点，除了哨兵位节点
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}
}
~list()
{
clear();//先清掉所有节点
delete _head;//再清掉哨兵位节点
_head = nullptr;
}
size_t size()//返回链表中有多少个值
{
iterator it = begin();
size_t sz = 0;
while (it != end())
{
sz++;
it++;
}
}
private:
node* _head;
};
注意：const类型list会自动调用const类型的迭代器，非const类型的list会自动调用非cosnt的迭代器。?
?链表中的end（）和begin（）的位置：如下
a.插入节点
void insert(iterator pos, const T& x)//在pos位置插入一个节点
{
node* newnode = new node(x);//创建一个新节点，会调用node的构造函数
//调整双向指针，使newnode到链表里去
node* prev = pos._pnode->_prev;
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = pos._pnode;
pos._pnode->_prev = newnode;
}在pos位置之前插入一个4的节点：
保存pos位置的上一个节点地址，将新节点与pos位置的节点和上一个节点进行互相连接即可。
void push_back(const T& x)//在链表的最后一个位置插入节点
{
insert(end(), x);
}
void push_Front(const T& x)//在链表的第一个位置插入节点
{
insert(_head->_next,x);
}b.删除节点
iterator erase(iterator pos)//在pop位置删除掉一个节点
{
assert(pos._pnode );
assert(pos != end());
node* prev = pos._pnode->_prev;//保存上一个节点的地址
node* next = pos._pnode->_next;//保存上一个节点的地址
delete pos._pnode;//删除节点
//互相连接
prev->_next = next;
next->_prev = prev;
return iterator(next);//在返回下一个节点的地址
}删除pos位置的节点，先保存pos位置的上一个节点和下一个节点地址，然后删除掉pos位置的节点，再把上一个节点和下一个节点连接起来。?为了防止迭代器失效，在返回下一个节点的地址。
void pop_front()//删除第一个节点
{
erase(_head->_next);
}
void pop_back()//删除最后一个节点的值
{
erase(_head->_prev);
}
void clear()//清掉所有节点，除了哨兵位节点
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}
}
~list()
{
clear();//先清掉所有节点
delete _head;//再清掉哨兵位节点
_head = nullptr;
}
点个赞呗~