双向链表的定义与基本操作

双向链表操作实现

双向链表

双向链表（Doubly Linked List）是一种链式数据结构，其中的每个节点不仅指向下一个节点，还指向前一个节点。这与单向链表不同，后者每个节点只包含到下一个节点的引用。双向链表因此允许在两个方向上遍历：向前和向后。
每个节点在双向链表中通常包含三部分：

• 指向前一个节点的引用（或指针）。
  
• 存储的数据元素。
  
• 指向下一个节点的引用（或指针）。
  

双向链表的优点包括：

• 可以从任意一个节点出发，既能够向前访问也能够向后访问，增加了灵活性。
  
• 在已知节点位置的情况下，插入和删除操作可以高效地进行，因为只需要改变相应节点的前驱和后继的指针即可。
  

缺点是由于每个节点需要额外存储指向前一个节点的指针，因此相比单向链表会占用更多的内存空间。
代码实现

双向链表的创建、插入、删除、查找等常用操作。

1. #include <stdio.h>        // 标准输入输出库，用于 printf 等函数
2. #include <stdbool.h>        // 布尔类型库，提供 bool、true、false
3. #include <stdlib.h>        // 标准库，提供 malloc/calloc/free 和 exit 等函数
5. //定义链表中数据域的类型为 int
6. typedef int DataType_t;
8. //定义双向链表的结点结构体
9. typedef struct DoubleLinkedList
10. {
11.         DataType_t                       data; //结点的数据域
12.         struct DoubleLinkedList        *prev; //直接前驱的指针域
13.         struct DoubleLinkedList        *next; //直接后继的指针域
15. }DoubleLList_t;
18. //创建头结点：初始化一个空的双向链表
19. DoubleLList_t* DoubleLList_Create(void)
20. {
21.     // 为头结点动态分配内存，并初始化为 0（calloc 会清零）
22.         DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
23.          // 如果内存分配失败，打印错误信息并退出程序
24.     if(Head == NULL){
25.                 perror("Calloc memory for the Head is failed!\n");
26.                 exit(-1);
27.         }
28.         Head->next = NULL;
29.         Head->prev = NULL;
30.         return Head;
31. }
33. //创建一个新结点（仅数据域赋值，指针域初始化为 NULL）
34. DoubleLList_t* DoubleLList_NewNode(DataType_t data)
35. {
36.         //1.创建一个新结点并对新结点申请内存
37.         DoubleLList_t *New = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
38.         if (NULL == New)
39.         {
40.                 perror("Calloc memory for NewNode is Failed");
41.                 return NULL;
42.         }
44.         //2.对新结点的数据域和指针域（2个）进行初始化
45.         New->data = data;
46.         New->prev = NULL;
47.         New->next = NULL;
49.         return New;
50. }
52. // 头插法：在链表头部（第一个有效结点位置）插入新元素
53. bool DbleLList_HeadInsert(DoubleLList_t* Head,DataType_t data)
54. {
55.     // 创建新结点
56.         DoubleLList_t *New = DoubleLList_NewNode(data);
57.           if (New == NULL){
58.       return false;
59.           }
60.     // 若为空，新结点直接作为第一个有效结点
61.         if(Head->next == NULL){
62.                 Head->next = New;
63.         }
64.         else{// 否则，将新结点插入到首结点之前
65.                 New->next = Head->next;
66.                 Head->next->prev = New;
67.                 Head->next = New;
68.         }
69.         return true;// 插入成功
70. }
72. // 尾插法：在链表尾部插入新元素
73. bool DbleLList_TailInsert(DoubleLList_t* Head,DataType_t data)
74. {
75.         DoubleLList_t *New = DoubleLList_NewNode(data);
76.   if (New == NULL) {
77.       return false;
78.   }
79.   //如果只有头结点，New直接成为首结点
80.         if(Head->next == NULL){//如果只有头结点，New直接成为首结点
81.                 Head->next = New;
82.         }
83.         else{// 否则，从首结点开始遍历，寻找最后一个结点
84.                 DoubleLList_t *Find_Tail = Head->next;
85.                 while(Find_Tail->next != NULL){
86.                         Find_Tail = Find_Tail->next;
87.                 }
88.          // 找到尾结点后，将新结点连接在其后
89.                 Find_Tail->next = New;
90.                 New->prev = Find_Tail;               
91.         }
92.         return true;
93. }
95. //指定在链表中某个结点后插入一个新结点
96. bool DbleLList_DestInsert_l(DoubleLList_t* Head,DataType_t dest,DataType_t data)
97. {
98.         DoubleLList_t *New = DoubleLList_NewNode(data);
99.           if (New == NULL) {
100.     return false;
101.           }
102.         if(Head->next == NULL){//如果只有头结点，New直接成为首结点
103.                 Head->next = New;
104.         }
105.         DoubleLList_t *Find_Dest = Head->next;
106.         //遍历链表，找到数据域data等于目标值dest的结点
107.         while(Find_Dest->data != dest){       
108.                 if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，data和dest还不相等，说明dest为无效指定结点位置
109.                
110.                         printf("无效指定结点位置\n");
111.                         return false;
112.                 }
113.                 Find_Dest = Find_Dest->next;
115.         }
116.         if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，数据域data等于dest，新结点New成为尾结点
117.        
118.                 Find_Dest->next = New;
119.                 New->prev = Find_Dest;
120.         }
121.         else{
122.                 New->next = Find_Dest->next;
123.                 Find_Dest->next->prev = New;
124.                 New->prev = Find_Dest;
125.                 Find_Dest->next = New;
126.         }
127.         return true;
128. }
129. //指定在链表中某个结点前插入一个新结点
130. bool DbleLList_DestInsert_f(DoubleLList_t *Head,DataType_t dest,DataType_t data)
131. {
132.         DoubleLList_t *New = DoubleLList_NewNode(data);
133.           if (New == NULL) {
134.     return false;
135.           }
136.         if(Head->next == NULL){//如果只有头结点，New直接成为首结点
137.                 Head->next = New;
138.         }
139.         DoubleLList_t *Find_Dest = Head->next;
140.         //遍历链表，找到数据域data等于目标值dest的结点
141.         while(Find_Dest->data != dest){       
142.                 if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，data和dest还不相等，说明dest为无效指定结点位置
143.                
144.                         printf("无效指定结点位置\n");
145.                         return false;
146.                 }
147.                 Find_Dest = Find_Dest->next;
149.         }
150.         //1.首结点是目标结点
151.         if(Find_Dest == Head->next){
152.                 New->next = Head->next;
153.                 Head->next->prev = New;
154.                 Head->next = New;       
155.         }
156.         else{
157.                 New->prev = Find_Dest->prev;
158.                 Find_Dest->prev->next =New;
159.                 New->next = Find_Dest;
160.                 Find_Dest->prev = New;
161.         }
162.         return true;
163. }
165. //遍历链表并输出所有结点的data值
166. bool DbleLList_Print(DoubleLList_t *Head)
167. {
168.         DoubleLList_t *Phead = Head;
169.         if(Head->next == NULL){
170.                 printf("current DoubleLList is empty!\n");
171.                 return false;
172.         }
173.         printf("链表内容: ");
174.         while(Phead->next){
175.                 Phead = Phead->next;
176.                 printf("%d ",Phead->data);
177.                 if(Phead->next == NULL){       
178.                         break;
179.                 }
180.         }
181.         printf("\n");
182.         return true;
183. }
185. //删除链表头结点
186. bool DbleLList_HeadDel(DoubleLList_t *Head)
187. {
188.         DoubleLList_t *Temp  = Head->next;
189.         //if链表只有一个头结点
190.         if(Head->next == NULL){
191.                 printf("current DoubleLList is empty!\n");
192.                 return false;
193.         }
194.         //if当前链表只有一个首结点
195.         if(Temp->next == NULL){
196.                 Head->next = NULL;
197.                 free(Temp);
198.                 return true;
199.         }
200.         //新的首结点pre指向NULL不指向Head
201.         Temp->next->prev = NULL;
202.         //头结点next指向要删除结点的next
203.         Head->next = Temp->next;
204.        
205.         free(Temp);
206.         return true;
207. }
209. //指定位置删除链表结点
210. bool DbleLList_del_dest(DoubleLList_t* Head,DataType_t dest)
211. {       
212.         if(Head->next == Head){
213.                 printf("current DoubleLList is empty!\n");
214.                 return false;
215.         }
217.         DoubleLList_t *Find_Dest = Head->next;
218.         while(Find_Dest->data != dest){       
219.                 if (Find_Dest->next == NULL){//若遍历到链表最后一个结点
221.                         printf("未找到指定节点\n");
222.                         return false;
223.                 }
224.                 Find_Dest = Find_Dest->next;
225.         }
227.         if (Head->next == Find_Dest){//若目标结点是链表第一个结点
228.                 if(Find_Dest->next = NULL){//若目标结点还是是链表唯一结点
229.                         Head->next = NULL;
230.                 }
231.                 else{
232.                 Find_Dest->next->prev = NULL;
233.                 Head->next = Find_Dest->next;
234.                 }
235.         }
236.         else{//若目标结点是链表最后一个结点
237.                 if(Find_Dest->next == NULL){
238.                         Find_Dest->prev->next = NULL;
239.                 }
240.                 else{//若目标结点有前驱后继
241.                         Find_Dest->prev->next = Find_Dest->next;
242.                         Find_Dest->next->prev = Find_Dest->prev;
243.                 }
244.         }
245.         free(Find_Dest);
246.         return true;
247. }

复制代码

主函数测试

1. int main(int argc, char const *argv[])
2. {
3.     // 创建双向链表
4.     DoubleLList_t *Head = DoubleLList_Create();
5.     printf("1. 创建双向链表完成\n");
6.     DbleLList_Print(Head);
7.    
8.     // 测试头插法
9.     printf("\n2. 测试头插法插入 10, 20, 30\n");
10.     DbleLList_HeadInsert(Head, 10);
11.     DbleLList_HeadInsert(Head, 20);
12.     DbleLList_HeadInsert(Head, 30);
13.     DbleLList_Print(Head); // 预期结果: 30 20 10
14.    
15.     // 测试尾插法
16.     printf("\n3. 测试尾插法插入 40, 50\n");
17.     DbleLList_TailInsert(Head, 40);
18.     DbleLList_TailInsert(Head, 50);
19.     DbleLList_Print(Head); // 预期结果: 30 20 10 40 50
20.    
21.     // 测试指定节点后插入
22.     printf("\n4. 测试在20后插入25\n");
23.     DbleLList_DestInsert_l(Head, 20, 25);
24.     DbleLList_Print(Head); // 预期结果: 30 20 25 10 40 50
25.    
26.     // 测试指定节点前插入
27.     printf("\n5. 测试在40前插入35\n");
28.     DbleLList_DestInsert_f(Head, 40, 35);
29.     DbleLList_Print(Head); // 预期结果: 30 20 25 10 35 40 50
30.    
31.     // 测试删除头节点
32.     printf("\n6. 测试删除头节点\n");
33.     DbleLList_HeadDel(Head);
34.     DbleLList_Print(Head); // 预期结果: 20 25 10 35 40 50
35.    
36.     // 测试删除指定节点
37.     printf("\n7. 测试删除节点10\n");
38.     DbleLList_del_dest(Head, 10);
39.     DbleLList_Print(Head); // 预期结果: 20 25 35 40 50
40.    
41.     // 测试删除尾节点
42.     printf("\n8. 测试删除尾节点(50)\n");
43.     DbleLList_del_dest(Head, 50);
44.     DbleLList_Print(Head); // 预期结果: 20 25 35 40
45.    
46.     // 测试删除中间节点
47.     printf("\n9. 测试删除中间节点(25)\n");
48.     DbleLList_del_dest(Head, 25);
49.     DbleLList_Print(Head); // 预期结果: 20 35 40
50.    
51.     // 测试删除所有节点
52.     printf("\n10. 测试删除所有节点\n");
53.     DbleLList_HeadDel(Head);
54.     DbleLList_HeadDel(Head);
55.     DbleLList_HeadDel(Head);
56.     DbleLList_Print(Head); // 预期结果: 空链表
57.    
58.     // 释放头节点
59.     free(Head);
60.     Head = NULL;
61.     printf("\n11. 释放链表完成\n");
62.    
63.     return 0;
64. }

复制代码

测试结果

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