Technology Sharing

The underlying implementation of C list container

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. What is a list?

list is a headed doubly linked list in C++ container. The head node does not store data. The next element of the head node is the first element storing data. The previous element of the head node is connected to the last element storing data. (The structure is shown in the figure below)

The structure of each node in the linked list is divided into a data part, a front pointer and a back pointer (the following is a structure diagram and code)

2. List code implementation and syntax analysis

2.1 Defining the structure of the node

The types of data and front and back pointers in the linked list are generated by templates and can adapt to built-in types and custom types.The reason why struct is used to define the class here is that the default member variable types of struct are all public, so other functions can call them easily.There is also a list_node constructor T() here, which is an anonymous variable. Its function is not only to store data. In addition, if no parameters are written when calling the list_node constructor, there will also be a default value.

2.2 Define the structure of the linked list

In the list, there are two member variables: a pointer to the node type _node and a pointer to the number of nodes _size.

  1. template<class T>
  2. class list
  3. {
  4. typedef list_node<T> Node;
  5. void empty_init()
  6. {
  7.     _head = new Node;
  8.     _head -> next = _head;
  9.     _head -> prev = _head;
  10.     _size = 0;
  11. }
  12. list()
  13. {
  14.     empty_init();
  15. }
  16.     private:
  17.         Node* _node;
  18.         size_t _size;
  19. }

2.3 Add linked list function (insert push_back)

Now that we have defined the basic structure of the list, we are going to add some basic functionality, such as inserting data into the list and traversing the list with iterators.

Push_back function: First, build a new node newnode, then store the data X to be stored in newnode, find the tail node and insert newnode into the next node of the tail node.

  1. template<class T>
  2. struct list_node
  3. {
  4. 	T _data;
  5. 	list_node<T>* _next;
  6. 	list_node<T>* _prev;
  7. 	list_node(const T& x=T())
  8. 		:_data(x)
  9. 		, _next(nullptr)
  10. 		, _prev(nullptr)
  11. 	{
  12.  
  13. 	}
  14. };
  15.  
  16. template<class T>
  17. class list
  18. {
  19. typedef list_node<T> Node;
  20. void empty_init()
  21. {
  22.     _head = new Node;
  23.     _head -> next = _head;
  24.     _head -> prev = _head;
  25.     _size = 0;
  26. }
  27. list()
  28. {
  29.     empty_init();
  30. }
  31. void push_back(const T& x)
  32. {
  33.     Node* newnode = new Node(x);
  34.     Node* tail = _head->prev;
  35.  
  36.     tail->_next = newnode;
  37.     newnode->prev = tail;
  38.  
  39.     newnode->_next = _head;
  40.     _head->prev = newnode;
  41.     
  42.     _size++; 
  43. }
  44.     private:
  45.         Node* _node;
  46.         size_t _size;
  47. }

2.4 Adding linked list functionality (iterators and iterator operator overloading)

Unlike sequential lists, because the nodes of linked lists are not stored together in a continuous space, there is no way to directly obtain data by using pointer ++ and dereference. Therefore, we need to overload operators such as * -&gt; ++ -- and so on.

  1. template<class T>
  2. struct list_node
  3. {
  4. 	T _data;
  5. 	list_node<T>* _next;
  6. 	list_node<T>* _prev;
  7. 	list_node(const T& x=T())
  8. 		:_data(x)
  9. 		, _next(nullptr)
  10. 		, _prev(nullptr)
  11. 	{
  12.  
  13. 	}
  14. };
  15. template<class T>
  16. struct __list_iterator
  17. {
  18.     typedef list_node<T> Node;
  19.     typedef __list_iterator self;
  20.  
  21.     Node* _node;
  22.     __list_iterator(Node* node)
  23.         :_node(node)
  24.     {
  25.  
  26.     }
  27.     
  28.     T& operator *(Node * node)
  29.     {
  30.         return _node->_data;
  31.     }
  32.  
  33.     T* operator(Node * node)
  34.     {
  35.         return &_node->_data;
  36.     }
  37.     self& operator++()
  38.     {
  39.         _node = _node->next;
  40.         return *this;
  41.     }
  42.     
  43.     self& operator--()
  44.     {
  45.         _node = _node->prev;
  46.         return *this;
  47.     }
  48.  
  49.     bool operator!=(const self& s)
  50.     {
  51.         return _node != s._node;
  52.     }
  53. }
  54.  
  55. template<class T>
  56. class list
  57. {
  58. typedef list_node<T> Node;
  59. typedef __list_iterator<T> iterator;
  60.  
  61. iterator begin()
  62. {
  63.     return iterator(_head->next);
  64. }
  65.  
  66. iterator end()
  67. {
  68.     return iterator(_head);
  69. }
  70.  
  71. void empty_init()
  72. {
  73.     _head = new Node;
  74.     _head -> next = _head;
  75.     _head -> prev = _head;
  76.     _size = 0;
  77. }
  78.  
  79. list()
  80. {
  81.     empty_init();
  82. }
  83.  
  84. void push_back(const T& x)
  85. {
  86.     Node* newnode = new Node(x);
  87.     Node* tail = _head->prev;
  88.  
  89.     tail->_next = newnode;
  90.     newnode->prev = tail;
  91.  
  92.     newnode->_next = _head;
  93.     _head->prev = newnode;
  94.     
  95.     _size++; 
  96. }
  97.     private:
  98.         Node* _node;
  99.         size_t _size;
  100. }

After completing the above operations, we can debug the program in this way. Although List is not an array, we can access the elements inside List in a similar way.Although the way iterators iterate over each element of a container is the same, iterators mask the details of the underlying implementation and provide a unified access method.。

  1. test_list()
  2. {
  3.     list<int> lt;
  4.     lt.push_back(1);
  5.     lt.push_back(2);
  6.     lt.push_back(3);
  7.     list<int>::iterator it = lt.begin();
  8.  
  9.     while(it != lt.end())
  10.     {
  11.         cout << *it << " ";
  12.         ++it;
  13.     }
  14.     cout<< endl;
  15. }

2.5 Add linked list function (upgrade insert() and eraser() for insert operation)

First, we can write an insert() function, which can be reused by other functions such as push_back and push_front, and can also insert data at any position.

  1. iterator insert(iterator pos , const T& x)
  2. {
  3.     Node* newnode = new Node(x);
  4.     Node* cur = pos._node;
  5.     Node* prev = cur ->_prev;
  6.     
  7.     prev->_next = newnode;
  8.     newnode->_prev = prev;
  9.     newnode->_next = cur;
  10.     cur->_prev = newnode;
  11.  
  12.     return newnode; 
  13. }
  14.  
  15. iterator erase(iterator pos)
  16. {
  17.     Node* cur = pos._node;
  18.     Node* prev = cur->_prev;
  19.     Node* next = cur->_next;
  20.  
  21.     delete cur;
  22.     prev->_next = next;
  23.     next->_prev = prev;
  24.  
  25.     return next;
  26. }
  27.  
  28. void push_back(const T& x)
  29. {
  30.     insert(this.end(),x);
  31. }
  32.  
  33. void push_front(const T& x)
  34. {
  35.     insert(begin(),x);
  36. }
  37.  
  38. void pop_back()
  39. {
  40.     erase(--end());
  41. }
  42.  
  43. void pop_front()
  44. {
  45.     erase(begin());
  46. }

2.6 Add linked list function (clear function and destructor)

Because the return value of the erase function is the next location of the deleted data, the effect of ++ will be achieved even if ++ is not written here.

  1. ~list()
  2. {
  3.     clear();
  4.     delete _head;
  5.     _head = nullpre;
  6. }
  7.  
  8. void clear()
  9. {
  10.     iterator it = begin();
  11.     while(it != end())
  12.     {
  13.         it = erase(*it);
  14.     }
  15. }

2.7 Add linked list function (copy construction and assignment overload)

(1) Copy construction

  1. list( list<int> lt )
  2. {
  3.     empty_init();
  4.     for(auto e : lt)
  5.     {
  6.         this.push_back(e);
  7.     }
  8. }

(2) Assignment overloading

  1. 		void swap(list<T>& lt)
  2. 		{
  3. 			std::swap(_head, lt._head);
  4. 			std::swap(_size, lt._size);
  5. 		}
  6. 		list<int>& operator=(list<int> lt)
  7. 		{
  8. 			swap(lt);
  9. 			return *this;
  10. 		}

2.8 const iterators

For const iterators, we need to understand thatA const iterator cannot modify the data pointed to by the iterator, not that the iterator itself cannot be modified.The iterator itself needs to complete operations such as ++, -- to perform traversal operations, so when writing a const type iterator, I only modify the function that returns the content pointed to by the iterator with const, and the other functions remain unchanged.

  1. template<class T>
  2. struct __list_const_iterator
  3. {
  4. 	typedef list_node<T> Node;
  5. 	typedef __list_const_iterator<T> self;
  6. 	Node* _node;
  7. 	__list_const_iterator(Node* node)
  8. 		:_node(node)
  9. 	{
  10.  
  11. 	}
  12. 	
  13. 	const T& operator *()
  14. 	{
  15. 		return _node->_data;
  16. 	}
  17. 	const T* operator->()
  18. 	{
  19. 		return &_node->_data;
  20. 	}
  21. };

3. Complete code

  1. #pragma once
  2. #include<iostream>
  3. using namespace std;
  4. namespace hjy
  5. {
  6. 	template<class T>
  7. 	struct list_node
  8. 	{
  9. 		T _data;
  10. 		list_node<T>* _next;
  11. 		list_node<T>* _prev;
  12. 		list_node(const T& x=T())
  13. 			:_data(x)
  14. 			, _next(nullptr)
  15. 			, _prev(nullptr)
  16. 		{
  17.  
  18. 		}
  19. 	};
  20. 	template<class T,class Ref,class Ptr>
  21. 	struct __list_iterator
  22. 	{ 
  23. 		typedef list_node<T> Node;
  24. 		typedef __list_iterator<T,Ref,Ptr> self;
  25. 		Node* _node;
  26. 		__list_iterator(Node* node)
  27. 			:_node(node)
  28. 		{
  29.  
  30. 		}
  31. 		self& operator ++()
  32. 		{
  33. 			_node = _node->_next;
  34. 			return *this;
  35. 		}
  36. 		self& operator --()
  37. 		{
  38. 			_node = _node->_prev;
  39. 			return *this;
  40. 		}
  41. 		self operator ++(int)
  42. 		{
  43. 			self tmp(*this);
  44. 			_node = _node->_next;
  45. 			return tmp;
  46. 		}
  47. 		self operator --(int)
  48. 		{
  49. 			self tmp(*this);
  50. 			_node = _node->_prev;
  51. 			return tmp;
  52. 		}
  53. 		Ref operator *()
  54. 		{
  55. 			return _node->_data;
  56. 		}
  57. 		Ptr operator->()
  58. 		{
  59. 			return &_node->_data;
  60. 		}
  61. 		bool operator!=(const self& s)
  62. 		{
  63. 			return _node != s._node;
  64. 		}
  65. 	};
  66. 	/*template<class T>
  67. 	struct __list_const_iterator
  68. 	{
  69. 		typedef list_node<T> Node;
  70. 		typedef __list_const_iterator<T> self;
  71. 		Node* _node;
  72. 		__list_const_iterator(Node* node)
  73. 			:_node(node)
  74. 		{
  76. 		}
  77. 		self& operator ++()
  78. 		{
  79. 			_node = _node->_next;
  80. 			return *this;
  81. 		}
  82. 		self& operator --()
  83. 		{
  84. 			_node = _node->_prev;
  85. 			return *this;
  86. 		}
  87. 		self operator ++(int)
  88. 		{
  89. 			self tmp(*this);
  90. 			_node = _node->_next;
  91. 			return tmp;
  92. 		}
  93. 		self operator --(int)
  94. 		{
  95. 			self tmp(*this);
  96. 			_node = _node->_prev;
  97. 			return tmp;
  98. 		}
  99. 		const T& operator *()
  100. 		{
  101. 			return _node->_data;
  102. 		}
  103. 		const T* operator->()
  104. 		{
  105. 			return &_node->_data;
  106. 		}
  107. 		bool operator!=(const self& s)
  108. 		{
  109. 			return _node != s._node;
  110. 		}
  111. 	};*/
  112. 	template<class T>
  113. 	class list
  114. 	{
  115. 		typedef list_node<T>  Node;
  116. 	public:
  117. 		typedef __list_iterator<T,T&,T*> iterator;
  118. 		typedef __list_iterator<T, const T&, const T*> const_iterator;
  119. 		//typedef __list_const_iterator<T> const_iterator;
  120.  
  121. 		const_iterator begin()const
  122. 		{
  123. 			return const_iterator(_head->_next);
  124. 		}
  125. 		const_iterator end()const
  126. 		{
  127. 			return const_iterator(_head);
  128. 		}
  129.  
  130. 		iterator begin()
  131. 		{
  132. 			return _head->_next;
  133. 		}
  134. 		iterator end()
  135. 		{
  136. 			return _head;
  137. 		}
  138. 		void empty_init()
  139. 		{
  140. 			_head = new Node;
  141. 			_head->_next = _head;
  142. 			_head->_prev = _head;
  143. 			_size = 0;
  144. 		}
  145. 		list()
  146. 		{
  147. 			empty_init();
  148. 		}
  149. 		//list<int>& operator=(const list<int>& lt) 传统写法
  150. 		//{
  151. 		//	if (this != &lt)
  152. 		//		clear();
  153. 		//	for (auto e : lt)
  154. 		//	{
  155. 		//		push_back(e);
  156. 		//	}
  157. 		//	return *this;
  158. 		//}
  159. 		void swap(list<T>& lt)
  160. 		{
  161. 			std::swap(_head, lt._head);
  162. 			std::swap(_size, lt._size);
  163. 		}
  164. 		list<int>& operator=(list<int> lt)
  165. 		{
  166. 			swap(lt);
  167. 			return *this;
  168. 		}
  169. 		~list()
  170. 		{
  171. 			clear();
  172. 			delete _head;
  173. 			_head = nullptr;
  174. 		}
  175. 		//list(const list<T>& lt)//没有const迭代器所以这样写不行
  176. 		//{
  177. 		//	empty_init();
  178. 		//	for (auto e : lt)
  179. 		//	{
  180. 		//		push_back(e);
  181. 		//	}
  182. 		//}
  183. 		list( list<T>& lt)
  184. 		{
  185. 			empty_init();
  186. 			for (auto e : lt)
  187. 			{
  188. 				push_back(e);
  189. 			}
  190. 		}
  191. 		void push_back(const T& x)
  192. 		{
  193. 			insert(end(), x);
  194. 		}
  195. 		void push_front(const T& x)
  196. 		{
  197. 			insert(begin(), x);
  198. 		}
  199. 		void pop_front()
  200. 		{
  201. 			erase(begin());
  202. 		}
  203. 		void pop_back()
  204. 		{
  205. 			erase(end()--);
  206. 		}
  207. 		void clear()
  208. 		{
  209. 			iterator it = begin();
  210. 			while (it != end())
  211. 			{
  212. 				it = erase(it);
  213. 			}
  214. 		}
  215. 		iterator insert(iterator pos, const T& val)
  216. 		{
  217. 			Node* cur = pos._node;
  218. 			Node* newnode = new Node(val);
  219. 			Node* prev = cur->_prev;
  220. 			prev->_next = newnode;
  221. 			newnode->_prev = prev;
  222. 			newnode->_next = cur;
  223. 			cur->_prev = newnode;
  224. 			++_size;
  225. 			return iterator(newnode);
  226. 		}
  227. 		iterator erase(iterator pos)
  228. 		{
  229. 			Node* cur = pos._node;
  230. 			Node* prev = cur->_prev;
  231. 			Node* next = cur->_next;
  232. 			delete cur;
  233. 			prev->_next = next;
  234. 			next->_prev = prev;
  235. 			--_size;
  236. 			return iterator(next);
  237. 		}
  238. 		size_t size()
  239. 		{
  240. 			return _size;
  241. 		}
  242. 	private:
  243. 		Node* _head;
  244. 		size_t _size;
  245. 	};
  246. 	void test_list1()
  247. 	{
  248. 		list<int>lt;
  249. 		lt.push_back(1);
  250. 		lt.push_back(2);
  251. 		lt.push_back(3);
  252. 		lt.push_back(4);
  253. 		lt.push_back(5);
  254. 		for (auto e : lt)
  255. 			cout << e << " ";
  256. 		cout << endl;
  257.  
  258. 		list<int>lt1 = lt;
  259. 		for (auto e : lt1)
  260. 			cout << e << " ";
  261. 		cout << endl;
  262.  
  263. 	}
  264. 	/*void print_list(const list<int>& lt)
  265. 	{
  266. 		list<int>::const_iterator it = lt.begin();
  267. 		while (it != lt.end())
  268. 		{
  269. 			cout << *it << " ";
  270. 			++it;
  271. 		}
  272. 		cout << endl;
  273. 		for (auto e : lt)
  274. 		{
  275. 			cout << e << " ";
  276. 		}
  277. 		cout << endl;
  278. 	}*/
  279. 	template<typename T>
  280. 	void print_list(const list<T>& lt)
  281. 	{
  282. 		typename list<T>::const_iterator it = lt.begin();
  283. 		while (it != lt.end())
  284. 		{
  285. 			cout << *it << " ";
  286. 			++it;
  287. 		}
  288. 		cout << endl;
  289. 	}
  290. 	void test_list2()
  291. 	{
  292. 		list<string>lt;
  293. 		lt.push_back("111");
  294. 		lt.push_back("111");
  295. 		lt.push_back("111");
  296. 		print_list(lt);
  297. 	}
  298. }

Personal profile

I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages ​​such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.

my contact information

Mail