c++中list的简单实现

list

介绍

list:
是数据结构中的链表，存储方式是在内存中每一个节点取一段空间用特定的方式链接起来，这样子就不会有浪费的空间
我们用的是带头循环双向链表

节点类(listNode)

因为一个节点中要包含其他信息所以单独弄成一个类

template<class T>
//链表节点类
struct listNode
{
	listNode<T>* _next;//指向下一个节点
	listNode<T>* _prev;//指向上一个节点
	T date;//内容
	
	listNode(const T& x = T())
		:_next(nullptr)
		,_prev(nullptr)
		,date(x)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

__list__iterator(迭代器类)

为什么要有迭代器类呢?
因为我们要封装一下这个迭代器，让迭代器该有的操作在list也可以用出来。
如果在list内部弄迭代器会很不好弄。

//正向迭代器类
//Ref 来区别const和普通
template<class T,class Ref,class Ptr>
struct __list__iterator
{
	typedef listNode<T> Node;//减少代码
	typedef __list__iterator<T,Ref> self;//来控制他的类别
	Node* _node;//节点
	__list__iterator(Node* node)
		:_node(node)
	{}
	//++it
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//it++
	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->date;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
	Ptr operator->()
	{
		return &_node->date;
	}
};
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

operator->

因为这个比较特殊很难看懂所以我们单独解释
他的本质是->->,代码解释更好看懂
因为之前的设计者觉得不好看，所以做的特殊处理

struct MyStruct
{
	int _a1;
	int _a2;
	MyStruct(int _a1 = 1, int _a2 = 1)
		:_a1(_a1)
		,_a2(_a2)
	{

	}
};
void test2()
{
	list<MyStruct> s;
	s.push_back(MyStruct());
	s.push_back(MyStruct());
	s.push_back(MyStruct());//插入的是一个类
	list<MyStruct>::iterator lt = s.begin();
	while (lt != s.end())
	{
		cout << lt->_a1<<":"<< lt->_a2 << " ";//读这个类里面的内容
		//lt->_a1 的本质是 lt.operator->()->_a1; 特殊处理
		++lt;
	}
}
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

list的成员函数

因为我们偷点懒所以把一些东西typedef一下

	typedef listNode<T> Node;
	typedef __list__iterator<T,T&,T*> iterator;
	typedef __list__iterator<T,const T&,const T*> const_iterator;
	typedef Reverselterator<T, T&, T*> reverse_iterator;
1
2
3
4

empty_init() 初始化节点

因为我们要多次用到所以单独写一个出来方便
同时可以用list()套一下他

void empty_init()//初始化节点
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}
1
2
3
4
5
6

list(list& lt) 拷贝构造

简单写法
引用的作用是深拷贝，不要弄成浅拷贝了

list(list<T>& lt)
{
	empty_init();
	for (const auto& ch : lt)
	{
		push_back(ch);
	}
}
1
2
3
4
5
6
7
8

clear() 清除链表

直接把链表清空

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
1
2
3
4
5
6
7
8

~list() 析构

清除之后直接把哨兵位删掉就可以了

~list()
{
	clear();
	delete _head;
}
1
2
3
4
5

insert() 插入

在某个节点之前插入

iterator insert(iterator pos, const T& x)//在摸个节点之前插入
{
	Node* cur = pos._node;//插入的位置
	Node* prev = cur->_prev;//插入的下一个位置
	Node* newnode = new Node(x);//构成节点
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11

erase() 删除

删除某个节点

iterator erase(iterator pos)
{
	assert(pos !=end());//判断他不是哨兵位
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	prev->_next = next;
	next->_prev = prev;

	delete cur;
	return next;
}
1
2
3
4
5
6
7
8
9
10
11
12

push_back() 尾插

注释这段因为和insert中基本上没区别,所以简单化了

void push_back(const T& x)//尾插
{
	/*Node* newnode = new Node(x);
	Node* tail = _head->_prev;//链表尾部节点
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;*/
	insert(end(), x);
}
1
2
3
4
5
6
7
8
9
10

push_front() 头插

void push_front(const T& x)//头插
{
	insert(begin(), x);
}
1
2
3
4

pop_back() 尾删

void pop_back()//尾删
{
	erase(--end());
}
1
2
3
4

pop_front() 头删

void pop_front()//头删
{
	erase(begin());
}
1
2
3
4

begin() 头节点

这里因为是要头节点，所以我们直接把begin设置为第一个节点(有用的节点)

const_iterator begin() const
{
	return _head->_next;
}
1
2
3
4

end() 尾节点

因为end是尾 所以我们把哨兵位当尾，这样子就可以更好的读

const_iterator end() const
{
	return _head;
}
1
2
3
4

总结

可以先尝试一下 自己实现
代码总体加我自己的注释给在这里
实现完可以自己对比一下

template<class T>
//链表节点类
struct listNode
{
	listNode<T>* _next;
	listNode<T>* _prev;
	T date;
	
	listNode(const T& x = T())
		:_next(nullptr)
		,_prev(nullptr)
		,date(x)
	{}
};
	//正向迭代器类
	//Ref 来区别const和普通
	template<class T,class Ref,class Ptr>
	struct __list__iterator
	{
		typedef listNode<T> Node;
		typedef __list__iterator<T,Ref> self;
		Node* _node;
		__list__iterator(Node* node)
			:_node(node)
		{}
		//++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//it++
		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->date;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		bool operator==(const self& s)
		{
			return _node == s._node;
		}
		Ptr operator->()
		{
			return &_node->date;
		}
	};
template<class T>
class list
{
	typedef listNode<T> Node;
public:
	typedef __list__iterator<T,T&,T*> iterator;
	typedef __list__iterator<T,const T&,const T*> const_iterator;
	typedef Reverselterator<T, T&, T*> reverse_iterator;
	const_iterator begin() const
	{
		return _head->_next;
	}
	const_iterator end() const
	{
		return _head;
	}
	iterator begin()
	{
		//return iterator(_head->_next);
		return _head->_next;
	}
	iterator end()
	{
		//return iterator(_head);
		return _head;
	}
	iterator rbegin()
	{
		return end();
	}
	iterator rend()
	{
		return begin();
	}
	void empty_init()//初始化节点
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}
	list()
	{
		empty_init();
	}
	list(list<T>& lt)
	{
		empty_init();
		for (const auto& ch : lt)
		{
			push_back(ch);
		}
	}
	~list()
	{
		clear();
		delete _head;
	}
	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);
		}
	}
	void swap(list<T>& lt)
	{
		std::swap(_head, lt._head);
	}
	list<T>& operator=(list<T> lt)
	{
		swap(lt);
		return *this;
	}
	void push_back(const T& x)//尾插
	{
		/*Node* newnode = new Node(x);
		Node* tail = _head->_prev;//链表尾部节点
		tail->_next = newnode;
		newnode->_prev = tail;
		newnode->_next = _head;
		_head->_prev = newnode;*/
		insert(end(), x);
	}
	void push_front(const T& x)//头插
	{
		insert(begin(), x);
	}
	void pop_back()//尾删
	{
		erase(--end());
	}
	void pop_front()//头删
	{
		erase(begin());
	}
	iterator insert(iterator pos, const T& x)//在摸个节点之前插入
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* newnode = new Node(x);
		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = cur;
		cur->_prev = newnode;
		return newnode;
	}
	iterator erase(iterator pos)
	{
		assert(pos !=end());
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;
		prev->_next = next;
		next->_prev = prev;

		delete 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