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 无法直接跳到下一个节点
• 节点指针的原始操作太底层、不安全

ok，我们知道迭代器的主要功能无非就是 * 和 ++ 操作，既然数据都在节点中，*iterator无法直接取出数据，++无法直接取下一个接单的地址，所以我们可以用一个类来封装一个迭代器，然后在这个类中实现 * 和 ++ 的运算符重载，在这个类中通过节点的指针来访问数据和++操作，用一个节点的指针来构造一个迭代器

代码语言：javascript

AI代码解释

#include<iostream>
using namespace std;
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)
		{}
	};
	template<class T>
	struct list_iterator
	{
		using Node = list_Node<T>;
		using Self = list_iterator<T>;
		//用需要访问的节点的指针给_node初始化，构造一个list_iterator对象出来
		list_iterator(Node* node)
			:_node(node)
		{}
		Node* _node;
		//*
		T& operator*()
		{
			return _node->data;
		}
		//++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;//*this的类型是list_iterator<T>
		}
        bool operator!=(const Self& s) const
        {
	        return _node != s._node;
        }
	};
}

ok，这样我们就实现了一个普通迭代器，这个迭代器的关键所在就在于：使用一个节点的指针构造一个迭代器对象

• 如果要*iterator，就通过构造迭代器的指针访问数据
• 如果要++，就通过构造迭代器的指针中的next

2.2.1 遍历的起点哨兵：begin()

通过前面的学习，我们知道begin()是第一个有效数据位置的迭代器，那在链表中第一个有效数据所在的节点就是begin()所在的位置

• list.h

代码语言：javascript

AI代码解释

template<class T>
class list
{
public:
	using iterator = list_iterator<T>;
	iterator begin()
	{
		return iterator(_head->_next);
	}
}

2.2.2 遍历的终点哨兵：end()

通过前面的学习，我们知道end()是最后一个有效数据位置的下一个位置的迭代器，那在链表中最后一个有效数据位置的下一个位置所在的节点就是end()所在的位置，也就是“哨兵位”所在的位置

• list.h

代码语言：javascript

AI代码解释

template<class T>
class list
{
public:
	using iterator = list_iterator<T>;
	iterator end()
	{
		return iterator(_head);
	}
}

iterator(_head) ; 和上面 begin() 的解释完全一样！！！

ok，迭代器这块还是有点小难度的，接下来我们接着完善list的相关操作：

2.3 任意位置的插入：灵活添加元素（insert）

inset使用迭代器传位置！！！

• list.h

代码语言：javascript

AI代码解释

template<class T>
class list
{
public:
	void insert(iterator pos, const T& x)
	{
		//为x创建节点空间
		Node* newnode = new Node(x);
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		newnode->_next = cur;
		newnode->_prev = prev;
		prev->_next = newnode;
		cur->_prev = newnode;
	}
}

• 测试代码：

代码语言：javascript

AI代码解释

namespace carrot
{
	void testList1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int>::iterator it = lt.begin();
		lt.insert(it, 10);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

• 代码解释：

2.4 任意位置的删除：灵活删除元素（erase）

erase使用迭代器传位置！！！

• list.h

代码语言：javascript

AI代码解释

void  erase(iterator pos)
{
	Node* cur = pos._node;
	Node* next = cur->_next;
	Node* prev = cur->_prev;
	prev->_next = next;
	next->_prev = prev;
	delete cur;
	cur = nullptr;
}

如果我们的erase按照上面的代码的话，在调用erase中的迭代器会出现失效的情况，为了解决这个问题，我们应该让erase返回删除位置的后一个位置的迭代器，也就是pos（why?因为在删除的过程中，pos后的位置上的数据挪动到pos位置上）

• 修改后的代码：

代码语言：javascript

AI代码解释

template<class T>
class list
{
public:
    iterator erase(iterator pos)
    {
	    Node* cur = pos._node;
	    Node* next = cur->_next;
	    Node* prev = cur->_prev;
	    prev->_next = next;
	    next->_prev = prev;
	    delete cur;
	    cur = nullptr;
	    return iterator(next);
    }
}

erase中的pos的解释和insert一样

ok,有了insert和erase，我们就可以在push_back、push_front、pop_back、pop_front中复用insert和erase。