IT评测·应用市场-qidao123.com

标题: 【初探数据布局】线性表——链表（二）带头双向循环链表（详解与实现） [打印本页]

---

作者: 石小疯    时间: 2025-3-14 16:20
标题: 【初探数据布局】线性表——链表（二）带头双向循环链表（详解与实现）
1. 什么是带头双向循环链表？

带头双向循环链表，顾名思义，包罗以下几个重要特点：

• 双向性：每个节点不仅有指向下一个节点的next指针，还有一个指向前一个节点的prev指针。这使得遍历链表时可以从任意一个节点开始，向前或向后都可以。
  
• 循环性：链表的最后一个节点的next指针指向头节点，而头节点的prev指针指向最后一个节点，形成一个闭环。即链表没有尾节点，头节点和尾节点毗连起来，方便链表的尾插尾删等操作。
  
• 头节点（哨兵节点）：链表通过引入一个特别的头节点（哨兵节点）来简化插入和删除操作。这个头节点自己不存储现实数据，只是作为一个占位符，避免了空链表或单一节点链表的特别情况。（我的上一篇文章解说过，欢迎来学习哦【初探数据布局】链表OJ算法——哨兵位（归并两个有序链表详解））
  

2. 带头双向循环链表的布局

1. typedef int LTDataType;
3. typedef struct ListNode
4. {
5.     LTDataType data;       // 存储节点数据
6.     struct ListNode* next; // 指向下一个节点
7.     struct ListNode* prev; // 指向前一个节点
8. } ListNode;

复制代码

每个ListNode布局体包罗：

• data：保存节点的数据。
  
• next：指向下一个节点。
  
• prev：指向前一个节点。
  

3. 带头双向循环链表的操作

带头双向循环链表支持常见的增删查改操作，以下是常用操作的实现。
3.1 初始化链表

1. ListNode* ListInit()
2. {
3.     ListNode* head = (ListNode*)malloc(sizeof(ListNode));
4.     if (head == NULL) {
5.         perror("malloc fail");
6.         exit(-1);
7.     }
8.     head->next = head;  // 头节点的next指向自己，形成循环
9.     head->prev = head;  // 头节点的prev也指向自己，形成循环
10.     return head;
11. }

复制代码

在初始化时，创建一个头节点，并将其next和prev指针都指向自身，这样链表初始时是空的，而且形成了一个循环布局。
3.2 插入节点

• 尾插操作：在链表尾部插入新节点。
  

1. void ListPushBack(ListNode* pHead, LTDataType x)
2. {
3.     assert(pHead);
4.     ListInsert(pHead, x);
5. }

复制代码

ListInsert用于执行具体的插入操作，它将新节点插入到链表末尾。

• 头插操作：在链表头部插入新节点。
  

1. void ListPushFront(ListNode* pHead, LTDataType x)
2. {
3.     assert(pHead);
4.     ListInsert(pHead->next, x);
5. }

复制代码

3.3 删除节点

• 尾删操作：删除链表尾部的节点。
  

1. void ListPopBack(ListNode* pHead)
2. {
3.     assert(pHead);
4.     ListNode* tail = pHead->prev;
5.     ListErase(tail);
6. }

复制代码

• 头删操作：删除链表头部的节点。
  

1. void ListPopFront(ListNode* pHead)
2. {
3.     assert(pHead);
4.     ListErase(pHead->next);
5. }

复制代码

3.4 查找节点

通过值查找链表中的节点。

1. ListNode* ListFind(ListNode* pHead, LTDataType x)
2. {
3.     assert(pHead);
4.     ListNode* cur = pHead->next;
5.     while (cur != pHead) {
6.         if (cur->data == x)
7.             return cur;
8.         cur = cur->next;
9.     }
10.     return NULL;
11. }

复制代码

3.5 删除指定节点

通过pos指针删除指定位置的节点。

1. void ListErase(ListNode* pos)
2. {
3.     assert(pos);
4.     ListNode* after = pos->next;
5.     ListNode* behind = pos->prev;
6.     behind->next = pos->next;
7.     after->prev = pos->prev;
8.     free(pos);
9.     pos = NULL;
10. }

复制代码

4. 带头双向循环链表的上风

• 简化链表操作：带头节点和双向指针的联合使得在链表的任意位置插入和删除操作更加简便。特别是通过哨兵节点，可以避免单独处理空链表、头节点和尾节点的特别情况。
  
• 双向遍历：通过prev和next指针，我们可以实现从链表任意节点出发，向前或向后遍历。这为一些复杂操作提供了极大的灵活性。
  
• 内存管理：链表在操作时可以动态地分配和开释节点内存，减少内存浪费。
  

5. 完整代码

List.h

1. #pragma once
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<assert.h>
8. // 带头+双向+循环链表增删查改实现
9. typedef int LTDataType;
10. typedef struct ListNode
11. {
12.         LTDataType data;
13.         struct ListNode* next;
14.         struct ListNode* prev;
15. }ListNode;
17. // 创建返回链表的头结点.
18. ListNode* ListInit();
19. // 双向链表销毁
20. void ListDestory(ListNode* pHead);
21. // 双向链表打印
22. void ListPrint(ListNode* pHead);
23. // 双向链表尾插
24. void ListPushBack(ListNode* pHead, LTDataType x);
25. // 双向链表尾删
26. void ListPopBack(ListNode* pHead);
27. // 双向链表头插
28. void ListPushFront(ListNode* pHead, LTDataType x);
29. // 双向链表头删
30. void ListPopFront(ListNode* pHead);
31. // 双向链表查找
32. ListNode* ListFind(ListNode* pHead, LTDataType x);
33. // 双向链表在pos的前面进行插入
34. void ListInsert(ListNode* pos, LTDataType x);
35. // 双向链表删除pos位置的节点
36. void ListErase(ListNode* pos);

复制代码

List.c

1. #define  _CRT_SECURE_NO_WARNINGS 1
3. #include"List.h"
5. ListNode* ListInit()
6. {
7.         //设置哨兵位头结点
8.         ListNode* head = (ListNode*)malloc(sizeof(ListNode));
9.         if (head == NULL) {
10.                 perror("malloc fail");
11.                 exit(-1);
12.         }
13.         head->next = head;
14.         head->prev = head;
15.         return head;
16. }
18. void ListDestory(ListNode* pHead)
19. {
20.         assert(pHead);
21.         ListNode* cur = pHead->next;
22.         while (cur != pHead) {
23.                 ListNode* next = cur->next;
24.                 free(cur);
25.                 cur = next;
26.         }
27.         free(pHead);
28.         pHead = NULL;
29. }
31. void ListPrint(ListNode* pHead)
32. {
33.         assert(pHead);
34.         ListNode* cur = pHead->next;
35.         printf("HEAD=>");
36.         while (cur != pHead) {
37.                 printf("%d<=>",cur->data);
38.                 cur = cur->next;
39.         }
40.         printf("\n");
41. }
43. ListNode* CreateNewNode(LTDataType x)
44. {
45.         ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
46.         if (newnode == NULL) {
47.                 perror("malloc fail");
48.                 exit(-1);
49.         }
50.         newnode->data = x;
51.         newnode->next = NULL;
52.         newnode->prev = NULL;
53.         return newnode;
54. }
56. void ListPushBack(ListNode* pHead, LTDataType x)
57. {
58.         assert(pHead);
59.         ListInsert(pHead, x);
60. }
62. void ListPopBack(ListNode* pHead)
63. {
64.         assert(pHead);
65.         ListNode* tail = pHead->prev;
66.         ListErase(tail);
67. }
69. void ListPushFront(ListNode* pHead, LTDataType x)
70. {
71.         assert(pHead);
72.         ListInsert(pHead->next, x);
73. }
75. void ListPopFront(ListNode* pHead)
76. {
77.         assert(pHead);
78.         ListErase(pHead->next);
79. }
81. ListNode* ListFind(ListNode* pHead, LTDataType x)
82. {
83.         assert(pHead);
84.         ListNode* cur = pHead->next;
85.         while (cur != pHead) {
86.                 if (cur->data == x)
87.                         return cur;
88.                 cur = cur->next;
89.         }
90.         return NULL;
91. }
93. void ListInsert(ListNode* pos, LTDataType x)
94. {
95.         assert(pos);
96.         ListNode* newnode = CreateNewNode(x);
97.         ListNode* cur = pos->prev;
98.         pos->prev = newnode;
99.         newnode->next = pos;
100.         cur->next = newnode;
101.         newnode->prev = cur;
102. }
104. void ListErase(ListNode* pos)
105. {
106.         assert(pos);
107.         ListNode* after = pos->next;
108.         ListNode* behind = pos->prev;
109.         behind->next = pos->next;
110.         after->prev = pos->prev;
111.         free(pos);
112.         pos = NULL;
113. }

复制代码

Test.c

在现实使用时，我们可以通过以下代码进行链表的操作：

1. void test()
2. {
3.     ListNode* plist;
4.     plist = ListInit();  // 初始化链表
6.     // 插入元素
7.     ListPushBack(plist, 1);
8.     ListPushBack(plist, 2);
9.     ListPushBack(plist, 3);
10.     ListPushBack(plist, 4);
11.     ListPrint(plist);  // 打印链表
13.     // 删除元素
14.     ListPopBack(plist);
15.     ListPopBack(plist);
16.     ListPrint(plist);  // 打印链表
18.     // 头部插入
19.     ListPushFront(plist, 0);
20.     ListPrint(plist);  // 打印链表
21.     ListPopFront(plist);
22.     ListPrint(plist);  // 打印链表
24.     // 查找元素并插入
25.     ListNode* pos = ListFind(plist, 2);
26.     ListInsert(pos, 20);
27.     ListPrint(plist);  // 打印链表
28. }

复制代码

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

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4