list就是我们之前学过的链表，我们都知道链表和string、vector不一样，链表自身是不连续的一段内存，而string和vector是连续的。并且这里的list是双向带头的链表。因此我们先来看链表的节点：

template struct list_node { 	list_node(const T& val = T()) 		:next(nullptr) 		,prev(nullptr) 		,data(val) 	{} 	list_node* next; 	list_node* prev; 	T data; };

我们使用模板来表示链表的一个节点，这一个节点里面有一个T类型的数据，并且有两个方向next和prev，两个节点的指针来存储另外两个节点的信息。

对于容器，我们都需要有迭代器，像我们使用过的string 和 vector 都有迭代器，我们在模拟基础实现的时候，直接使用了原生指针typedef成了迭代器，但是对于链表来说，它的内存是不连续的，因此不能进行随机访问，也就是不能进行+，+=这些操作，因此我们必须封装一个迭代器：

template struct list_iterator { 	typedef list_node node; 	typedef list_iterator self; 	list_iterator(node* val) 		:_node(val) 	{}  	Ref operator*() 	{ 		return _node->data; 	}  	Ptr operator->() 	{ 		return &_node->data; 	}   	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& val) const 	{ 		return _node != val._node; 	}  	bool operator==(const self& val) const 	{ 		return _node == val._node; 	}  	node* _node; };

 这里我们使用了模板来完成链表的迭代器，对于iterator 和 const_iterator，区别就是能不能对此处位置值的修改，因此我们完全可以使用模板来完成两个迭代器。

T这个参数就是数据类型，也就是我们链表里面存的是什么类型的数据。对于Ref和Ptr，其实就是在迭代器那里，如果我们传入的是const_iterator，那么Ref，Ptr也就会被编译器推断成相应正确的类型。

Ref operator*() { 	return _node->data; }  Ptr operator->() { 	return &_node->data; }

迭代器的本质其实也就是一个节点，只不过是对这个节点进行了封装，我们在使用迭代器时，就可以通过迭代器来操作相应的节点位置。并且我们对迭代器也进行了相应的运算符重载，例如前置、后置++(--)，!= 和 ==，解引用* ，->等操作，这些操作都比较简单，返回对应的结果即可，唯一要注意的是，->运算符重载时，是返回节点数据的地址。

下面我们来看看list类的实现：

class list { public:  	typedef list_node node; 	typedef list_iterator iterator; 	typedef list_iterator const_iterator;  private:  	node* _head; 	size_t _size;  };

我们先来看看三个typedef：

1. typedef list_node  node;这个比较好理解，我们在创建一个节点时，需要使用到 list_node，因为太长所以直接定义为node。
2. typedef list_iterator  iterator; 
3. typedef list_iterator  const_iterator;

这里就能明白，为什么我们在封装迭代器的时候需要传入三个模板参数，当我们使用不同的迭代器时，传入的参数就不一样，就可以满足普通迭代器和const迭代器的区别了。

list内部成员就只有一个头节点和 _size实时记录list的大小。

我们先来看list的一些构造函数：

void Init_Empty() { 	_head = new node; 	_head->next = _head; 	_head->prev = _head; 	_size = 0; }  list() { 	Init_Empty(); }  list(size_t n, const T& val = T()) { 	Init_Empty(); 	for (size_t i = 0; i < n; ++i) 	{ 		push_back(val); 	} }  list(int n, const T& val = T()) { 	Init_Empty(); 	for (int i = 0; i < n; ++i) 	{ 		push_back(val); 	} }  template  list(Iterator first, Iterator last) { 	Init_Empty(); 	while (first != last) 	{ 		push_back(*first); 		++first; 	} }  list(const list& lt) { 	Init_Empty(); 	for (auto e : lt) 		push_back(e); }  void swap(list lt) { 	std::swap(_head, lt._head); 	std::swap(_size, lt._size); }  list& operator=(const list lt) { 	swap(lt); 	return *this; }  ~list() { 	clear(); 	delete _head; 	_head = nullptr; }  void clear() { 	auto it = begin(); 	while (it != end()) 	{ 		it = erase(it); 	} }

我们先实现了一个Init_Empty函数，这个函数就是帮助我们先构造处一个头节点，因此list无参构造就可以直接调用这个函数。

接下来是用n个val值初始化list：

list(size_t n, const T& val = T()) { 	Init_Empty(); 	for (size_t i = 0; i < n; ++i) 	{ 		push_back(val); 	} }  list(int n, const T& val = T()) { 	Init_Empty(); 	for (int i = 0; i < n; ++i) 	{ 		push_back(val); 	} }

因为我们的头节点是不算在链表数据之内的，它只是一个帮助我们找到其他节点的一个工具。所以我们先调用 Init_Empty，完成头节点的构造，再向头节点后面不断插入即可。

template  list(Iterator first, Iterator last) { 	Init_Empty(); 	while (first != last) 	{ 		push_back(*first); 		++first; 	} }  list(const list& lt) { 	Init_Empty(); 	for (auto e : lt) 		push_back(e); }

迭代器区间构造和拷贝构造函数也比较简单，思想和n个val初始化类似，这里不做过多解释。

void swap(list lt) { 	std::swap(_head, lt._head); 	std::swap(_size, lt._size); }  list& operator=(const list lt) { 	swap(lt); 	return *this; }  ~list() { 	clear(); 	delete _head; 	_head = nullptr; } void clear() { 	auto it = begin(); 	while (it != end()) 	{ 		it = erase(it); 	} }

最后是赋值重载和析构，对于赋值重载，我们只需要交换对应list的成员变量即可，和前面的string vector思想一致。对于析构函数，我们直接调用了clear(),因为clear的功能就是从begin()开始，一直删除直到剩下头节点，然后再delete头节点即可。

接下来是迭代器，这里比较简单，也就不解释了：

iterator begin() { 	return _head->next; }  iterator end() { 	return _head; }  const_iterator begin()const { 	return _head->next; }  const_iterator end()const { 	return _head; }

接下来是insert和erase函数使用：

iterator insert(iterator pos, const T& val) { 	node* tmp = new node; 	node* cur = pos._node; 	node* prev = cur->prev; 	tmp->data = val; 	prev->next = tmp; 	tmp->prev = prev; 	tmp->next = cur; 	cur->prev = tmp;  	_size++;  	return tmp; } iterator erase(iterator pos) { 	assert(pos != end()); 	node* cur = pos._node; 	node* prev = cur->prev; 	node* next = cur->next;  	delete[] cur; 	cur = nullptr; 	prev->next = next; 	next->prev = prev;  	_size--;  	return next; }

我们之前学习链表的时候，对于增删已经非常熟悉，无非就是增加或者删除节点，然后将对应的节点的next与prev调整好指向方向。这里对于insert，因为我们要在pos位置增加一个节点，我们只需要找到pos位置之前的节点prev，然后将新开出来的节点插入到pos和 prev之间即可。

对于erase，我们需要找到pos位置的prev和next，然后delete[ ]掉pos位置的节点，然后将prev和next链接起来就行了，需要注意的只是删除的时候pos位置不能等于end()，因为我们不能删除头节点。

然后是头插尾插和头删尾删：

void push_back(const T& val) { 	insert(end(), val); }  void push_front(const T& val) { 	insert(begin(), val); }  void pop_back() { 	erase(--end()); }  void pop_front() { 	erase(begin()); }

这里就是insert和erase的复用，找好对应的pos位置即可。

最后就是几个简单的函数功能：

//链表的长度 size_t size() { 	return _size; }  //是否为空 bool empty() { 	return _size == 0; }  //返回链表第一个数据 T& front() { 	iterator it = begin(); 	return it._node->data; }  //返回链表第一个数据 const T& front()const { 	const_iterator it = begin(); 	return it._node->data; }  //返回链表最后一个数据 T& back() { 	iterator it = end(); 	return it._node->prev->data; }  //返回链表最后一个数据 const T& back()const { 	const_iterator it = end(); 	return it._node->prev->data; }

上面的函数功能都比较好理解，大家知道是干什么的就行，实现起来肯定没问题。

以上内容就是对list的基础功能实现，如有错误，欢迎批评指正！！！