要手写 List，先明确其底层结构 ——带头双向循环链表，这是所有接口高效实现的基础

那既然是这样的话，是不是就可以说明list中的私有成员仅仅只需要一个头结点就可以了，也就是哨兵位。

list中的私有成员是一个节点类型，那我们就还需要一个节点结构，这个节点结构中需要包含：

• prev指针：指向当前节点的前一个节点的指针（保存前一个节点的地址）
• next指针：指向当前节点的后一个节点的指针（保存后一个节点的地址）
• data：存储数据

也许会有UU想问：为什么会有这个节点结构？

这是因为每个在一个单独的结构里面，这个结构不仅存储数据，还有指针指向前一个和后一个节点，所以链表必须要有一个节点的结构！！！

ok，话不多说，直接上代码：

• list.h

代码语言：javascript

AI代码解释

namespace carrot
{
    //节点类型
	template<class T>
	struct list_Node
	{
		list_Node<T>* _prev;//指向前一个节点的指针
		list_Node<T>* _next;//指向后一个节点的指针
		T data;//存储数据
	};
	template<class T>
	class list
	{
		using Node = list_Node<T>;
	private:
		Node* _head;//头结点（哨兵位）
	};
}

通过前面数据结构中对双向链表的学习，我们知道我们需要一个空的头结点，那我们就需要构造一个空的头结点：

• list.h

代码语言：javascript

AI代码解释

template<class T>
class list
{
	using Node = list_Node<T>;
	//构造
	//构造一个空的头结点
	list()
	{
		_head = new Node;
		_head->_prev = _head;
		_head->_next = _head;
	}
private:
	Node* _head;//头结点（哨兵位）
};

二、架构构建：核心功能实现详解

2.1 尾插数据：push_back

通过对list底层的分析，我们已经有了一个空的链表，那我们是不是就可以在链表的尾部进行插入数据的操作了~~~

那我们该怎么插入这个数据呢？

在尾插的操作中，哨兵位没有发生改变。

plist本来指向0x100，有了值之后plist指向0x800。

通过前面的学习，我们可以快速写出代码：

当我们运行上面的代码时，会不会有什么问题呢？

那是不是说明我们没有创建一个新的节点空间，并将数据存储进去，那我们就需要在节点结构中加上构造节点的构造函数：

代码语言：javascript

AI代码解释

namespace carrot
{
	template<class T>
	struct list_Node
	{
		list_Node<T>* _prev;//指向前一个节点的指针
		list_Node<T>* _next;//指向后一个节点的指针
		T data;//存储数据
        //创建一个节点
		list_Node(const T& x)
			:_prev(nullptr)
			,_next(nullptr)
			,data(x)
		{}
	};
}

• push_back代码 list.h：

代码语言：javascript

AI代码解释

template<class T>
class list
{
public:
	//push_back
	void push_back(const T& x)
	{
		//为x创建一个节点空间
		Node* newnode = new Node(x);
		Node* tail = _head->_prev;
		tail->_next = newnode;
		newnode->_prev = tail;
		newnode->_next = _head;
		_head->_prev = newnode;
	}
}

ok，通过上面的操作，我们就实现了List的一个基本框架，那我们接下来看看list中是如何实现迭代器的

2.2 链表迭代器实现：封装节点指针与运算符重载

也许会有uu想说：迭代器嘛，不就是给指针重新命名成iterator或者const_iterator，然后直接进行 *迭代器或者++迭代器，不就行了，不是很简单嘛~~

ok，我们知道迭代器的特别之处就在于“ * ”和“++”操作，* 就可以直接取出数据，++ 就是下一个位置的迭代器

但是我们想一想，链表list中的迭代器也可以直接进行 * 和 ++ 操作吗？

• 我们直接进行 * 操作，可以直接取出节点中的数据吗？很明显不能，因为节点中不仅有保存数据的data，还有prev和next指针，无法直接取出数据。
• 我们直接进行 ++ 操作，可以得到下一个位置的迭代器吗？很明显不能，因为链表中的地址不是连续的。

那我们该怎么实现这个迭代器呢？

问题根源

• 数据存储在节点内部，*iterator 无法直接访问
• ++iterator 无法直接跳到下一个节点
• 节点指针的原始操作太底层、不安全