一.list介绍
list底层是一个双向带头循环链表，这个我们以前用C语言模拟实现过，->双向带头循环链表
下面是list的文档介绍： list文档介绍
我们会根据 list 的文档来模拟实现 list 的增删查改及其它接口。
二.list模拟实现思路
既然是用C++模拟实现的，那么一定要封装在类里。
为了适合各种类型的数据，会使用模板。
节点 Node
了解双向循环带头链表的都知道，我们需要一个节点 （Node），之前用C语言实现的时候，我们写了一个叫做 BuynewNode 的函数来获取节点，而在C++里我们用类封装一个，注意这个用 struct 封装比较好，因为 struct 默认是公有的，这样方便我们访问，所以可以写一个类：
struct list_node
迭代器 iterator
我们知道，C++提供了一种统一的方式来访问容器，这就是迭代器，string 和 vector 的迭代器模拟实现很简单，因为 string 和 vector 底层是用数组实现的，数组是一段连续的物理空间，支持随机访问，所以它是天然的迭代器；
但是链表不一样，它不是一段连续的物理空间，不支持随机访问，所以想让 list 的迭代器在表面上和 string，vector 的迭代器用起来没有区别，我们在底层上就需要用类封装迭代器，然后再迭代器类的内部，重载 ++ -- * -> != == 这些迭代器会用到的运算符；
所以创建一个迭代器类：
struct list_iterator
const 迭代器 const_iterator
实现的普通的迭代器，还有 const 迭代器，const 迭代器的意思是让指针指向的内容不变，而指针本身可以改变，例如指针++，指针-- 这种操作，所以 const 迭代器与普通迭代器的不同只有 重载 * 运算符的返回值不同，它是 const T& （T是模板参数），重写一个const 迭代器类又显得太冗余，代码的可读性就降低了；
前面在学习模板时，我们知道不同的模板参数，编译器会生成不同的函数，所以我们选择加一个模板参数 ：Ref 。这样只要在显示实例化模板参数时：
普通迭代器就传 T&；
const 迭代器就传 const T&；
-> 运算符重载
看下面这段代码：
1. using namespace std; 2. 3. struct A 4. { 5. A(int a1,int a2) 6. :_a1(a1) 7. ,_a2(a2) 8. {} 9. 10. int _a1; 11. int _a2; 12. }; 13. 14. void test_list() 15. { 16. list<A> lt; //实例化自定义类型 17. lt.push_back(A(1, 1)); 18. lt.push_back(A(2, 2)); 19. lt.push_back(A(3, 3)); 20. lt.push_back(A(4, 4)); 21. 22. list<A>::iterator it = lt.begin(); 23. 24. while (it != lt.end()) 25. { 26. cout << it->_a1 << " " << it->_a2 << endl; //像指针一样访问自定义类型里的成员变量 27. it++; 28. } 29. } 30. 31. int main() 32. { 33. test_list(); 34. 35. return 0; 36. }
有时候，实例化的模板参数是自定义类型，我们想要像指针一样访问访问自定义类型力的成员变量，这样显得更通俗易懂，所以就要重载 -> 运算符，它的返回值是 T* ，但是正常来说这里应该是这样访问的： it -> -> _a1
因为迭代器指向的是 整个自定义类型，要想再访问其内部成员应该再使用一次 -> （这个->就不是重载的 -> ，就是普通的 -> ），但是上面的代码为什么就写了一个 -> ，这个是C++语法把这里特殊化了。
那该怎么在迭代器类里重载 -> 运算符呢？
和const 迭代器一样，只需要再加一个模板参数 ：Ptr
显示实例化的时候传 T* 就行了。
迭代器类 模拟实现源码： struct list_iterator
以上的都算 list 模拟实现的难点，其他的像 重载 ++ 什么的，对于学过数据结构的小伙伴们是非常简单的，就不赘述了，没学过的可以看看这篇文章：双向带头循环链表
1. template<class T,class Ref,class Ptr> //三个模板参数 2. struct list_iterator //封装迭代器 3. { 4. typedef list_node<T> Node; //重命名节点 5. typedef list_iterator<T, Ref, Ptr> self; //重命名迭代器类型 6. Node* _node; 7. 8. list_iterator(Node*node) //构造函数，单参数的构造函数支持隐式类型转换 9. :_node(node) 10. {} 11. 12. //重载 * ++ -- != == -> 13. Ref operator*() const 14. { 15. return _node->_val; 16. } 17. 18. Ptr operator->() const 19. { 20. return &_node->_val; 21. } 22. 23. self& operator++() //前置++ 24. { 25. _node = _node->_next; 26. 27. return *this; 28. } 29. 30. self operator++(int) //后置++ 31. { 32. self tmp = *this; 33. _node = _node->_next; 34. 35. return tmp; 36. } 37. 38. self& operator--() //前置-- 39. { 40. _node = _node->_prev; 41. 42. return *this; 43. } 44. 45. self operator--(int) //后置-- 46. { 47. self tmp = *this; 48. _node = _node->_prev; 49. 50. return tmp; 51. } 52. 53. bool operator!=(const self& lt) const 54. { 55. return _node != lt._node; 56. } 57. 58. bool operator==(const self& lt) const 59. { 60. return _node == lt._node; 61. } 62. 63. };
list
我们在用C语言实现双向带头循环链表时，会先初始化链表的头（head），即让它的 前驱指针（prev）和后继指针（next）都指向自己；
在C++的模拟实现 list 中，我们会创建一个类 list 来管理链表的节点并实现增删查改及其它接口，所以 list 的构建函数就是初始化 头（head）节点。
三.源码
list.h
我们可以模拟实现以上接口，具体函数的逻辑可以查阅文档，实现起来都是很简单的。
1. namespace nagi //把模拟实现list的类都放在一个命名空间里封装起来 2. { 3. template<class T> 4. struct list_node //创建节点 5. { 6. list_node<T>* _prev; 7. list_node<T>* _next; 8. T _val; 9. 10. list_node(const T& val = T()) //构造函数，初始化节点 11. :_prev(nullptr) 12. ,_next(nullptr) 13. ,_val(val) 14. {} 15. 16. }; 17. 18. template<class T,class Ref,class Ptr> //三个模板参数 19. struct list_iterator //封装迭代器 20. { 21. typedef list_node<T> Node; 22. typedef list_iterator<T, Ref, Ptr> self; 23. Node* _node; 24. 25. list_iterator(Node*node) //构造函数，单参数的构造函数支持隐式类型转换 26. :_node(node) 27. {} 28. 29. //重载 * ++ -- != == -> 30. Ref operator*() const 31. { 32. return _node->_val; 33. } 34. 35. Ptr operator->() const 36. { 37. return &_node->_val; 38. } 39. 40. self& operator++() //前置++ 41. { 42. _node = _node->_next; 43. 44. return *this; 45. } 46. 47. self operator++(int) //后置++ 48. { 49. self tmp = *this; 50. _node = _node->_next; 51. 52. return tmp; 53. } 54. 55. self& operator--() //前置-- 56. { 57. _node = _node->_prev; 58. 59. return *this; 60. } 61. 62. self operator--(int) //后置-- 63. { 64. self tmp = *this; 65. _node = _node->_prev; 66. 67. return tmp; 68. } 69. 70. bool operator!=(const self& lt) const 71. { 72. return _node != lt._node; 73. } 74. 75. bool operator==(const self& lt) const 76. { 77. return _node == lt._node; 78. } 79. 80. }; 81. 82. template<class T> 83. class list 84. { 85. typedef list_node<T> Node; 86. public: 87. typedef list_iterator<T, T&, T*> iterator; //重命名普通迭代器 88. typedef list_iterator<T, const T&, const T*> const_iterator; //重命名const迭代器 89. 90. void empty_init() //因为构造函数和拷贝构造都会初始化头节点，所以就写成一个函数了 91. { 92. _head = new Node; 93. _head->_prev = _head; 94. _head->_next = _head; 95. _sz = 0; 96. } 97. 98. list() //构造函数 99. { 100. empty_init(); 101. } 102. //普通迭代器 103. iterator begin() 104. { 105. return _head->_next; 106. } 107. 108. iterator end() 109. { 110. return _head; 111. } 112. //const迭代器 113. const_iterator begin() const 114. { 115. return _head->_next; 116. } 117. 118. const_iterator end() const 119. { 120. return _head; 121. } 122. 123. iterator insert(iterator pos, const T& x) //在pos之前插入 124. { 125. Node* newnode = new Node(x); 126. Node* cur = pos._node; 127. Node* prev = cur->_prev; 128. prev->_next = newnode; 129. newnode->_prev = prev; 130. newnode->_next = cur; 131. cur->_prev = newnode; 132. _sz++; 133. 134. return newnode; 135. } 136. 137. iterator erase(iterator pos) //删除pos位置，注意删除的时候不能把头节点也删了，所以要做pos检查 138. { 139. assert(pos != end()); 140. 141. Node* cur = pos._node; 142. Node* prev = cur->_prev; 143. Node* next = cur->_next; 144. 145. prev->_next = next; 146. next->_prev = prev; 147. 148. delete cur; 149. _sz--; 150. 151. return next; //库里规定返回删除节点的下一个节点 152. } 153. 154. void push_back(const T& x) //尾插 155. { 156. insert(end(), x); 157. } 158. 159. void push_front(const T& x) //头插 160. { 161. insert(begin(), x); 162. } 163. 164. void pop_back() //尾删 165. { 166. erase(--end()); 167. } 168. 169. void pop_front() //头删 170. { 171. erase(begin()); 172. } 173. 174. void clear() //清楚除了头节点以外的所有节点 175. { 176. iterator it = begin(); 177. while (it != end()) 178. { 179. it=erase(it); 180. 181. } 182. _sz = 0; 183. } 184. 185. ~list() //析构函数 186. { 187. clear(); 188. 189. delete _head; 190. _head = nullptr; 191. } 192. 193. list(const list<T>& lt) //拷贝构造 194. { 195. empty_init(); 196. 197. for (auto& e : lt) 198. { 199. push_back(e); 200. } 201. 202. } 203. 204. void swap(list<T>& lt) 205. { 206. std::swap(_head, lt._head); 207. std::swap(_sz, lt._sz); 208. } 209. 210. list<T>& operator=(list<T> lt) //赋值重载 211. { 212. swap(lt); 213. 214. return *this; 215. } 216. 217. private: 218. Node* _head; //头节点 219. size_t _sz; //记录链表的长度 220. }; 221. 222. }
🐬🤖本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；🕊️👻
😄😆希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；🥰🤩
😍😁谢谢你的阅读。😸😼
