C++实现双向链表（含迭代器）_c++双向链表

1.什么是双向链表

这里既然要实现双向链表，就首先要知道双向链表是什么。

双向链表，实际上就是一种储存数据的容器，是属于链表的其中一种。他的特点是：数据储存在不连续的内存空间中，每个数据节点包含 数据、上一个数据节点的指针和下一个数据节点的指针。

缘于他的这种特点，他可以在 $O(1)$ 的时间复杂度内删除给定的节点，但是如果是查询特定的节点的话，其需要 $O(n)$ 的时间，所以对于较少随机查询，并且经常需要插入或删减中间数据的大量数据，我们可以考虑使用链表作为双向容器进行存储。

2.双向链表的C++代码实现

在编写代码之前，我们需要考虑一下我们需要编写什么东西，以及编写的流程。

对于双向链表，我们要编写的东西有：数据节点、迭代器、链表的初始化、获取节点、插入节点、删除节点。完成了上面基本功能的实现后，我们便可以方便的完成整个链表的实现。另外，我们还可以实现链表的 交换 和链表的 合并 的等一些其他的功能。

首先说明：以下代码均在类内实现，所以一段代码单独拷贝使用不一定能够通过编译，并且最后会给出全部整合在一起的代码

(1)数据节点的代码编写

可以说，数据节点是双向链表的基础，所以，数据节点编写的好不好很大程度上决定了我们的双向链表好不好。

首先我们知道，数据节点应包含上一个节点的指针和下一个节点的指针，那么数据内容的存储又应该如何实现呢？这里用两种方案：1.直接在节点中存储该数据；2.开辟另外的内存存储该数据，在节点中存储指向该内存的指针。在这里我们选择第二种方案进行实现。

于是我们可以写出以下代码：

//节点
struct node
{
	node* last = nullptr;
	_Ty* content = nullptr;
	node* next = nullptr;

	node() = default;

	node(node* _last, node* _next) noexcept :
		last(_last), next(_next)
	{
		//保证上下节点与自己的连接
		if (this->last != nullptr)
		{
			this->last->next = this;
		}

		if (this->next != nullptr)
		{
			this->next->last = this;
		}
	}

	~node()
	{
		if (content != nullptr)
		{
			delete content;
			content = nullptr;
		}

		//保证上下节点的连接
		if (this->last != nullptr)
		{
			this->last->next = this->next;
		}

		if (this->next != nullptr)
		{
			this->next->last = this->last;
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

(2)迭代器

通常来说，我们一般不会直接给外部使用指向节点的指针（因为不安全，可能出现越界等非法操作），而是通过迭代器进行包装，给外部使用包装好的，较为安全的迭代器。

一个容器一般有四种迭代器：迭代器、常量迭代器、反向迭代器、常量迭代器。因为这四种迭代器的代码具有高度重复性，所以这里我们只需使用两个模板类作为基类就可以实现四种迭代器。

这里我们需要实现迭代器能够进行自增自减运算与比较操作，并且能够获取到指针指向的数据的引用，另外做一些安全方面的检查。

代码如下：

//迭代器 - 基类
template<class _Valty>
class _Iterator
{
public:
	using _Self = _Iterator<_Valty>;
	using _NoConstSelf = _Iterator<std::remove_const_t<_Valty>>;
	using ValueType = _Valty;
	friend _List;

private:
	node* _Now = nullptr;
	const _List* _Container = nullptr;
	size_t _Record_Condition = 0;

protected:
	//判断是否在列表范围内
	void _RangeCheck_() const
	{
		_ConditionCheck();
		if (_Now == nullptr)
			throw "Iterator is out of range!";
	}

	//确认是否有内容（即是否是尾部）
	void _ContentCheck_() const
	{
		_ConditionCheck();
		if (_Now->content == nullptr)
			throw "Can not get null content!";
	}

	//确认列表是否仍然存在
	void _ContainerCheck_() const
	{
		if (_Container == nullptr)
			throw "Can not belong to null list!";
	}

	//确认列表是否有删减
	void _ConditionCheck() const
	{
		_ContainerCheck_();
		if (_Record_Condition != _Container->_Condition)
			throw "Can not use the invalid iterator!";
	}

public:
	_Iterator(node* _now, const _List* _container) noexcept :
		_Now(_now), _Container(_container), _Record_Condition(_container->_Condition)
	{
		_RangeCheck_();
	}

	template<class _TIter,
		class _Judge = std::enable_if_t<std::is_same_v<_TIter, _Self> || std::is_same_v<_TIter, _NoConstSelf>, void>>
		_Iterator(const _TIter& _Copy) noexcept
	{
		this->_Now = _Copy._Now;
		this->_Container = _Copy._Container;
		this->_Record_Condition = _Copy._Record_Condition;
	}

	template<class _TIter>
	std::enable_if_t<std::is_same_v<_TIter, _Self> || std::is_same_v<_TIter, _NoConstSelf>, _Self&>
		operator=(const _TIter& _Copy) noexcept
	{
		this->_Now = _Copy._Now;
		this->_Container = _Copy._Container;
		this->_Record_Condition = _Copy._Record_Condition;
		return *this;
	}

	ValueType* operator->() const
	{
		_ContentCheck_();
		return _Now->content;
	}

	ValueType& operator*() const
	{
		_ContentCheck_();
		return *_Now->content;
	}

	_Self& operator++()
	{
		_Now = _Now->next;
		_RangeCheck_();
		return *this;
	}

	_Self& operator++(int)
	{
		auto _RItr = *this;
		_Now = _Now->next;
		_RangeCheck_();
		return _RItr;
	}

	_Self& operator--()
	{
		_Now = _Now->last;
		_RangeCheck_();
		return *this;
	}

	_Self& operator--(int)
	{
		auto _RItr = *this;
		_Now = _Now->last;
		_RangeCheck_();
		return _RItr;
	}

	bool operator==(const _Self& _cmper) const
	{
		return this->_Now == _cmper._Now;
	}

	bool operator!=(const _Self& _cmper) const
	{
		return this->_Now != _cmper._Now;
	}
};

//反迭代器 - 基类
template<class _Iter>
class _Reverse_Iterator
{
public:
	using _Self = _Reverse_Iterator<_Iter>;
	using _NoConstSelf = _Reverse_Iterator<typename _Iter::_NoConstSelf>;

	using ValueType = typename _Iter::ValueType;
	friend _List;

private:
	_Iter _iter;

protected:
	ValueType* _RealPos_() const
	{
		auto _RItr = _iter;
		return (--_RItr).operator->();
	}

public:
	_Reverse_Iterator(node* _now, const _List* _container) noexcept :
		_iter(_now, _container) {}

	template<class _TIter,
		class _Judge = std::enable_if_t<std::is_same_v<_TIter, _Self> || std::is_same_v<_TIter, _NoConstSelf>, void>>
		_Reverse_Iterator(const _TIter& _Copy) noexcept
	{
		_iter = _Copy._iter;
	}

	template<class _TIter>
	std::enable_if_t<std::is_same_v<_TIter, _Self> || std::is_same_v<_TIter, _NoConstSelf>, _Self&>
		operator=(const _TIter& _Copy) noexcept
	{
		_iter = _Copy._iter;
		return *this;
	}

	ValueType* operator->() const
	{
		return _RealPos_();
	}

	ValueType& operator*() const
	{
		return *_RealPos_();
	}

	_Self& operator++()
	{
		--_iter;
		return *this;
	}

	_Self& operator++(int)
	{
		auto _RItr = *this;
		--_iter;
		return _RItr;
	}

	_Self& operator--()
	{
		++_iter;
		return *this;
	}

	_Self& operator--(int)
	{
		auto _RItr = *this;
		++_iter;
		return _RItr;
	}

	bool operator==(const _Self& _cmper) const
	{
		return this->_iter == _cmper._iter;
	}

	bool operator!=(const _Self& _cmper) const
	{
		return this->_iter != _cmper._iter;
	}
};

//迭代器
using iterator = _Iterator<_Ty>;
//常迭代器
using const_iterator = _Iterator<const _Ty>;
//反迭代器
using reverse_iterator = _Reverse_Iterator<iterator>;
//常反迭代器
using const_reverse_iterator = _Reverse_Iterator<const_iterator>;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221

(3)链表初始化

一般而言，一个容器都会记录下该容器的 begin 、 end 和 size，所以我们现在类内给出这三个数据的实现：

这里还给出了 Condition ，用于判断迭代器的有效性，后面会细说

private:
	node* _Begin = nullptr;
	node* _End = nullptr;
	size_t _Size = 0;
	size_t _Condition = 0;
1
2
3
4
5

需要注意：出于安全性考虑，这些数据都不应该能被外部能直接访问到，所以要设置成保护或者私有

于是，我们初始化一个链表，就是要考虑如何设置好上面三个数据。因为 begin 是指向容器第一个元素的地址， end 是指向容器的末尾元素后一个元素的地址，我们可以不对 begin进行设置，只设置好 end 即可，于是可以给出下面的代码：

protected:
	//重置 _End
	void _ResetEnd_()
	{
		if (_End == nullptr)
			_End = new node();

		//正常情况下只会进入第一个分支
		if (_Begin == nullptr || _Begin == _End)
		{
			_End->last = nullptr;
			_Begin = _End;
		}
		else
		{
			node* read_ptr = _Begin;
			while (read_ptr->last != nullptr && read_ptr != _End)
				read_ptr = read_ptr->last;

			_End->last = read_ptr;
			read_ptr->last = _End;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这里我出于继承的考虑，调用这个函数时会根据实际情况进行处理

有了这个函数，我们在每次创建一个新链表的时候，在构造函数中调用这个函数即可。

此外，因为设置好了 begin 和 end ,我们可以利用这两个数据给出获取迭代器的方法：

iterator begin()
{
   return iterator(_Begin, this);
}

const_iterator begin() const
{
   return const_iterator(_Begin, this);
}

iterator end()
{
   return iterator(_End, this);
}

const_iterator end() const
{
   return const_iterator(_End, this);
}

const_iterator cbegin() const
{
   return const_iterator(_Begin, this);
}

const_iterator cend() const
{
   return const_iterator(_End, this);
}

reverse_iterator rbegin()
{
   return reverse_iterator(_End, this);
}

const_reverse_iterator rbegin() const
{
   return const_reverse_iterator(_End, this);
}

reverse_iterator rend()
{
   return reverse_iterator(_Begin, this);
}

const_reverse_iterator rend() const
{
   return const_reverse_iterator(_Begin, this);
}

const_reverse_iterator crbegin() const
{
   return const_reverse_iterator(_End, this);
}

const_reverse_iterator crend() const
{
   return const_reverse_iterator(_Begin, this);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

(4)获取节点

获取节点直接利用 begin 和 end 就能够获取，这里不多赘述。

public:
//列表最前一个元素
[[nodiscard]] _Ty& front()
{
	if (_Size == 0)
		throw "Can not get element from null list!";
	return *_Begin->content;
}

//列表最后一个元素
[[nodiscard]] _Ty& back()
{
	if (_Size == 0)
		throw "Can not get element from null list!";
	return *_End->last->content;
}

//列表最前一个元素
[[nodiscard]] const _Ty& front() const
{
	if (_Size == 0)
		throw "Can not get element from null list!";
	return *_Begin->content;
}

//列表最后一个元素
[[nodiscard]] const _Ty& back() const
{
	if (_Size == 0)
		throw "Can not get element from null list!";
	return *_End->last->content;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

(5)插入和删除节点

插入和删除节点的时候，如果节点是在头部或尾部，我们需要对 begin 和 end 进行修改。

此外，当节点删除后，我们需要修改状态值，因为我们也在迭代器生成之时在迭代器中保存了一份状态值，所以当比较到状态值不同时，我们即可实现对迭代器的无效化处理，保证了安全性。

实现代码如下：

//插入节点
template<class ..._Valty>
void _InsertNode_(node* _Where, _Valty&&... _Vals)
{
	//空节点默认插入到最后一个节点
	if (_Where == nullptr)
		_Where = _End;

	//在 _Where 前面创建新节点
	node* _NewNode = new node(_Where->last, _Where);
	_NewNode->content = new _Ty(_Vals...);

	//如果节点在最前面 _Begin 变成该节点
	if (_NewNode->last == nullptr)
		_Begin = _NewNode;

	//列表长度加一
	_Size++;
}

//删除节点
void _DeleteNode_(node* _Where)
{
	//不能删除空节点和尾节点
	if (_Where == nullptr)
		throw "Can not delete null node!";

	if (_Where->next == nullptr)
		throw "Can not delete end node!";

	if (_Where == _Begin)
		_Begin = _Where->next;

	delete _Where;

	//列表长度减一
	_Size--;

	//每次清除节点，状态码加一
	_Condition++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

(6)链表的交换与合并

有的时候，我们可能需要交换两个链表里面内容或将两个链表按顺序合并成一个链表，这个时候，使用上面的给出的方法去实现既费力又低效。因此，我们这里单独给出链表的交换与合并的代码实现：

//交换列表
template<class _TList>
void _Swap(_TList _Swapper)
{
	node* temp_ptr = nullptr;
	size_t temp_size = 0;

	//交换头部
	temp_ptr = this->_Begin;
	this->_Begin = _Swapper._Begin;
	_Swapper._Begin = temp_ptr;

	//交换尾部
	temp_ptr = this->_End;
	this->_End = _Swapper._End;
	_Swapper._End = temp_ptr;

	//交换Size
	temp_size = this->_Size;
	this->_Size = _Swapper._Size;
	_Swapper._Size = temp_size;
}

//增长列表
template<class _TList>
void _Merge(_TList _Merger)
{
	if (_Merger._Size == 0)
		return;

	//处理中间的连接
	if (this->_Size != 0)
	{
		this->_End->last->next = _Merger._Begin;
		_Merger._Begin->last = this->_End->last;
	}
	else
	{
		this->_Begin = _Merger._Begin;
	}

	//将 _End 移动到最后
	this->_End->last = _Merger._End->last;
	_Merger._End->last->next = this->_End;
	this->_Size += _Merger._Size;

	//清空被拼接的列表
	_Merger._Begin = _Merger._End;
	_Merger._End->last = nullptr;
	_Merger._Size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

3.完整代码

最后，我们对上面的代码进行一个整合，得到完整的双向链表的代码实现。

//list.h
#pragma once
#ifndef _YYYCZ_LIST_
#define _YYYCZ_LIST_

#include<initializer_list>

#pragma push_macro("new")
#undef new

namespace YYYCZ
{
	template<class _Ty>
	class list
	{
		using _List = list<_Ty>;
		using _IniList = std::initializer_list<_Ty>;

		//节点
		struct node
		{
			node* last = nullptr;
			_Ty* content = nullptr;
			node* next = nullptr;

			node() = default;

			node(node* _last, node* _next) noexcept :
				last(_last), next(_next)
			{
				//保证上下节点与自己的连接
				if (this->last != nullptr)
				{
					this->last->next = this;
				}

				if (this->next != nullptr)
				{
					this->next->last = this;
				}
			}

			~node()
			{
				if (content != nullptr)
				{
					delete content;
					content = nullptr;
				}

				//保证上下节点的连接
				if (this->last != nullptr)
				{
					this->last->next = this->next;
				}

				if (this->next != nullptr)
				{
					this->next->last = this->last;
				}
			}
		};

	private:
		using _Self = list<_Ty>;

		node* _Begin = nullptr;
		node* _End = nullptr;
		size_t _Size = 0;
		size_t _Condition = 0;

	public:
		//迭代器 - 基类
		template<class _Valty>
		class _Iterator
		{
		public:
			using _Self = _Iterator<_Valty>;
			using _NoConstSelf = _Iterator<std::remove_const_t<_Valty>>;
			using ValueType = _Valty;
			friend _List;

		private:
			node* _Now = nullptr;
			const _List* _Container = nullptr;
			size_t _Record_Condition = 0;

		protected:
			//判断是否在列表范围内
			void _RangeCheck_() const
			{
				_ConditionCheck();
				if (_Now == nullptr)
					throw "Iterator is out of range!";
			}

			//确认是否有内容（即是否是尾部）
			void _ContentCheck_() const
			{
				_ConditionCheck();
				if (_Now->content == nullptr)
					throw "Can not get null content!";
			}

			//确认列表是否仍然存在
			void _ContainerCheck_() const
			{
				if (_Container == nullptr)
					throw "Can not belong to null list!";
			}

			//确认列表是否有删减
			void _ConditionCheck() const
			{
				_ContainerCheck_();
				if (_Record_Condition != _Container->_Condition)
					throw "Can not use the invalid iterator!";
			}

		public:
			_Iterator(node* _now, const _List* _container) noexcept :
				_Now(_now), _Container(_container), _Record_Condition(_container->_Condition)
			{
				_RangeCheck_();
			}

			template<class _TIter,
				class _Judge = std::enable_if_t<std::is_same_v<_TIter, _Self> || std::is_same_v<_TIter, _NoConstSelf>, void>>
				_Iterator(const _TIter& _Copy) noexcept
			{
				this->_Now = _Copy._Now;
				this->_Container = _Copy._Container;
				this->_Record_Condition = _Copy._Record_Condition;
			}

			template<class _TIter>
			std::enable_if_t<std::is_same_v<_TIter, _Self> || std::is_same_v<_TIter, _NoConstSelf>, _Self&>
				operator=(const _TIter& _Copy) noexcept
			{
				this->_Now = _Copy._Now;
				this->_Container = _Copy._Container;
				this->_Record_Condition = _Copy._Record_Condition;
				return *this;
			}

			ValueType* operator->() const
			{
				_ContentCheck_();
				return _Now->content;
			}

			ValueType& operator*() const
			{
				_ContentCheck_();
				return *_Now->content;
			}

			_Self& operator++()
			{
				_Now = _Now->next;
				_RangeCheck_();
				return *this;
			}

			_Self& operator++(int)
			{
				auto _RItr = *this;
				_Now = _Now->next;
				_RangeCheck_();
				return _RItr;
			}

			_Self& operator--()
			{
				_Now = _Now->last;
				_RangeCheck_();
				return *this;
			}

			_Self& operator--(int)
			{
				auto _RItr = *this;
				_Now = _Now->last;
				_RangeCheck_();
				return _RItr;
			}

			bool operator==(const _Self& _cmper) const
			{
				return this->_Now == _cmper._Now;
			}

			bool operator!=(const _Self& _cmper) const
			{
				return this->_Now != _cmper._Now;
			}
		};

		//反迭代器 - 基类
		template<class _Iter>
		class _Reverse_Iterator
		{
		public:
			using _Self = _Reverse_Iterator<_Iter>;
			using _NoConstSelf = _Reverse_Iterator<typename _Iter::_NoConstSelf>;

			using ValueType = typename _Iter::ValueType;
			friend _List;

		private:
			_Iter _iter;

		protected:
			ValueType* _RealPos_() const
			{
				auto _RItr = _iter;
				return (--_RItr).operator->();
			}

		public:
			_Reverse_Iterator(node* _now, const _List* _container) noexcept :
				_iter(_now, _container) {}

			template<class _TIter,
				class _Judge = std::enable_if_t<std::is_same_v<_TIter, _Self> || std::is_same_v<_TIter, _NoConstSelf>, void>>
				_Reverse_Iterator(const _TIter& _Copy) noexcept
			{
				_iter = _Copy._iter;
			}

			template<class _TIter>
			std::enable_if_t<std::is_same_v<_TIter, _Self> || std::is_same_v<_TIter, _NoConstSelf>, _Self&>
				operator=(const _TIter& _Copy) noexcept
			{
				_iter = _Copy._iter;
				return *this;
			}

			ValueType* operator->() const
			{
				return _RealPos_();
			}

			ValueType& operator*() const
			{
				return *_RealPos_();
			}

			_Self& operator++()
			{
				--_iter;
				return *this;
			}

			_Self& operator++(int)
			{
				auto _RItr = *this;
				--_iter;
				return _RItr;
			}

			_Self& operator--()
			{
				++_iter;
				return *this;
			}

			_Self& operator--(int)
			{
				auto _RItr = *this;
				++_iter;
				return _RItr;
			}

			bool operator==(const _Self& _cmper) const
			{
				return this->_iter == _cmper._iter;
			}

			bool operator!=(const _Self& _cmper) const
			{
				return this->_iter != _cmper._iter;
			}
		};

		//迭代器
		using iterator = _Iterator<_Ty>;
		//常迭代器
		using const_iterator = _Iterator<const _Ty>;
		//反迭代器
		using reverse_iterator = _Reverse_Iterator<iterator>;
		//常反迭代器
		using const_reverse_iterator = _Reverse_Iterator<const_iterator>;

		//用于判断是否是自己的迭代器
		template<class _Iter>
		struct isIterator
		{
			using _DIter = std::decay_t<_Iter>;

			static constexpr bool value = std::is_same_v<_DIter, iterator> || std::is_same_v<_DIter, const_iterator> ||
				std::is_same_v<_DIter, reverse_iterator> || std::is_same_v<_DIter, const_reverse_iterator>;
		};

		template<class _Iter, class _Ty>
		using isIterator_or_Point_t = std::enable_if_t<isIterator<_Iter>::value || std::_Is_iterator_v<_Iter>
			|| std::is_pointer_v<_Iter>, _Ty>;

		iterator begin()
		{
			return iterator(_Begin, this);
		}

		const_iterator begin() const
		{
			return const_iterator(_Begin, this);
		}

		iterator end()
		{
			return iterator(_End, this);
		}

		const_iterator end() const
		{
			return const_iterator(_End, this);
		}

		const_iterator cbegin() const
		{
			return const_iterator(_Begin, this);
		}

		const_iterator cend() const
		{
			return const_iterator(_End, this);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(_End, this);
		}

		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(_End, this);
		}

		reverse_iterator rend()
		{
			return reverse_iterator(_Begin, this);
		}

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(_Begin, this);
		}

		const_reverse_iterator crbegin() const
		{
			return const_reverse_iterator(_End, this);
		}

		const_reverse_iterator crend() const
		{
			return const_reverse_iterator(_Begin, this);
		}

	protected:
		//重置 _End
		void _ResetEnd_()
		{
			if (_End == nullptr)
				_End = new node();

			//正常情况下只会进入第一个分支
			if (_Begin == nullptr || _Begin == _End)
			{
				_End->last = nullptr;
				_Begin = _End;
			}
			else
			{
				node* read_ptr = _Begin;
				while (read_ptr->last != nullptr && read_ptr != _End)
					read_ptr = read_ptr->last;

				_End->last = read_ptr;
				read_ptr->last = _End;
			}
		}

		//插入节点
		template<class ..._Valty>
		void _InsertNode_(node* _Where, _Valty&&... _Vals)
		{
			//空节点默认插入到最后一个节点
			if (_Where == nullptr)
				_Where = _End;

			//在 _Where 前面创建新节点
			node* _NewNode = new node(_Where->last, _Where);
			_NewNode->content = new _Ty(_Vals...);

			//如果节点在最前面 _Begin 变成该节点
			if (_NewNode->last == nullptr)
				_Begin = _NewNode;

			//列表长度加一
			_Size++;
		}

		//删除节点
		void _DeleteNode_(node* _Where)
		{
			//不能删除空节点和尾节点
			if (_Where == nullptr)
				throw "Can not delete null node!";

			if (_Where->next == nullptr)
				throw "Can not delete end node!";

			if (_Where == _Begin)
				_Begin = _Where->next;

			delete _Where;

			//列表长度减一
			_Size--;

			//每次清除节点，状态码加一
			_Condition++;
		}

		//拷贝节点
		void _CopyNode_(const _Self& _Copy)
		{
			clear();
			_ResetEnd_();
			for (const auto& _val : _Copy)
				_InsertNode_(nullptr, _val);
		}

		//交换列表
		template<class _TList>
		void _Swap(_TList _Swapper)
		{
			node* temp_ptr = nullptr;
			size_t temp_size = 0;

			//交换头部
			temp_ptr = this->_Begin;
			this->_Begin = _Swapper._Begin;
			_Swapper._Begin = temp_ptr;

			//交换尾部
			temp_ptr = this->_End;
			this->_End = _Swapper._End;
			_Swapper._End = temp_ptr;

			//交换Size
			temp_size = this->_Size;
			this->_Size = _Swapper._Size;
			_Swapper._Size = temp_size;
		}

		//增长列表
		template<class _TList>
		void _Merge(_TList _Merger)
		{
			if (_Merger._Size == 0)
				return;

			//处理中间的连接
			if (this->_Size != 0)
			{
				this->_End->last->next = _Merger._Begin;
				_Merger._Begin->last = this->_End->last;
			}
			else
			{
				this->_Begin = _Merger._Begin;
			}

			//将 _End 移动到最后
			this->_End->last = _Merger._End->last;
			_Merger._End->last->next = this->_End;
			this->_Size += _Merger._Size;

			//清空被拼接的列表
			_Merger._Begin = _Merger._End;
			_Merger._End->last = nullptr;
			_Merger._Size = 0;
		}

		//检查迭代器是否正常
		template<class _Iter>
		void _IteratorCheck(const _Iter& _itr)
		{
			if (_itr._Container != this)
				throw "Can not use the iterator that not belong to this list!";
			_itr._ConditionCheck();
		}

	public:
		list() noexcept
		{
			_ResetEnd_();
		}

		//初始化列表初始化
		list(_IniList _ini_list) noexcept
		{
			_ResetEnd_();
			for (const auto& _val : _ini_list)
				_InsertNode_(nullptr, _val);
		}

		//多个重复元素初始化
		list(const _Ty& _val, size_t _Conut) noexcept
		{
			_ResetEnd_();
			for (size_t i = 0;i < _Conut;i++)
				_InsertNode_(nullptr, _val);
		}

		//迭代器初始化
		template<class _Iter, class _Judge = isIterator_or_Point_t<_Iter, _Iter>>
		list(_Iter _First, _Iter _Last) noexcept
		{
			_ResetEnd_();
			for (;_First != _Last;++_First)
				_InsertNode_(nullptr, *_First);
		}

		//拷贝初始化
		list(const _Self& _Copy) noexcept
		{
			_CopyNode_(_Copy);
		}

		//拷贝
		_Self& operator=(const _Self& _Copy) noexcept
		{
			_CopyNode_(_Copy);
		}

		//析构时一定要清空列表，释放内存
		~list() noexcept
		{
			clear();
		}

		//重新赋值操作 - 初始化列表
		void assign(_IniList _ini_list) noexcept
		{
			clear();
			_ResetEnd_();
			for (const auto& _val : _ini_list)
				_InsertNode_(nullptr, _val);
		}

		//重新赋值操作 - 重复元素
		void assign(const _Ty& _val, size_t _Conut) noexcept
		{
			clear();
			_ResetEnd_();
			for (size_t i = 0; i < _Conut; i++)
				_InsertNode_(nullptr, _val);
		}

		//重新赋值操作 - 迭代器
		template<class _Iter>
		isIterator_or_Point_t<_Iter, void> assign(_Iter _First, _Iter _Last) noexcept
		{
			clear();
			_ResetEnd_();
			for (; _First != _Last; ++_First)
				_InsertNode_(nullptr, *_First);
		}

		//重新赋值操作 - 拷贝
		void assign(const _Self& _Copy) noexcept
		{
			_CopyNode_(_Copy);
		}

	public:
		//获取列表长度
		[[nodiscard]] size_t size() const
		{
			return _Size;
		}

		//是否为空
		[[nodiscard]] bool empty() const
		{
			return _Size == 0;
		}

		//重设列表长度
		void resize(size_t size, const _Ty& _val = _Ty())
		{
			while (_Size < size)
				push_back(_val);

			while(_Size > size)
				pop_back();
		}

	public:
		//列表最前一个元素
		[[nodiscard]] _Ty& front()
		{
			if (_Size == 0)
				throw "Can not get element from null list!";
			return *_Begin->content;
		}

		//列表最后一个元素
		[[nodiscard]] _Ty& back()
		{
			if (_Size == 0)
				throw "Can not get element from null list!";
			return *_End->last->content;
		}

		//列表最前一个元素
		[[nodiscard]] const _Ty& front() const
		{
			if (_Size == 0)
				throw "Can not get element from null list!";
			return *_Begin->content;
		}

		//列表最后一个元素
		[[nodiscard]] const _Ty& back() const
		{
			if (_Size == 0)
				throw "Can not get element from null list!";
			return *_End->last->content;
		}

	public:
		//以右值形式插入元素
		template<class ..._Valty>
		void emplace(const_iterator _Where, _Valty&&..._vals)
		{
			_IteratorCheck(_Where);
			_InsertNode_(_Where._Now, _vals...);
		}

		//以右值形式在最前面插入元素
		template<class ..._Valty>
		void emplace_front(_Valty&&..._vals)
		{
			_InsertNode_(_Begin, _vals...);
		}

		//以右值形式在最后面插入元素
		template<class ..._Valty>
		void emplace_back(_Valty&&..._vals)
		{
			_InsertNode_(_End, _vals...);
		}

		//插入元素
		void insert(const_iterator _Where, const _Ty& _val)
		{
			emplace(_Where, _val);
		}

		//在最前面插入元素
		void push_front(const _Ty& _val)
		{
			emplace_front(_val);
		}

		//在最后面插入元素
		void push_back(const _Ty& _val)
		{
			emplace_back(_val);
		}

		//删除元素
		void erase(const_iterator _Where)
		{
			_IteratorCheck(_Where);
			_DeleteNode_(_Where._Now);
		}

		//删除一段长度的元素
		void erase(const_iterator _First, const_iterator _Last)
		{
			_IteratorCheck(_First);
			_IteratorCheck(_Last);

			node* _first = _First._Now;
			node* _last = _Last._Now;
			node* _temp_ptr = nullptr;

			//逐个进行删除
			while (_first != _last && _first != _End)
				_temp_ptr = _first,
				_first = _first->next,
				_DeleteNode_(_temp_ptr);
		}

		//删除最前面元素
		void pop_front()
		{
			if (_Size == 0)
				throw "Can not delete element in null list!";
			_DeleteNode_(_Begin);
		}

		//删除最后面元素
		void pop_back()
		{
			if (_Size == 0)
				throw "Can not delete element in null list!";
			_DeleteNode_(_End->last);
		}

		//清空列表
		void clear()
		{
			while (_Begin != _End)
				_DeleteNode_(_Begin);
		}

	public:
		//交换列表
		void swap(_Self& _Swapper)
		{
			_Swap<_Self&>(_Swapper);
		}

		//拼接列表
		void merge(_Self& _Merger)
		{
			_Merge<_Self&>(_Merger);
		}

		//拼接列表
		void merge(_Self&& _Merger)
		{
			_Merge<_Self&>(_Merger);
		}
	};
}

#pragma pop_macro("new")

#endif // !_YYYCZ_LIST_
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755

4.简单的测试代码

这段代码虽然没有测试到所有的功能，但是大体已经测试到了

#include "list.h"

#include<iostream>
#include<random>
#include<sstream>
using namespace std;
using namespace YYYCZ;

//实现链表的输出
//返回输出内容
//实际不只是可以对我写的链表使用
template<class _Container>
string print(const _Container& _List)
{
	static stringstream TextMaker;

	string out_text;
	string text_read;

	out_text = "[";
	//因为定义了迭代器，故可以简洁的写成这样的一个for循环
	for (const auto& i : _List)
	{
		TextMaker << i;
		TextMaker >> text_read;
		TextMaker.clear();

		out_text += text_read;
		out_text.push_back(',');
	}

	if (out_text.size() > 1)
		out_text.pop_back();

	out_text.push_back(']');

	return out_text;
}

//方便使用cout输出
template<class _Ty>
std::ostream& operator<<(std::ostream& out, YYYCZ::list<_Ty> _List)
{
	return out << print(_List);
}

int main()
{
	using _Tt = int;
	YYYCZ::list<_Tt> myList;

	//随机生成一个长度为10的链表
	srand(time(nullptr));
	myList.assign({ _Tt(rand()),_Tt(rand()),
		_Tt(rand()),_Tt(rand()),_Tt(rand()),_Tt(rand()),
		_Tt(rand()),_Tt(rand()), _Tt(rand()),_Tt(rand()) });

	//输出该链表

	/*
	string out_text = print(myList);
	cout << "生成的链表为：" << out_text << endl;
	*/

	//与上面两行代码等价
	cout << "生成的链表为：" << myList << endl;

	//删除前两个元素
	myList.erase(myList.begin(), ++++myList.begin());
	
	cout << "删除两个元素后的链表为：" << myList << endl;

	//清空元素
	myList.clear();

	cout << "清空后的链表为：" << myList << endl;

	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

针不戳，自己写出来的双向链表针不戳