链表 Linked List

2024.3.15
芝士wa
参考视频：bilibli-数据结构-链表  “印度小哥讲得真好”
链表

• 对于链表来说，存储数据需要两个部门，一是数据本身，二是指针，该指针指向下一个数据的地址，依次链接，直到末了一个元素，指针指向空（NULL）
  

• 遍历的时间复杂度为O(n)
  
• 插入的时间复杂度为O(n)
  
• 删除的时间复杂度为O(n)
  

链表VS数组

• 数组是连续存储空间，链表通过指针维系，存储数据并不连续
  
• 数组可以通过下标访问元素，只需要O(1)的时间复杂度，而链表则必须按照顺序访问，因此时间复杂度为O(n/2) = O(n)
  
• 数组的大小是固定的，在创建数组时确认
  
• 上风：链表在添加或删除元素时，制止了不相关元素的复制移动，空间复杂度较小
  
• 使用链表时，要格外注意指针问题
  

链表的C++实现

完整代码

1. #pragma once
2. #include <iostream>
3. using namespace std;
6. template<class T>
7. class Node
8. {
9. public:
10.         T data;
11.         Node* next;
12. };
14. template<class T>
15. class LinkedList
16. {
17. public:
18.         LinkedList();
19.         ~LinkedList();
20.         Node<T>* head;
21.        
22.         int m_num;//记录节点个数
23.         //尾插法
24.         void Insert(T x);
26.         //在特定位置添加
27.         void Insert(T x, int n);
29.         //打印，遍历法
30.         void print();
32.         //递归方法打印
33.         void Rprint(Node<T>* p);
35.         //特定位置删除
36.         void remove(int n);
38.         //反转链表，迭代法
39.         void reverse();
41.         //反转链表，递归方法
42.         void Reverse(Node<T>* p);
43. };
45. template<class T>
46. LinkedList<T>::LinkedList()
47. {
48.         head = new Node<T>;
49.         head->next = NULL;
50.         this->m_num = 0;
51. }
54. template<class T>
55. LinkedList<T>::~LinkedList()
56. {
57.         Node<T>* ite = head;
58.         Node<T>* next;
59.         while (ite != NULL) {
60.                 next = ite->next;
61.                 delete ite;
62.                 ite = next;
63.         }
64.         this->m_num = 0;
65. }
70. template<class T>//尾插法添加元素
71. void LinkedList<T>::Insert(T x)
72. {
73.         Node<T>* end = new Node<T>;
74.         end->data = x;
75.         end->next = NULL;
77.         if (head== NULL) {
78.                 //链表为空
79.                 head = end;
81.                 this->m_num++;
82.                 cout << "添加成功，当前节点数量：" << this->m_num << endl;
83.         }
84.         else {
85.                 Node<T>* ite = head;
86.                 //链表不为空，得到末尾end
87.                 while (ite->next != NULL) {
88.                         ite = ite->next;
89.                 }
90.                 //现在ite指向最后一个元素
91.                 ite->next = end;
92.         }
93.         this->m_num++;
94.         cout << "添加成功，当前节点数量：" << this->m_num << endl;
95. }
98. template<class T>//特定位置添加元素
99. void LinkedList<T>::Insert(T x, int n)
100. {
101.         Node<T>* temp = new Node<T>;
102.         temp->data = x;
103.         temp->next = NULL;
104.         if (n == 1) {
105.                 //在头节点之后添加
106.                 temp->next = head->next;
107.                 head = temp;
109.                 this->m_num++;
110.                 cout << "添加成功，当前节点数量：" << this->m_num << endl;
111.                 return;
112.         }
113.         else if(n > 1 && n <= this->m_num){
114.                 Node<T>* ite = head;
115.                 //找到第n-1个元素，
116.                 for (int i = 0; i <= n - 2; i++) {
117.                         ite = ite->next;
118.                 }
119.                 temp->next = ite->next;
120.                 ite->next = temp;
121.                 this->m_num++;
122.                 cout << "添加成功，当前节点数量：" << this->m_num << endl;
123.                 return;
124.         }
125.         else {
126.                 cout << "越界" << endl;
127.                 return;
128.         }
129. }
131. template<class T>
132. void LinkedList<T>::print()
133. {
134.         Node<T>* ite = head;
135.         while (ite!= NULL) {
136.                 cout << ite->data << "\t";
137.                 ite = ite->next;
138.         }
139.         cout << endl;
140. }
141. template<class T>
142. void LinkedList<T>::Rprint(Node<T> * p)
143. {
144.         if (p == NULL) {
145.                 return;
146.         }
147.         Rprint(p->next);
148.         cout << p->data << "\t";
149. }
151. template<class T>
152. void LinkedList<T>::remove(int n)
153. {
154.         Node<T>* temp = head;
155.         //第一个节点
156.         if (n == 1) {
157.                 head = head->next;
158.                 delete temp;
160.                 this->m_num--;
161.                 cout << "删除成功，当前节点数量：" << this->m_num << endl;
162.                 return;
163.         }
164.         //第2~num之间删除节点
165.         else if (n > 1 && n <= this->m_num) {
166.                 for (int i = 0; i < n - 2; i++) {
167.                         temp = temp->next;
168.                 }
169.        
170.                 //现在temp指向的是第n-1个节点
171.                 Node<T>* temp1 = temp->next;//指向第n个
172.                 temp->next = temp1->next;
173.                 delete temp1;
175.                 this->m_num--;
176.                 cout << "删除成功，当前节点数量：" << this->m_num << endl;
177.                 return;
178.         }
179.         else {
180.                 cout << "越界" << endl;
181.                 return;
182.         }
183.        
184. }
186. template<class T>
187. void LinkedList<T>::reverse()
188. {
189.         Node<T>* current, * prev, * next;
190.         current = head;
191.         prev = NULL;
192.         while (current != NULL) {
193.                 next = current->next;
194.                 current->next = prev;
195.                 prev = current;
196.                 current = next;
197.         }
198.         head = prev;
199. }
201. template<class T>
202. void LinkedList<T>::Reverse(Node<T>* p)
203. {
204.         if (p->next == NULL) {
205.                 head = p;
206.                 return;
207.         }
208.         Reverse(p->next);
209.         p->next->next = p;
210.         p->next = NULL;
211. }

复制代码

• 模板，泛型
  
• 内部维护链表长度
  
• 分别用递归和迭代的方式实现了打印和反转
  
• 进行了简单的越界判定处置惩罚
  

双向链表

1. template<class T>
2. class Node
3. {
4.   T data;
5.   Node* prev;
6.   Node* next;
7. };

复制代码

总结

本文先容了链表的概念和特性，并用C++实现了单链表。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。