【C++】list的模拟实现

前言：

list是带头双向循环链表，与vector的底层结构不一样，vector是连续的空间，list的每个节点是独立的空间。

模拟实现list主要有以下类：

struct ListNode//节点类
struct ListIterator//正向迭代器类
struct ReverseIterator//反向迭代器类
class list//模拟实现list类
1
2
3
4

1 节点类

每个节点都有它的指针域和数据域，因为是双向的，所以指针域有两个分别为前指针和后指针。同时写个构造函数，用来创建新节点。

template<class T>
struct ListNode//节点类
{
	ListNode<T>* _prev;
	ListNode<T>* _next;
	T _val;

	ListNode(const T& x = T())
		:_prev(nullptr)
		,_next(nullptr)
		,_val(x)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

使用类模板可以传任意类型。

2 模拟实现list类

2.1 成员变量

私有成员变量是链表的头，即哨兵位节点，类型是节点类指针类型，方便连接其他节点。

节点类的名字有点长，可以重命名简化：

typedef ListNode<T> Node;
1

成员变量：

private:
	Node* _head;
1
2

2.2 初始化

初始化是对哨兵位的初始化，即让哨兵位成为一个节点，这个节点不放数据，只是用来连接。它的前指针和后指针都是指向自己。

void Init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}
1
2
3
4
5
6

2.3 构造

1️⃣无参构造
复用初始化即可。

list()
{
	Init();
}
1
2
3
4

2️⃣有参构造1
先对哨兵位节点初始化，然后n为多少尾插多少元素

//有参构造1
list(int n, const T& x = T())
{
	Init();
	while (n--)
	{
		push_back(x);
	}
}
1
2
3
4
5
6
7
8
9

3️⃣有参构造2

该函数的参数只要是迭代器就行，先初始化哨兵位，然后逐个尾插迭代器指向的内容。

template <class Iterator>
list(Iterator first, Iterator last)
{
	Init();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}
1
2
3
4
5
6
7
8
9
10

2.4 拷贝构造

先初始化哨兵位，然后从被拷贝的链表里逐个节点尾插到新链表里。

//拷贝构造
list(const list<T>& lt)
{
	Init();
	for (const auto& e : lt)
	{
		push_back(e);
	}
}
1
2
3
4
5
6
7
8
9

2.5 赋值重载

1️⃣写法1
判断被赋值的对象与要赋值的对象是否地址相同，相同直接返回当前对象，不相同先清理链表的元素，然后用范围for逐个尾插。

//写法1
list<T>& operator=(const list<T>& lt)
{
	if (this != &lt)
	{
		clear();
		for (const auto& e : lt)
		{
			push_back(e);
		}
	}
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1️⃣写法2
这个不多说了，还是复用交换函数，然后返回this指针。

//写法2
list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}
1
2
3
4
5
6

2.6 析构

先清理链表里的所有元素，除了哨兵位节点，然后释放哨兵位节点，置空。

//析构
~list()
{
	clear();
	delete _head;
	_head = nullptr;
}
1
2
3
4
5
6
7

2.7 交换、清理、返回元素个数、判空

//交换
void swap(const list<T>& lt)
{
	std::swap(_head, lt._head);
}
//清理
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
//获取元素个数
size_t size() const
{
	Node* cur = _head->_next;
	size_t count = 0;
	while (cur != _head)
	{
		count++;
		cur = cur->_next;
	}
	return count;
}
//判空
bool empty() const
{
	return _head->_next == _head;
}
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

2.8 获取第一个节点数据和最后一个节点数据

//获取第一个节点数据
T& front()
{
	return _head->_next->_val;
}
const T& front()const
{
	return _head->_next->_val;
}
//获取最后一个节点数据
T& back()
{
	return _head->_prev->_val;
}
const T& back()const
{
	return _head->_prev->_val;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.9 pos位置插入

//pos位置插入
iterator insert(iterator pos, const T& x)
{
	Node* newnode = new Node(x);//创建新节点
	Node* cur = pos._node;//得到pos位置的节点
	Node* Prev = cur->_prev;//pos位置前一个节点
	newnode->_prev = Prev;//Prev<=>newnode
	Prev->_next = newnode;
	newnode->_next = cur;//newnode<=>cur
	cur->_prev = newnode;
	return newnode;//返回
}
1
2
3
4
5
6
7
8
9
10
11
12

2.10 pos位置删除

//pos位置删除
iterator erase(iterator pos)
{
	assert(pos != _head);//pos不能是哨兵位节点
	Node* cur = pos._node; // 得到pos位置的节点
	Node* Prev = cur->_prev;//pos位置前一个节点
	Node* Next = cur->_next;//pos位置后一个节点
	Prev->_next = Next;//Prev<=>Next
	Next->_prev = Prev;
	delete cur;//清理cur
	return Next;//返回
}
1
2
3
4
5
6
7
8
9
10
11
12

2.11 尾插、尾删、头插、头删

复用begin 和 end

//尾插
void push_back(const T& x)
{
	insert(end(), x);
}
//头插
void push_front(const T& x)
{
	insert(begin(), x);
}
//尾删
void pop_back()
{
	erase(--end());
}
//头删
void pop_front()
{
	erase(begin());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.12 迭代器遍历

分为两种：

• 正向——begin+end
• 反向——rbegin+rend

begin返回第一个节点的位置，end返回最后一个节点的下一个位置

//正向迭代器遍历
iterator begin()
{
	return _head->_next;
}
iterator end()
{
	return _head;
}
const_iterator begin() const
{
	return _head->_next;
}
const_iterator end() const
{
	return _head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

rbegin返回最后一个节点的下一个位置，rend返回第一个节点的位置

//反向迭代器遍历
reverse_iterator rbegin()
{
	return end();
}
reverse_iterator rend()
{
	return begin();
}
const_reverse_iterator rbegin() const
{
	return end();
}
const_reverse_iterator rend() const
{
	return begin();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3 正向迭代器类

迭代器类是对迭代器的行为另作处理。在vector里，iterator++就是正常的++，因为空间是连续的。但是list不是，如果还是像前面的++一样就不会指向下一个节点，因为list的每个节点是独立的空间，不连续，所以要对迭代器的++、–等操作符作封装，重新定义它们的行为。

	template<class T, class Ref, class Ptr>
	struct ListIterator//正向迭代器类
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> self;
		Node* _node;
		//构造
		ListIterator(Node* x)
			:_node(x)
		{}
		//前置++
		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;//返回临时对象，不能引用
		}
		// *
		Ref operator*()
		{
			return _node->_val;//返回该节点的数据
		}
		// ->
		Ptr operator->()
		{
			return &_node->_val;//返回该节点的数据的成员(数据是自定义类型)
		}
		//判断不相等
		bool operator!=(const self& lt)
		{
			return _node != lt._node;
		}
		//判断相等
		bool operator==(const self& lt)
		{
			return _node == lt._node;
		}
	};
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

这里的Ref、Ptr是模板参数，这样写更方便，不管传过来的是const类型还是非const类型，都可以在一段代码里处理好，减少了代码冗余。

在list类里重命名：

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
1
2

4 反向迭代器类

反向迭代器类其实是对正向迭代器作了一层封装，它的第一个模板参数是iterator，后面两个与正向迭代器相同，作用在rbegin和rend函数上。

下面的图可以知道正、反向迭代器在链表里的位置：

可以看出，它们是对称的。但由于是这样的结构，所以反向迭代器的++、- - 以及解引用操作就会有些不一样。

	template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator//反向迭代器类
	{
		typedef ReverseIterator<Iterator, Ref, Ptr> self;	
		
		Iterator cur;
		ReverseIterator(Iterator x)
			:cur(x)
		{}
		//前置++
		self& operator++()
		{
			--cur;//++就是--
			return *this;
		}
		//后置++
		self operator++(int)
		{
			Iterator tmp = cur;
			--cur;
			return tmp;
		}
		//前置--
		self& operator--()
		{
			++cur;//--就是++
			return *this;
		}
		//后置--
		self operator--(int)
		{
			Iterator tmp = cur;
			++cur;
			return tmp;
		}
		// *  解引用前一个位置的元素
		Ref operator*()
		{
			Iterator tmp = cur;
			--tmp;
			return *tmp;
		}
		// ->
		Ptr operator->()
		{
			return &(operator*());//复用
		}
		//判断不相等
		bool operator!=(const self& it)
		{
			return cur != it.cur;
		}
		//判断相等
		bool operator==(const self& it)
		{
			return cur == it.cur;
		}
	};
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

在list类里重命名：

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;
1
2

5 全部代码

list.h

#include <iostream>
#include <assert.h>
using namespace std;

namespace yss
{
	template<class T>
	struct ListNode//节点类
	{
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _val;

		ListNode(const T& x = T())
			:_prev(nullptr)
			,_next(nullptr)
			,_val(x)
		{}
	};

	template<class T, class Ref, class Ptr>
	struct ListIterator//正向迭代器类
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> self;
		Node* _node;
		//构造
		ListIterator(Node* x)
			:_node(x)
		{}

		//前置++
		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;
		}

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

		//判断不相等
		bool operator!=(const self& lt)
		{
			return _node != lt._node;
		}
		//判断相等
		bool operator==(const self& lt)
		{
			return _node == lt._node;
		}

	};

	template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator//反向迭代器类
	{
		typedef ReverseIterator<Iterator, Ref, Ptr> self;	
		
		Iterator cur;
		ReverseIterator(Iterator x)
			:cur(x)
		{}

		//前置++
		self& operator++()
		{
			--cur;
			return *this;
		}
		//后置++
		self operator++(int)
		{
			Iterator tmp = cur;
			--cur;
			return tmp;
		}
		//前置--
		self& operator--()
		{
			++cur;
			return *this;
		}
		//后置--
		self operator--(int)
		{
			Iterator tmp = cur;
			++cur;
			return tmp;
		}
		// *  解引用前一个位置的元素
		Ref operator*()
		{
			Iterator tmp = cur;
			--tmp;
			return *tmp;
		}
		// ->
		Ptr operator->()
		{
			return &(operator*());
		}
		//判断不相等
		bool operator!=(const self& it)
		{
			return cur != it.cur;
		}
		//判断相等
		bool operator==(const self& it)
		{
			return cur == it.cur;
		}
	};

	template<class T>
	class list//模拟实现list
	{
	public:
		typedef ListNode<T> Node;

		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;

		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
		typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

		//正向迭代器遍历
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		const_iterator end() const
		{
			return _head;
		}

		//反向迭代器遍历
		reverse_iterator rbegin()
		{
			return end();
		}
		reverse_iterator rend()
		{
			return begin();
		}
		const_reverse_iterator rbegin() const
		{
			return end();
		}
		const_reverse_iterator rend() const
		{
			return begin();
		}

		// 初始化
		void Init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		//无参构造
		list()
		{
			Init();
		}
		//有参构造1
		list(int n, const T& x = T())
		{
			Init();
			while (n--)
			{
				push_back(x);
			}
		}
		//有参构造2
		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			Init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//交换
		void swap(const list<T>& lt)
		{
			std::swap(_head, lt._head);
		}

		//拷贝构造
		list(const list<T>& lt)
		{
			Init();
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}

		//赋值重载
		//写法1
		/*list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}*/
		//写法2
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		//清理
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		//析构
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		//获取元素个数
		size_t size() const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}
			return count;
		}

		//判空
		bool empty() const
		{
			return _head->_next == _head;
		}

		//获取第一个节点数据
		T& front()
		{
			return _head->_next->_val;
		}
		const T& front()const
		{
			return _head->_next->_val;
		}
		//获取最后一个节点数据
		T& back()
		{
			return _head->_prev->_val;
		}
		const T& back()const
		{
			return _head->_prev->_val;
		}

		//尾插
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		//头插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		//尾删
		void pop_back()
		{
			erase(--end());
		}
		//头删
		void pop_front()
		{
			erase(begin());
		}

		//pos位置插入
		iterator insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);//创建新节点
			Node* cur = pos._node;//得到pos位置的节点
			Node* Prev = cur->_prev;//pos位置前一个节点
			newnode->_prev = Prev;//Prev<=>newnode
			Prev->_next = newnode;
			newnode->_next = cur;//newnode<=>cur
			cur->_prev = newnode;
			return newnode;//返回
		}
		//pos位置删除
		iterator erase(iterator pos)
		{
			assert(pos != _head);//pos不能是哨兵位节点
			Node* cur = pos._node; // 得到pos位置的节点
			Node* Prev = cur->_prev;//pos位置前一个节点
			Node* Next = cur->_next;//pos位置后一个节点
			Prev->_next = Next;//Prev<=>Next
			Next->_prev = Prev;
			delete cur;//清理cur
			return Next;//返回
		}

	private:
		Node* _head;
	};
}
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

test.cpp

#include "list.h"
int main()
{
	/*yss::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_front(100);
	lt.push_front(200);
	lt.push_front(300);
	lt.pop_back();
	lt.pop_front();
	lt.pop_front();
	auto it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;*/

	yss::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	yss::list<int>::reverse_iterator it = lt.rbegin();
	while (it != lt.rend())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	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