目录
前言：
list是STL(标准模板库)中的八大容器之一，而STL属于C++标准库的一部分，因此在C++中可以直接使用list容器存储数据。list实质上是一个带头双向循环链表，这也使得他能够在常数的时间复杂度范围内插入和删除数据，缺点是不能像数组那样进行元素下标的随机访问。
一、模拟实现list
在C++中可以直接调用库里的list，并且使用起来非常的简便，和使用vector、string相差无几，但是为了能够更好的了解list和其底层原理，下文会对lsit的常用接口进行模拟实现，以便对list有更深入的理解，并且list的底层实现逻辑完美的表现了面向对象的思想。
1、list的基本结构
与实现vector和string不一样，list可以分成两个整体：链表本身、节点本身，因此需要两个类（链表类、节点类）完成list的基本实现，并且把节点类看作是一个普通的节点，而实现链表的具体功能函数都放在链表类中。
list基本功能代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
namespace ZH
{
template <class T>
struct list_node//节点类
{
list_node<T>* prev;
list_node<T>* next;
T val;
list_node(const T& t)
:prev(nullptr)
, next(nullptr)
, val(t)
{}
};
template <class T>
class list//链表类
{
public:
typedef list_node<T> node;//让节点类看起来像一个普通的节点
list()//构造函数、目的是创建哨兵位头节点
:_node(new node(-1))
{
_node->next = _node;
_node->prev = _node;
}
void push_front(const T& t)//头插
{
node* newnode = new node(t);
node* cur = _node->next;
_node->next = newnode;
newnode->prev = _node;
newnode->next = cur;
cur->prev = newnode;
}
void Print()//打印数据
{
node* cur = _node->next;
while (cur != _node)
{
cout << cur->val << " ";
cur = cur->next;
}
}
~list()//析构
{
node* cur = _node->next;
node* dest = cur->next;
while (cur != _node)
{
delete cur;
cur = dest;
dest = dest->next;
}
delete _node;
_node = nullptr;
}
private:
node* _node;
};
}
int main()
{
ZH::list<int> lt;
lt.push_front(1);
lt.push_front(2);
lt.push_front(3);
lt.push_front(4);
lt.Print();
return 0;
}运行结果：
从上面的代码可以发现， list的底层实现和之前c语言中实现双向循环链表的逻辑一模一样，只不过用C++的方式将其进行了封装。
这里节点类里的成员变量要放在公有域（struct定义类默认为公有域），因为在list中会改变节点前后指针的指向，因此节点的指针要设为外部可见。
2、迭代器封装
2.1 正向迭代器
在调用库里面的list，会发现库里面list的迭代器用起来像是一个指针，因为可以对迭代器进行解引用操作以及++操作。所以在模拟实现迭代器时，我们也用一个指针来模拟迭代器的行为，不同的是指针进行++操作时，会指向该地址的下一个地址，而我们期望的迭代器++可以指向下一个节点。
示意图如下：
因此，如果单单的把指针看成迭代器则无法实现遍历链表的功能，所以要实现迭代器必须对指针进行又一层的封装，也就是把迭代器写成一个类，但是该类的底层还是一个节点指针，只是对该指针的操作有了新的规定。
正向迭代器代码实现如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
namespace ZH
{
template <class T>
struct list_node//节点类
{
list_node<T>* prev;
list_node<T>* next;
T val;
list_node(const T& t)
:prev(nullptr)
, next(nullptr)
, val(t)
{}
};
template<class T>
struct list_iterator//迭代器类
{
typedef list_node<T> node;
typedef list_iterator<T> self;
node* _node;// 成员变量
list_iterator(node* node)
:_node(node)
{}
bool operator!=(const self& s)//重载！=
{
return _node != s._node;
}
self& operator++()//重载前置++
{
_node = _node->next;
return *this;
}
T& operator*()//重载解引用
{
return _node->val;
}
};
template <class T>
class list//链表类
{
public:
typedef list_node<T> node;//让节点类看起来像一个普通的节点
typedef list_iterator<T> iterator;//让迭代器类看起来像一个迭代器
list()//构造函数、目的是创建哨兵位头节点
:_node(new node(-1))
{
_node->next = _node;
_node->prev = _node;
}
void push_front(const T& t)//头插
{
node* newnode = new node(t);
node* cur = _node->next;
_node->next = newnode;
newnode->prev = _node;
newnode->next = cur;
cur->prev = newnode;
}
iterator begin()
{
//begin返回的是一个指向头节点的下一个节点的迭代器对象
return iterator(_node->next);//匿名对象创建并返回
}
iterator end()
{
//begin返回的是一个指向头节点的迭代器对象
return iterator(_node);//匿名对象创建并返回
}
~list()//析构
{
node* cur = _node->next;
node* dest = cur->next;
while (cur != _node)
{
delete cur;
cur = dest;
dest = dest->next;
}
delete _node;
_node = nullptr;
}
private:
node* _node;//指向哨兵位的头节点
};
}
int main()
{
ZH::list<int> lt;
lt.push_front(1);
lt.push_front(2);
lt.push_front(3);
lt.push_front(4);
ZH::list<int>::iterator it = lt.begin();
while (it!=lt.end())
{
cout << *it << " ";
++it;
}
return 0;
}运行结果：
注意，这里的it要看成是一个对象，他的类型是 list<int>::iterator。ZH::list<int>::iterator it = lt.begin();这句代码实际上是调用了拷贝构造，用begin（）的返回对象构造了一个新的对象it。
2.2 反向迭代器
反向迭代器与正向迭代器的区别在于，反向迭代器是从链表的最后一个节点开始往前遍历的，并且他的逻辑和正向迭代器的逻辑是相反的，可以确定的一点是反向迭代器也是通过一个类来实现的。
反向迭代器实现代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
namespace ZH
{
template <class T>
struct list_node//节点类
{
list_node<T>* prev;
list_node<T>* next;
T val;
list_node(const T& t)
:prev(nullptr)
, next(nullptr)
, val(t)
{}
};
template<class T>
struct list_iterator//迭代器类
{
typedef list_node<T> node;
typedef list_iterator<T> self;
node* _node;// 成员变量
list_iterator(node* node)
:_node(node)
{}
bool operator!=(const self& s)//重载！=
{
return _node != s._node;
}
self& operator++()//重载前置++
{
_node = _node->next;
return *this;
}
self& operator--()//重载前置--
{
_node = _node->prev;
return *this;
}
T& operator*()//重载解引用
{
return _node->val;
}
};
template<class T>
class list_reverse_iterator
{
public:
typedef list_iterator<T> iterator;
typedef list_reverse_iterator<T> rself;
list_reverse_iterator(iterator it)
:rit(it)
{}
bool operator!=(const rself& s)//重载！=
{
return rit!= s.rit;//复用正向迭代器的！=重载
}
rself& operator++()//重载前置++
{
--rit;//复用正向迭代器的++
return *this;
}
T& operator*()//重载解引用
{
return *rit;//复用正向迭代器的解引用
}
private:
iterator rit;
};
template <class T>
class list//链表类
{
public:
typedef list_node<T> node;//让节点类看起来像一个普通的节点
typedef list_iterator<T> iterator;//让迭代器类看起来像一个迭代器
typedef list_reverse_iterator<T> reverse_iterator;
list()//构造函数、目的是创建哨兵位头节点
:_node(new node(-1))
{
_node->next = _node;
_node->prev = _node;
}
void push_front(const T& t)//头插
{
node* newnode = new node(t);
node* cur = _node->next;
_node->next = newnode;
newnode->prev = _node;
newnode->next = cur;
cur->prev = newnode;
}
reverse_iterator rbegin()
{
return reverse_iterator(iterator(_node->prev));//返回最后一个节点
}
reverse_iterator rend()
{
return reverse_iterator(iterator(_node));//返回头节点
}
~list()//析构
{
node* cur = _node->next;
node* dest = cur->next;
while (cur != _node)
{
delete cur;
cur = dest;
dest = dest->next;
}
delete _node;
_node = nullptr;
}
private:
node* _node;//指向哨兵位的头节点
};
}
int main()
{
ZH::list<int> lt;
lt.push_front(1);
lt.push_front(2);
lt.push_front(3);
lt.push_front(4);
ZH::list<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
cout << *rit << " ";
++rit;
}
return 0;
}运行结果：
从上述代码中可以发现，反向迭代器是复用正向迭代器的成员函数达到实现的，只不过在反向迭代器类里进行又一层包装。
3、指定位置插入
有了迭代器，就可以实现从指定位置插入了，指定位置插入代码如下：
void Insert(iterator pos, const T& val)//插入
{
node* newnode = new node(val);
node* cur = pos._node;
node* prev = cur->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = cur;
cur->prev = newnode;
}值得注意的是，list的插入不会导致迭代器失效，因为即使在该迭代器指向节点的前面插入一个数据，则该迭代器还是指向该节点的。
4、指定位置删除
指定位置删除代码如下：
void Erase(iterator pos)//删除
{
assert(pos != end());
node* cur = pos._node;
node* prev = cur->prev;
node* next = cur->next;
prev->next = next;
next->prev = prev;
delete cur;
}删除逻辑示意图：
删除与插入不同在于，删除之后迭代器会失效，因为此时it指向的是一块被回收的区域，不能直接访问it所指向的区域，会导致野指针问题。
5、结语
以上就是关于list如何实现的讲解，list的模拟实现完全体现了面向对象的思想，链表本身、节点以及迭代器都被封装成一个类，从用户的角度看，是在对象的层面上直接进行操作的，但是底层却是各种复用，依旧是通过操作内置类型来实现上层的对象之间的操作。
最后希望本文可以给你带来更多的收获，如果本文对你起到了帮助，希望可以动动小指头帮忙点赞👍+关注😎+收藏👌！如果有遗漏或者有误的地方欢迎大家在评论区补充，谢谢大家！！
