【数据结构与算法】双向带头循环链表（附源码）

2023-07-26 131

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构与算法】双向带头循环链表（附源码）

一.前言

在前面的博客中，我们学习了顺序表和结构最简单的链表——单链表，但是单链表存在在着一些不足，比如单链表的插入和删除的操作，总是要找到指定节点的前驱或是后继，这样就会比较麻烦。

那么本篇文章所讲述的双向带头循环链表（以后简称双链表），就可以很好解决这个问题。

二.双向带头循环链表的结构

1.该链表有一个哨兵位节点，即头节点；

2.每个节点都包含一个prev 指针和 next 指针，分别指向当前节点的前驱和后继；

3.头节点的 prev 指向的是尾节点，尾节点的next 指向的是头节点，这样就实现了循环。

请看图示：

别看结构这么复杂，但其实它是一个很厉害的结构，代码实现会很简单。

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

这个接口用来创建哨兵位头节点，并使该节点的 prev 和 next 都指向自己以实现循环的目的。

1. LNode* Buynewnode(DLdatatype x)   //定义一个 malloc 新节点的函数，以便后续需要
2. {
3.  LNode* newnode = (LNode*)malloc(sizeof(LNode));
4.  assert(newnode);
5.  newnode->prev = NULL;
6.  newnode->next = NULL;
7.  newnode->data = x;
8.  return newnode;
9. }
10. LNode* ListNodeinit()
11. {
12.   LNode* phead = (LNode*)malloc(sizeof(LNode));
13.   assert(phead);
14.   phead->prev = phead;  //使其都指向自己
15.   phead->next = phead;
16.   phead->data = -1;
17.   return phead;
18. }

2.Listdestroy

我们需要遍历链表，并定义一个next 来保存 cur 的下一个节点，在链表都free 完后，再销毁头节点；

注意：应该是从头节点的 next 开始遍历。

1. void ListNodedestroy(LNode* phead)
2. {
3.  assert(phead);
4. 
5.  LNode* cur = phead->next;
6.  while (cur != phead)
7.  {
8.    LNode* next = cur->next;
9.    free(cur);
10.     cur = next;
11.   }
12. 
13.   free(phead);
14.   phead = NULL;
15. }

B.插入

1.头插 ListNodepushfront

1.这里要头插就太简单了，但是我们最好保存一下头节点的 next ，这样就不应考虑链接时的顺序问题；

2.使头节点的 next 指向新节点，然后新节点的 prev 指向头节点；

3.新节点的 next 指向保存的节点，保存的节点的 prev 指向新节点；

这里并不需要考虑链表为空的情况，这就是双链表的强大之处。

1. void ListNodepushfront(LNode* phead, DLdatatype x)
2. {
3.  assert(phead);
4. 
5.  LNode* newnode = Buynewnode(x);
6. 
7.  LNode* first = phead->next;  //保存头节点的下一个
8. 
9.  phead->next = newnode;
10.   newnode->prev = phead;
11.   newnode->next = first;
12.   first->prev = newnode;
13. }
14.

2.尾插 ListNodepushback

1.尾插就需要找尾；

2.这里的找尾很简单，就是头节点的 prev；

3.将尾节点与新节点链接起来。

1. void ListNodepushback(LNode* phead, DLdatatype x)
2. {
3.  assert(phead);
4. 
5.  LNode* newnode = Buynewnode(x);
6.  LNode* tail = phead->prev;
7.  tail->next = newnode;
8.  newnode->prev = tail;
9.  newnode->next = phead;
10.   phead->prev = newnode;
11. 
12. }

3.插入 ListNodeinsert

1.再插入前需要写一个 find 函数，用来寻找指定的位置 pos；

2.找到 pos 的前驱 prev ；

3.将前驱，pos，新节点链接起来。

1. LNode* ListNodefind(LNode* phead,DLdatatype x)
2. {
3.  assert(phead);
4. 
5.  LNode* cur = phead->next;
6.  while (cur != phead)
7.  {
8.    if (cur->data == x)
9.    {
10.       return cur;
11.     }
12. 
13.     cur = cur->next;
14. 
15.   }
16. 
17.   return NULL;
18. }
19. 
20. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
21. {
22.   assert(phead);
23.   assert(pos);
24. 
25.   LNode* newnode = Buynewnode(x);
26.   LNode* prev = pos->prev;
27. 
28.   prev->next = newnode;
29.   newnode->prev = prev;
30.   newnode->next = pos;
31.   pos->prev = newnode;
32. }

总结：其实可以用一个插入接口就可以实现头插和尾插这两个接口。

C.删除

1.删除时要注意的点是不能把头节点也给删了，如果删了就破坏了双链表的结构；

2.如果是空链表也不能删除。

1.头删 ListNodepopfront

1.删除时保存其下一个节点；

2.链接头节点 phead 和保存的下一个节点；

3.删除 phead 的next。

1. void ListNodepopfront(LNode* phead)
2. {
3.  assert(phead);
4.  assert(ListNodeempty(phead));
5.  if (phead->next == phead)
6.  {
7.    perror("ListNodepopfront");
8.    return;
9.  }
10. 
11.   LNode* first = phead->next;
12.   LNode* second = first->next;
13.   phead->next = second;
14.   second->prev = phead;
15. 
16.   free(first);
17.   first = NULL;
18. 
19. 
20. }

2.尾删 ListNodepopback

1.找尾，即：phead的prev；

2.找尾节点的前驱 prev ，使其next指向phead，phead的prev指向该前驱；

1. void ListNodepopback(LNode* phead)
2. {
3.  assert(phead);
4.  assert(ListNodeempty(phead));
5. 
6.  if (phead->next == phead)
7.  {
8.    perror("ListNodepopback");
9.    exit(-1);
10.   }
11. 
12.   LNode* tail = phead->prev;
13.   LNode* prev = tail->prev;
14. 
15.   prev->next = phead;
16.   phead->prev = prev;
17.   free(tail);
18.   tail = NULL;
19. }

3.删除 ListNodeerase

1.调用 find 函数找到要删除的节点pos；

2.找到 pos 的前驱和后继；

3.链接其前驱，后继；

4.删除pos。

1. void ListNodeerase(LNode* pos, LNode* phead)
2. {
3.  assert(phead);
4.  assert(pos);
5. 
6.  if (phead->next == phead)
7.  {
8.    perror("ListNodeerase");
9.    exit(-1);
10.   }
11.   LNode* prev = pos->prev;
12.   LNode* next = pos->next;
13. 
14.   prev->next = next;
15.   next->prev = prev;
16. 
17.   free(pos);
18.   pos = NULL;
19. }

总结：这里可以复用删除函数去实现头删和尾删。

D.打印 ListNodeprint

注意是从头节点的下一个节点开始遍历，且循环终止条件是看是否等于 phead，因为双链表没有 NULL。

1. void ListNodeprint(LNode* phead)
2. {
3.  assert(phead);
4.  LNode* cur = phead->next;
5.  while (cur != phead)
6.  {
7.    printf("%d <=> ", cur->data);
8.    cur = cur->next;
9.  }
10. 
11.   printf("\n");
12. 
13. 
14. }

四.源码

List.h

1. #pragma once
2. 
3. 
4. #include <stdio.h>
5. #include <stdlib.h>
6. #include <assert.h>
7. #include <stdbool.h>
8. 
9. typedef int DLdatatype;
10. 
11. typedef struct ListNode
12. {
13.   struct ListNode* prev;
14.   struct ListNode* next;
15.   DLdatatype data;
16. }LNode;
17. 
18. LNode* ListNodeinit();
19. 
20. void ListNodeprint(LNode* phead);
21. 
22. void ListNodepushback(LNode*phead,DLdatatype x);
23. 
24. void ListNodepushfront(LNode* phead, DLdatatype x);
25. 
26. void ListNodepopback(LNode* phead);
27. 
28. void ListNodepopfront(LNode* phead);
29. 
30. LNode* ListNodefind(LNode* phead,DLdatatype x);
31. 
32. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x);
33. 
34. void ListNodeerase(LNode* pos, LNode* phead);
35. 
36. void ListNodedestroy(LNode* phead);

List.c

1. #define _CRT_SECURE_NO_WARNINGS
2. 
3. #include "List.h"
4. 
5. LNode* Buynewnode(DLdatatype x)
6. {
7.  LNode* newnode = (LNode*)malloc(sizeof(LNode));
8.  assert(newnode);
9.  newnode->prev = NULL;
10.   newnode->next = NULL;
11.   newnode->data = x;
12.   return newnode;
13. }
14. 
15. LNode* ListNodeinit()
16. {
17.   LNode* phead = (LNode*)malloc(sizeof(LNode));
18.   assert(phead);
19.   phead->prev = phead;
20.   phead->next = phead;
21.   phead->data = -1;
22.   return phead;
23. }
24. 
25. void ListNodeprint(LNode* phead)
26. {
27.   assert(phead);
28.   LNode* cur = phead->next;
29.   while (cur != phead)
30.   {
31.     printf("%d <=> ", cur->data);
32.     cur = cur->next;
33.   }
34. 
35.   printf("\n");
36. 
37. 
38. }
39. 
40. void ListNodepushback(LNode* phead, DLdatatype x)
41. {
42.   assert(phead);
43. 
44.   /*LNode* newnode = Buynewnode(x);
45.   LNode* tail = phead->prev;
46.   tail->next = newnode;
47.   newnode->prev = tail;
48.   newnode->next = phead;
49.   phead->prev = newnode;*/
50. 
51.   ListNodeinsert(phead, phead, x);
52. 
53. 
54. }
55. 
56. void ListNodepushfront(LNode* phead, DLdatatype x)
57. {
58.   assert(phead);
59. 
60.   /*LNode* newnode = Buynewnode(x);
61. 
62.   LNode* first = phead->next;
63. 
64.   phead->next = newnode;
65.   newnode->prev = phead;
66.   newnode->next = first;
67.   first->prev = newnode;*/
68. 
69.   ListNodeinsert(phead->next, phead, x);
70. }
71. 
72. bool ListNodeempty(LNode* phead)
73. {
74.   assert(phead);
75. 
76.   return phead->next == phead;
77. }
78. 
79. void ListNodepopback(LNode* phead)
80. {
81.   assert(phead);
82.   //assert(ListNodeempty(phead));
83. 
84.   if (phead->next == phead)
85.   {
86.     perror("ListNodepopback");
87.     exit(-1);
88.   }
89. 
90.   /*LNode* tail = phead->prev;
91.   LNode* prev = tail->prev;
92. 
93.   prev->next = phead;
94.   phead->prev = prev;
95.   free(tail);
96.   tail = NULL;*/
97. 
98.   ListNodeerase(phead->prev, phead);
99. }
100. 
101. void ListNodepopfront(LNode* phead)
102. {
103.  assert(phead);
104.  //assert(ListNodeempty(phead));
105.  if (phead->next == phead)
106.  {
107.    perror("ListNodepopfront");
108.    return;
109.  }
110. 
111.  /*LNode* first = phead->next;
112.  LNode* second = first->next;
113.  phead->next = second;
114.  second->prev = phead;
115. 
116.  free(first);
117.  first = NULL;*/
118. 
119.  ListNodeerase(phead->next, phead);
120. }
121. 
122. LNode* ListNodefind(LNode* phead,DLdatatype x)
123. {
124.  assert(phead);
125. 
126.  LNode* cur = phead->next;
127.  while (cur != phead)
128.  {
129.    if (cur->data == x)
130.    {
131.      return cur;
132.    }
133. 
134.    cur = cur->next;
135. 
136.  }
137. 
138.  return NULL;
139. }
140. 
141. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
142. {
143.  assert(phead);
144.  assert(pos);
145. 
146.  LNode* newnode = Buynewnode(x);
147.  LNode* prev = pos->prev;
148. 
149.  prev->next = newnode;
150.  newnode->prev = prev;
151.  newnode->next = pos;
152.  pos->prev = newnode;
153. }
154. 
155. void ListNodeerase(LNode* pos, LNode* phead)
156. {
157.  assert(phead);
158.  assert(pos);
159. 
160.  if (phead->next == phead)
161.  {
162.    perror("ListNodeerase");
163.    exit(-1);
164.  }
165.  LNode* prev = pos->prev;
166.  LNode* next = pos->next;
167. 
168.  prev->next = next;
169.  next->prev = prev;
170. 
171.  free(pos);
172.  pos = NULL;
173. }
174. 
175. void ListNodedestroy(LNode* phead)
176. {
177.  assert(phead);
178. 
179.  LNode* cur = phead->next;
180.  while (cur != phead)
181.  {
182.    LNode* next = cur->next;
183.    free(cur);
184.    cur = next;
185.  }
186. 
187.  free(phead);
188.  phead = NULL;
189. 
190. }

test.c

至于test.c 就不贴出来了，这里面主要是一些测试接口的代码，没必要贴出来。

😽本篇文章到此就结束了，若有错误或是建议，欢迎小伙伴们指出；😻

😍请多多支持博主哦~🥰

🤩谢谢你的阅读~😃

【数据结构与算法】双向带头循环链表（附源码）

一.前言

二.双向带头循环链表的结构

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

2.Listdestroy

B.插入

1.头插 ListNodepushfront

2.尾插 ListNodepushback

3.插入 ListNodeinsert

C.删除

1.头删 ListNodepopfront

2.尾删 ListNodepopback

3.删除 ListNodeerase

D.打印 ListNodeprint

四.源码

List.h

List.c

test.c

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【数据结构与算法】双向带头循环链表（附源码）

一.前言

二.双向带头循环链表的结构

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

2.Listdestroy

B.插入

1.头插 ListNodepushfront

2.尾插 ListNodepushback

3.插入 ListNodeinsert

C.删除

1.头删 ListNodepopfront

2.尾删 ListNodepopback

3.删除 ListNodeerase

D.打印 ListNodeprint

四.源码

List.h

List.c

test.c

热门文章

最新文章

相关课程

相关电子书