一：节点结构的定义

在实现list之前，我们要先定义一下这个链表的节点结构。一个链表是有多个节点链接组成，所以节点自然是重中之重。

我们在头文件定义一下节点结构，上文讲到，一个节点包括_data、_prev、_next三个部分：

代码语言：javascript

AI代码解释

template <class T>
struct ListNode
{
	ListNode(const T& data = T())//给的缺省值是我们想要存储的数据类型的一个匿名对象（自定义类型需要构造函数）
		:_data(data)
		, _next(nullptr)
		, _prev(nullptr)
	{

	}

	T _data;
	ListNode<T>* _next;//指向下一个节点
	ListNode<T>* _prev;//指向上一个节点
};

当然，也要记得写这个模板类的默认构造，我们用想存储的数据的一个匿名对象来完成对_data的初始化。 

二、list类的默认构造，成员变量

我们用_count来记录链表的节点数目，_head记录双向带头链表的头节点。

为了简写代码，方便我们操作，我们顺便把ListNode<T>重命名为Node。

随后书写list的默认构造函数，就是赋予头节点空间，将头节点的_prev与_next指向自己，还有把_count初始化为0。

代码语言：javascript

AI代码解释

template<class T>
class list
{
	typedef ListNode<T> Node;
public:
	list()
	{
		_head = new Node();
		_head->_next = _head;
		_head->_prev = _head;
		_count = 0;
	}
private:
	Node* _head;
	size_t _count;
};

三、list：用类实现迭代器的思想

在实现我们list的各种接口之前，我们首先要来实现一下list容器的迭代器。

这属于是list内容的重中之重，不同于vector，我们返回一个指针作为迭代器，指针的++就可以让迭代器向后移动到另一个元素。我们的list是由许多个节点链接而成，又怎么可以使用各种++操作符呢？

在这个基础上，我们想到了，可以是先用一个类，在这个类中重载各种++，--运算符，手动实现迭代器的向后移动（向前移动）。

那我们又如何实现const的迭代器呢？难不成学vector在前面加个const就可以了吗？

显而易见，由于底层结构的不同，const迭代器的实现原理也有所不同。

其实很简单，要想实现const迭代器的作用，我们只需要在迭代器类的各种内置函数的返回参数的类型做手脚就行。函数返回类型变成了const，自然就是const迭代器的作用。这样的代价就是我们要写两个迭代器模板。

但为了减少我们的麻烦，我们可以在写迭代器的时候在tmplete后面多加几个类型参数就行，这样就把我们的麻烦当做礼物送给了编译器（编译器：听我说，谢谢你）。

代码语言：javascript

AI代码解释

template<class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;//节点类型
	typedef ListIterator<T, Ref, Ptr> Self;//代表自己这个类型

	Node _node;
	ListIterator(Node node = nullptr)//缺省为nullptr的默认构造函数
		:_node(node)
	{

	}
	ListIterator(const Self& l)//传一个迭代器类型（在实现后置++，后置--可以用得到)
		:_node(l._node)
	{

	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;//Ptr是指针类型，模拟实现->时应该返回的是地址，即返回一个指向当前值的指针
	}

	Self& operator++()//前置++
	{
		_node = _node->_next;
		return *this;
	}

	Self operator++(int)//后置++
	{
		Self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	Self operator--(int)
	{
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	bool operator!=(const Self& l)
	{
		return _node != l._node;
	}

	bool operator==(const Self& l)
	{
		return _node == l._node;
	}
};

四、反向迭代器的实现

与我们刚刚实现正向迭代器一样的思想，反向迭代器也需要用模板类的思想来解决。在实现反向迭代器的时候，我们核心仍然通过正向迭代器去运转，只不过在反向迭代器类中再次重载了各种操作符。例如，反向迭代器的前置++，我们只需要在实现的时候，在函数内调用正向迭代器的前置--就行。