双向链表的初始化、插入、删除、遍历

1. /**
2. * @file name ： DoubleLnList.c
3. * @brief     :  实现一个双向不循环链表的接口，可实现链表的增删改查，另外为了提高可移植性，所以链表中
4. *               数据元素的类型为DataType_t，用户可以根据实际情况修改链表中元素的类型
5. * @author    :  MINDSETT@163.com
6. * @date      :  2025/6/30
7. * @version   :  1.0
8. * @note      :  特别说明：此接口实现的双向链表中首结点的直接前驱指针指向NULL,并不是头结点的地址
9. * CopyRight (c)  2025  MINDSETT@163.com  All Right Reserved
10. */
12. #include <stdio.h>
13. #include <stdlib.h>
14. #include <stdbool.h>
15. //指定链表中元素的数据类型，用户可根据需要进行修改
16. typedef int DataType_t;
18. //构造链表的结点，链表中所有结点的数据类型应该是相同的（数据域+指针域）
19. typedef struct DoubleLinkedList
20. {
21.     DataType_t                  data;   //结点的数据域
22.     struct DoubleLinkedList *   prev;   //直接前驱指针域
23.     struct DoubleLinkedList *   next;   //直接后继的指针域
24. }DoubleLnList_t;  
27. /**
28. * @name    :  DoubleLnList_Create
29. * @brief   :  创建一个空链表，空链表应该有一个头节点，对链表进行初始化
30. * @param   :  None
31. * @retval  :  返回头结点的地址
32. * @date    :  2025/6/30
33. * @version :  1.0
34. * @note    :  None
35. */
36. DoubleLnList_t *DoubleLnList_Create(void)
37. {
38.     //创建一个头结点并对头结点申请内存
39.     DoubleLnList_t* Head=(DoubleLnList_t*)calloc(1,sizeof(DoubleLnList_t));
40.     if (NULL==Head){
41.         perror("calloc memory for Head is failed\n");
42.         exit(-1);
43.     }
44.     //对头结点进行初始化,头结点不存储数据域，指针域指向NULL
45.     Head->prev=NULL;
46.     Head->next=NULL;
47.     //将头结点的地址返回
48.     return Head;
49. }
52. /**
53. * @name    :  DoubleLnList_NewNode
54. * @brief   :  创建一个新结点，并为新结点申请堆内存以及对新结点的数据域和指针域进行初始化
55. * @param   :  
56. *             @data:新结点的数据
57. * @retval  :  返回新结点的地址
58. * @date    :  2025/6/30
59. * @version :  1.0
60. * @note    :  None
61. */
62. DoubleLnList_t * DoubleLnList_NewNode(DataType_t data)
63. {
64.     //创建新结点，并未新结点申请堆内存
65.     DoubleLnList_t * New=(DoubleLnList_t*)calloc(1,sizeof(DoubleLnList_t));
66.      if (NULL==New){
67.         perror("calloc memory for NewNode is failed\n");
68.         return NULL;
69.     }
70.     //对新结点的数据域和指针域进行初始化
71.     New->data=data;
72.     New->prev=NULL;
73.     New->next=NULL;
75.     return New;
76. }
79. /**
80. * @name    :  DoubleLnList_FirstInsert
81. * @brief   :  创建一个新结点,并把新结点插入链表的首部
82. * @param   :  
83. *             @Head:插入的链表
84. *             @data:新结点的数据
85. * @retval  :  功返回true，失败返回false
86. * @date    :  2025/6/30
87. * @version :  1.0
88. * @note    :  None
89. */
90. bool DoubleLnList_FirstInsert(DoubleLnList_t * Head,DataType_t data)
91. {
92.     //创建新结点，并对新结点进行初始化
93.     DoubleLnList_t* New=DoubleLnList_NewNode(data);
94.     if (NULL==New){
95.         perror("Create New node is failed\n");
96.         return false;
97.     }
98.     //判断链表是否为空，如果为空，则将新结点直接插入
99.     if (NULL==Head->next){
100.         Head->next=New;
101.         return true;
102.     }
103.     New->next=Head->next;//新结点的next指向原首结点
104.     Head->next->prev=New;//原首结点的prev指向新结点
105.     Head->next=New;//头结点的next指向新结点
107.     return true;
108. }
110. /**
111. * @name    :  DoubleLnList_tailInsert
112. * @brief   :  创建一个新结点,并把新结点插入链表的尾部
113. * @param   :  
114. *             @Head:插入的链表
115. *             @data:新结点的数据
116. * @retval  :  成功返回true，失败返回false
117. * @date    :  2025/6/30
118. * @version :  1.0
119. * @note    :  None
120. */
121. bool DoubleLnList_tailInsert(DoubleLnList_t * Head,DataType_t data)
122. {
123.     //创建新结点，并对新结点进行初始化
124.     DoubleLnList_t* New=DoubleLnList_NewNode(data);
125.     if (NULL==New){
126.         perror("Create New node is failed\n");
127.         return false;
128.     }
129.     //判断链表是否为空，如果为空，则将新结点直接插入
130.     if (NULL==Head->next){
131.         Head->next=New;
132.         return true;
133.     }
134.     //备份首结点的地址
135.     DoubleLnList_t * tail=Head->next;
136.     //找到尾结点
137.     while(tail->next){
138.         tail=tail->next;
139.     }
140.     tail->next=New;//尾结点的next指向新结点
141.     New->prev=tail;//新结点的prev指向尾结点
143.     return true;
144. }
147. /**
148. * @name    :  DoubleLnList_DestInsert
149. * @brief   :  创建一个新结点,并把新结点插入链表的指定位置
150. * @param   :  
151. *             @Head:插入的链表
152. *             @Dest:指定需要新结点插入位置的直接前驱的数据
153. *             @data:新结点的数据
154. * @retval  :  成功返回true，失败返回false
155. * @date    :  2025/6/30
156. * @version :  1.0
157. * @note    :  None
158. */
159. bool DoubleLnList_DestInsert(DoubleLnList_t * Head,DataType_t Dest,DataType_t data)
160. {
161.     //创建新结点，并对新结点进行初始化
162.     DoubleLnList_t* New=DoubleLnList_NewNode(data);
163.     if (NULL==New){
164.         perror("Create New node is failed\n");
165.         return false;
166.     }
167.     //判断链表是否为空，如果为空，则将新结点直接插入
168.     if (NULL==Head->next){
169.         Head->next=New;
170.         return true;
171.     }
172.     //备份首结点的地址
173.     DoubleLnList_t * curr=Head->next;
174.     //如果链表为非空，遍历链表，目的是找到目标结点
175.     while( NULL!=curr && Dest!=curr->data){
176.         curr=curr->next;
177.     }
178.     //未找到目标结点，错误输出
179.     if ( NULL==curr ){
180.         printf("Dest is not found\n");
181.         free(New);
182.         return false;
183.     }
185.     if(curr->next){      
186.         New->next=curr->next;//当前结点并不是尾结点时，新结点的next指向目标节点的next   
187.         curr->next->prev=New;//当前结点并不是尾结点时，目标结点的直接后继的prev指向新结点
188.     }
189.     New->prev=curr;         //新结点的prev指向目标结点
190.     curr->next=New;         //目标结点的next指向新结点
191.         
192.     return true;
193. }
196. /**
197. * @name    :  DoubleLnList_FirstDel
198. * @brief   :  删除链表的首结点
199. * @param   :  
200. *             @Head:链表的头结点
201. * @retval  :  成功返回true，失败返回false
202. * @date    :  2025/6/30
203. * @version :  1.0
204. * @note    :  None
205. */
206. bool DoubleLnList_FirstDel(DoubleLnList_t* Head)
207. {
208.     //备份首结点
209.     DoubleLnList_t * first=Head->next;
210.     //判断传参错误或链表为空
211.     if (NULL==Head || NULL==Head->next){
212.         perror("Linked list is empty\n");
213.         return false;
214.     }
215.     //1.只有一个首结点
216.     if (Head->next->next==NULL){
217.         Head->next=NULL;
218.         first->next=NULL;//首结点的next指向NULL,从链表中断开(避免野指针)
219.         free(first);
220.         return true;
221.     }
222.     //2.链表有多个结点
223.     Head->next->next->prev=NULL;//原首结点的直接后继的prev指向NULL
224.     Head->next=Head->next->next;//头结点的next指向原首结点的直接后继
225.     //旧的首结点的指针域指向NULL,从链表中断开(避免野指针)
226.     first->next=NULL;
227.     //释放首结点占用的内存
228.     free(first);
230.     return true;
231. }
234. /**
235. * @name    :  DoubleLnList_tailDel
236. * @brief   :  删除链表的尾结点
237. * @param   :  
238. *             @Head:链表的头结点
239. * @retval  :  成功返回true，失败返回false
240. * @date    :  2025/6/30
241. * @version :  1.0
242. * @note    :  None
243. */
244. bool DoubleLnList_tailDel(DoubleLnList_t* Head)
245. {
246.     //备份头结点和首结点
247.     DoubleLnList_t * prev=Head;
248.     DoubleLnList_t * tail=Head->next;
249.     //判断传参错误或链表为空
250.     if (NULL==Head || NULL==Head->next){
251.         perror("Linked list is empty\n");
252.         return false;
253.     }
254.     //1.只有一个首结点
255.     if (Head->next->next==NULL){
256.         Head->next=NULL;
257.         tail->next=NULL;//首结点的next指向NULL,从链表中断开(避免野指针)
258.         free(tail);
259.         return true;
260.     }
261.     //2.链表有多个结点
262.     //找到尾结点和它的直接前驱
263.     while(tail->next){
264.         prev=tail;
265.         tail=tail->next;
266.     }
267.     //尾结点的直接前驱的prev指向NULL
268.     prev->next=NULL;
269.     //旧的尾结点的指针域指向NULL,从链表中断开(避免野指针)
270.     tail->prev=NULL;
271.     free(tail);
273.     return true;
274. }
277. /**
278. * @name    :  DoubleLnList_DestDel
279. * @brief   :  删除链表的指定结点
280. * @param   :  
281. *             @Head:链表的头结点
282. *             @Dest:需要删除的指定结点
283. * @retval  :  功返回true，失败返回false
284. * @date    :  2025/6/30
285. * @version :  1.0
286. * @note    :  None
287. */
288. bool DoubleLnList_DestDel(DoubleLnList_t* Head,DataType_t Dest)
289. {
290.     //备份头结点和首结点
291.     DoubleLnList_t * prev=Head;
292.     DoubleLnList_t * curr=Head->next;
293.     //判断传参错误或链表为空
294.     if (NULL==Head || NULL==Head->next){
295.         perror("Linked list is empty\n");
296.         return false;
297.     }
298.     //1.只有一个首结点
299.     if (Head->next->next==NULL){
300.         Head->next=NULL;
301.         curr->next=NULL;//首结点的指针域指向NULL,从链表中断开(避免野指针)
302.         free(curr);
303.         return true;
304.     }
305.     //2.链表有多个结点
306.     //遍历链表，目的是找到目标结点和它的直接前驱
307.     while( NULL!=curr && Dest!=curr->data){
308.         prev=curr;
309.         curr=curr->next;
310.     }
311.     //未找到目标结点，错误输出
312.     if( NULL==curr ){
313.         printf("Dest is not found\n");
314.         return false;
315.     }
316.    
317.     //找到目标结点
318.     prev->next=curr->next;//目标结点的直接前驱的next指向目标结点的直接后继
319.     if(curr->next){
320.         if(curr==Head->next){
321.             curr->next->prev=NULL;//当前结点是首结点时，目标结点的直接后继的prev指向NULL
322.         }else{
323.             curr->next->prev=prev;//当前结点并不是首结点或尾结点时，目标结点的直接后继的prev指向目标结点的直接前驱
324.         }
325.     }
326.     //目标结点的指针域指向NULL,从链表中断开(避免野指针)
327.     curr->prev=NULL;
328.     curr->next=NULL;
329.     free(curr);
330.     return true;
331. }
334. /**
335. * @name    :  DoubleLnList_Print
336. * @brief   :  遍历输出链表中各个结点的数据
337. * @param   :  
338. *             @Head:需要遍历的链表
339. * @retval  :  成功返回true，失败返回false
340. * @date    :  2025/6/30
341. * @version :  1.0
342. * @note    :  None
343. */
344. bool DoubleLnList_Print(DoubleLnList_t* Head)
345. {
346.     //判断传参错误或链表为空
347.     if (NULL==Head || NULL==Head->next){
348.         perror("CurrentDoubleLinkedList is empty\n");
349.         return false;
350.     }
351.     //对链表的头节点的地址进行备份
352.     DoubleLnList_t *curr=Head;
353.     //循环遍历链表
354.     while( curr->next){
355.         curr=curr->next;
356.         printf("Data=%d ",curr->data);
357.     }
359.     return true;
360. }

复制代码

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除