C++_list简单源码剖析：list模拟实现

大家好！本文会用C++模拟一个基本的list类，帮助我们更好的理解list的内置函数的实现与规则。

list是带头双向循环链表，在C语言实现一个链表时，我们通常会实现两个结构体，List 与 ListNode,也就是封装了List的本体与List的节点，在C++模拟实现list也是如此，我们需要实现List与ListNode两个模板。

🚀1. ListNode模板

回忆C语言的链表节点封装，大致其实现为：

struct listnode
{
   
	listnode* next;
	listnode* prev;
	int val;
};

由此，ListNode的内容是比较简单，我们先行封装ListNode，以模板的形式实现，其成员变量只有一个val与两个指针：指针一个指向前节点，一个指向后节点，val就是存储的数据：

template<class T>
struct ListNode
{
   
	ListNode<T>* _prev;
	ListNode<T>* _next;
	 
	T _val;
	//构造函数
	ListNode(const T& val = T()) :
		_prev(nullptr),
		_next(nullptr),
		_val(val)
	{
   

	};
};

备注：

1. 关于使用struct的原因：在C++中，如果一个类的成员变量全都是需要公开被访问的，我们通常使用struct不用class。我们封装ListNode，实际上是在List类中进行操作的，为了List能更方便的实现ListNode访问上下节点的操作，ListNode的成员必须的public的。
   注: struct默认的所有成员是public，class默认的所有成员是private。
2. 关于 const T& val = T()在 C++_vector简单源码剖析：vector模拟实现 中⚡️内置类型也有构造函数 这里有说明，其实就是为了当T是内置类型(int , double)的时候，能顺利初始化val。

🚀2. List_iterator模板(重要)

Listiterator就是list的迭代器，提问🎤：在list类的封装中，能不能直接这么定义迭代器？->

template<class T>
class List
{
   
public:
	typedef ListNode<T> Node;
	typedef Node* iterator;
}

📜答案：不能，为什么🤔？在 C++_vector简单源码剖析：vector模拟实现 中，实现vector的迭代器似乎就是这样实现的，为什么到了list就不行了？
💡解释：
那要如何实现？既然默认的++或者–并不是我们所需要的，那么我们就要自己定义这些行为，这里就需要封装一个Listiterator模板，用一个类来封装ListNode与它的一些行为：

//List的迭代器模板
template<class T, class str, class ptr>
struct Listiterator
{
   
	typedef ListNode<T> Node;
	typedef Listiterator<T, str, ptr> Self;
	Node* _node;

	//迭代器的构造函数
	Listiterator(Node* pNode = nullptr);
	Listiterator(const Self& l);
	
	// ListNode的一些行为
	//前置++重载，当前节点到下一个节点
	Self operator++();
	//后置++重载，当前节点到下一个节点
	Self operator++(int);
	//前置--重载，当前节点到上一个节点
	Self operator--();
	//后置--重载，当前节点到上一个节点
	Self& operator--(int);
	//解引用重载
	str operator*();
	//->重载
	ptr operator->();
	//!=重载
	bool operator!=(const Self& l);
	//==重载
	bool operator==(const Self& l);
};

📈备注：

1. 在List模板中会实例化两个版本的迭代器，一个iterator，一个const_iterator, str会传入 T& 与 const T&，ptr会传入T与const T * 。
2. Listiterator的内容只有一个成员变量ListNode和它的一些行为，这样的过程叫做封装

🌱2.1 List_iterator的构造函数

typedef ListNode<T> Node;
typedef Listiterator<T, str, ptr> Self;
	Node* _node;
//迭代器的构造函数
Listiterator(Node* pNode = nullptr){
   
	_node = pNode;
}
Listiterator(const Self& l) {
   
	_node = l._node;
}

📈备注：构造一个迭代器，让其成员ListNode = 传入的ListNode 。

🌱2.2 List_iterator的关于ListNode的行为

	typedef ListNode<T> Node;
	typedef Listiterator<T, str, ptr> Self;
	Node* _node;
//前置++重载，当前节点到下一个节点
Self operator++()
{
   
	_node = _node->_next;
	return *this;
};
//后置++重载，当前节点到下一个节点
Self operator++(int) {
   
	Node* tmp = _node;
	_node = _node->_next;
	return tmp;
};
//前置--重载，当前节点到上一个节点
Self operator--()
{
   
	_node = _node->_prev;
	return *this;
};
//后置--重载，当前节点到上一个节点
Self& operator--(int) {
   
	Node* tmp = _node;
	_node = _node->_prev;
	return tmp;
};
//解引用重载
str operator*()
{
   
	return _node->_val;
};
//->重载
ptr operator->()
{
   
	return &*this;
};
//!=重载
bool operator!=(const Self& l) {
   
	return l._node !=_node;
};
//==重载
bool operator==(const Self& l) {
   
	return l._node == _node;
};

📈备注：++让封装的ListNode指向下一个节点，–指向上一个节点， * 解引用得到当前节点的值，->通过this指针使用成员，比较相不相等就是比较是不是同个节点。

🚀3. Reverse_list_iterator模板(拓展)

Reverse_list_iterator就是反向迭代器。

//反向迭代器
template<class T, class str, class ptr>
struct Reverse_list_iterator
{
   
	typedef ListNode<T> Node;
	typedef Reverse_list_iterator<T, str, ptr> Self;
	Node* _node;

	//构造函数
	Reverse_list_iterator(Node* tmp):
		_node(tmp) {
   };

	//前置++重载
	Self operator++()
	{
   
		_node = _node->_prev;
		return *this;
	};
	//后置++重载
	Self operator++(int) {
   
		Node* tmp = _node;
		_node = _node->_prev;
		return tmp;
	};
	//前置--重载，
	Self operator--()