• 数据结构与算法—双向链表

    目录

    一、链表的分类

    二、双向链表原理

    三、实现带头双向链表 

    1、声明链表结构体 

    2、初始化链表

    3、创建新节点

    4、打印链表

    5、头插&尾插

    头插 

    尾插

    6、头删&尾删

    头删

    尾删

    7、 查找节点

    8、 指定节点前插入

    9、 删除指定节点

    10、销毁链表

    完整版

    Lisy.h 声明

    List.c函数

    text.c测试代码

    一、链表的分类

    实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
    1. 单向或者双向
    2. 带头或者不带头（头又叫哨兵位）
    3. 循环或者非循环
    虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
    1. 无头单向非循环链表 ：结构简单，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ，如 哈希桶、图的邻接表 等等。另外这种结构在 笔试面试 中出现很多。
    2. 带头双向循环链表 ：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多 优势 ，实现反而 简单了 ，后面我们代码实现了就知道了。

    二、双向链表原理

     我们来对比单向链表的结构体，看一下与双向链表的结构体有什么区别：（左单向，右双向）

    1. 我们可以看出双向链表比单向链表多了一个结构体指针prev，它的作用是存储前一个结点的地址。
    2. 双向链表的每个节点既可以找到前一个节点，也可以找到后一个节点，
    3. 此外头节点和尾节点比较特殊，头节点的prev指向尾节点，尾节点的next指向头节点。
    4. 如果链表只有头节点（也叫哨兵位），那么它的prev和next都指向自己。 

    三、实现带头双向链表 

    1、声明链表结构体 

    1. typedef int LTDataType;
    2. typedef struct ListNode
    3. {
    4. 	struct ListNode* next;
    5. 	struct ListNode* prev;
    6. 	LTDataType data;
    7. }LTNode;
    • 首先构建链表结构体，将链表结点的data数据类型设置别名LTDataType，方便后续修改。
    • 定义结构体名称的别名为LTNode。 
    • 指针next指向该节点的下一个节点，
    • 指针prev指向该节点的前一个节点。
    • LTDataType类型的data用于存值。

    2、初始化链表

    1. LTNode* LTInit()
    2. {
    3. 	LTNode* phead = BuyLTNode(-1);
    4. 	phead->prev = phead;
    5. 	phead->next = phead;
    6. 	return phead;
    7. }
    • 函数的目的是创建一个空的双向链表并返回指向链表头部的指针。
    • 通过BuyLTNode( )函数为头节点开辟空间，头节点的data值为-1。（后续讲解）
    • 初始化时，prev和next均指向头节点。
    • 返回值为指针phead。

    创建结构体指针，将初始化函数的返回值赋值给结构体指针，即为初始化完成，代码如下：

    LTNode* plist = LTInit();

      这里也可以用二级指针接收链表地址初始化链表。

    1. void LTInit(LTNode** phead)
    2. {
    3. 	assert(phead);
    4. 	* phead = BuyLTNode(-1);
    5. 	(*phead)->prev = *phead;
    6. 	(*phead)->next = *phead;
    7. 	(*phead)->data = 0;
    8. }

    使用该函数初始化时，使用方法也有变化：

    1. LTNode* plist;
    2. LTInit(&plist);

    3、创建新节点

    1. LTNode* BuyLTNode(LTDataType x)
    2. {
    3. 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    4. 	if (newnode == NULL) {
    5. 		perror("malloc fail");
    6. 		return NULL;
    7. 	}
    8. 	newnode->data = x;
    9. 	newnode->prev = NULL;
    10. 	newnode->next = NULL;
    11. 	return newnode;
    12. }
    •  使用malloc为新节点newnode开辟结构体LTNode大小的空间。
    • 开辟失败perror打印错误信息，函数提前结束。
    • 为新节点的data赋值为参数x的值，prev、next置空。
    • 返回新节点指针。

    4、打印链表

    1. void LTPrint(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	printf("guard<==>");
    5. 	LTNode* cur = phead->next;
    6. 	while (cur != phead) {
    7. 		if(cur!=phead->prev)
    8. 			printf("%d<==>", cur->data);
    9. 		else
    10. 			printf("%d\n", cur->data);
    11. 		cur = cur->next;
    12. 	}
    13. }
    • assert检查链表是否为空，为空则报错。
    • 打印字符串 "guard<==>"，用于表示链表的头节点。
    • 指针cur指向头节点下一个节点，也就是第一个节点。
    • while循环的结束条件为cur指向头节点，双向链表尾部不为空，则循环遍历结束条件为尾结点的next指向头节点时。
    • 当cur不指向最后一个节点，打印节点之间的连接符号<==>。

    5、头插&尾插

    《头插&尾插 和 头删&尾删》我们都可以通过后续的指定位置前插入函数和删除函数实现， 这里进行讲解为了更好得熟悉理解双向链表。

    头插 

    1. void LTPushFront(LTNode* phead, LTDataType x)
    2. {
    3. 	assert(phead);
    4. 	LTNode* newnode = BuyLTNode(x);
    5. 	LTNode* first = phead->next;
    6. //下面两块代码的顺序可以颠倒，因为使用指针first储存了原来链表第一个元素的地址
    7. 	newnode->next = first;
    8. 	first->prev = newnode;
    9.  
    10. 	phead->next = newnode;
    11. 	newnode->prev = phead;
    12. }
    • assert检查链表是否为空，为空则报错。
    • 为新节点newnode开辟空间。
    • 指针first指向链表原第一个节点。
    • 将新节点的next指向原第一个节点，原第一个节点的prev指向新节点。
    • 头节点的next指向新节点，新节点的prev指向头节点。

     当然下面这种形式也对，只是后两个代码块不能调换顺序，具体原因大家可以画图试一下。

    1. void LTPushFront(LTNode* phead, LTDataType x)
    2. {
    3. 	assert(phead);
    4. 	LTNode* newnode = BuyLTNode(x);
    5.  
    6. 	newnode->next = phead->next;
    7. 	phead->next->prev = newnode;
    8.  
    9. 	newnode->prev = phead;
    10. 	phead->next = newnode;
    11. }

    尾插

    1. void LTPushBack(LTNode* phead, LTDataType x)
    2. {
    3. 	assert(phead);
    4. 	LTNode* newnode = BuyLTNode(x);
    5. 	LTNode* tail = phead->prev;
    6. 	
    7. 	newnode->next = phead;
    8. 	phead->prev = newnode;
    9.  
    10. 	tail->next = newnode;
    11. 	newnode->prev = tail;
    12. }
    • assert检查链表是否为空，为空则报错。
    • 为新节点newnode开辟空间。
    • 指针tail指向尾节点，直接通过头节点phead的prev即可找到尾节点。
    • 新节点的next指向头节点，头节点的prev指向新节点。
    • 原尾节点的next指向新节点，新节点的prev指向尾节点。

    6、头删&尾删

    头删

    1. bool LTEmpty(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	return phead->next == phead;
    5. }
    6.  
    7. void LTPopFront(LTNode* phead)
    8. {
    9. 	assert(phead);
    10. 	assert(!LTEmpty(phead));
    11.  
    12. 	LTNode* first = phead->next;
    13. 	LTNode* second = first->next;
    14.  
    15. 	second->prev = phead;
    16. 	phead->next = second;
    17. 	free(first);
    18. }
    • 借助LTEmpty函数判断链表是否只有头节点，只有头节点则不进行删除。
    • 第一个assert检查链表是否为空，为空则报错。
    • 第二个assert通过LTEmpty函数返回值判断是否可以进行删除。
    • 定义两个指针first和second分别指向第一个节点和第二个节点。
    • 将第二个节点的prev指向头节点。
    • 头节点的next指向第二个节点。
    • 释放第一个节点的空间。

    尾删

    1. void LTPopBack(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	assert(!LTEmpty(phead));
    5.  
    6. 	LTNode* tail = phead->prev;
    7. 	LTNode* tailPrev = tail->prev;
    8.  
    9. 	free(tail);
    10. 	tailPrev->next = phead;
    11. 	phead->prev = tailPrev;
    12.  
    13. }
    • 第一个assert检查链表是否为空，为空则报错。
    • 第二个assert通过LTEmpty函数返回值判断是否可以进行删除。
    • 定义两个指针tail和tailPrev，分别指向尾节点和尾节点的前一个节点。
    • 释放尾节点的空间。
    • tailPrev的next指向头节点。
    • 头节点的prev指向tailPrev（新的尾节点）。

    7、 查找节点

    1. LTNode* LTFind(LTNode* phead, LTDataType x)
    2. {
    3. 	assert(phead);
    4. 	LTNode* cur = phead->next;
    5. 	while (cur != phead) {
    6. 		if (cur->data == x)
    7. 			return cur;
    8.  
    9. 		cur = cur->next;
    10. 	}
    11. 	return NULL;
    12. }
    • assert检查链表是否为空，为空则报错。
    • 指针cur指向第一个节点。
    • 循环遍历链表，节点的data值为x时，返回该节点的地址。
    • 找不到则返回NULL。

    8、指定节点前插入

    1. void LTInsert(LTNode* pos, LTDataType x)
    2. {
    3. 	assert(pos);
    4.  
    5. 	LTNode* prev = pos->prev;
    6. 	LTNode* newnode = BuyLTNode(x);
    7.  
    8. 	prev->next = newnode;
    9. 	newnode->prev = prev;
    10.  
    11. 	newnode->next = pos;
    12. 	pos->prev = newnode;
    13. }
    • assert检查节点是否为空，为空则报错。
    • 指针prev指向pos节点的前一个节点。
    • 为新节点newnode开辟空间，节点的data值为x。
    • 将prev的next指向新节点，新节点的prev指向prev。
    • 新节点的next指向pos，pos的prev指向新节点。

    9、删除指定节点

    1. void LTErase(LTNode* pos)//可以判断phead是否等于哨兵位
    2. {
    3. 	assert(pos);
    4. 	LTNode* posPrev = pos->prev;
    5. 	LTNode* posNext = pos->next;
    6. 	
    7. 	posPrev->next = posNext;
    8. 	posNext->prev = posPrev;
    9. 	free(pos);
    10. }
    • assert检查节点是否为空，为空则报错。
    • 定义两个指针posPrev和posNext分别指向 pos的前一个节点和 pos后一个节点。
    • 前一个节点posPrev的next指向posNext。
    • 后一个节点posNext的prev指向posPrev
    • 释放pos节点的空间。

    10、销毁链表

    1. void LTDestroy(LTNode** phead)
    2. {
    3. 	assert(phead);
    4. 	assert(*phead);
    5. 	LTNode* cur = (*phead)->next;
    6. 	while (cur != *phead) {
    7. 		LTNode* next = cur->next;
    8. 		free(cur);
    9. 		cur = next;
    10. 	}
    11. 	free(*phead);
    12. 	*phead = NULL;
    13. }
    • assert检查链表是否为空，为空则报错。
    • 检查链表头指针 *phead 是否为非空，为空则报错。
    • 指针cur指向第一个节点，循环内通过cur遍历每个节点。
    • next指针记录cur下一个节点，将cur的空间释放，cur更新为next，指向下一个节点。

    • 在循环结束后，链表中的所有节点都已经被销毁，最后一步是释放链表头指针 *phead 所占用的内存。

    • *phead = NULL 最后，将链表头指针设置为 NULL，以确保不再引用链表，避免悬挂指针或野指针的问题。

    完整版

    完整版代码我保留了注释，方便读者学习，以下代码的功能经测试没有问题，放心使用。 

    Lisy.h 声明

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. typedef int LTDataType;
    7. typedef struct ListNode
    8. {
    9. 	struct ListNode* next;
    10. 	struct ListNode* prev;
    11. 	LTDataType data;
    12. }LTNode;
    13.  
    14. //初始化链表
    15. LTNode* LTInit();
    16. //void LTInit(LTNode** phead);
    17.  
    18. //打印链表
    19. void LTPrint(LTNode* phead);
    20.  
    21. //头插&尾插
    22. void LTPushFront(LTNode* phead, LTDataType x);
    23. void LTPushBack(LTNode* phead, LTDataType x);
    24.  
    25. //头删&尾删
    26. void LTPopFront(LTNode* phead);
    27. void LTPopBack(LTNode* phead);
    28.  
    29. //查找值为x的节点，返回节点地址
    30. LTNode* LTFind(LTNode* phead, LTDataType x);
    31.  
    32. //在指定节点前插入
    33. void LTInsert(LTNode* pos, LTDataType x); 
    34.  
    35. //删除指定节点
    36. void LTErase(LTNode* pos);
    37.  
    38. //销毁链表
    39. void LTDestroy(LTNode** phead);

    List.c函数

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "List.h"
    3.  
    4. //创建新节点
    5. LTNode* BuyLTNode(LTDataType x)
    6. {
    7. 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    8. 	if (newnode == NULL) {
    9. 		perror("malloc fail");
    10. 		return NULL;
    11. 	}
    12. 	newnode->data = x;
    13. 	newnode->prev = NULL;
    14. 	newnode->next = NULL;
    15. 	return newnode;
    16. }
    17.  
    18. //初始化链表
    19. LTNode* LTInit()
    20. {
    21. 	LTNode* phead = BuyLTNode(-1);
    22. 	phead->prev = phead;
    23. 	phead->next = phead;
    24. 	return phead;
    25. }
    26. //void LTInit(LTNode** phead)
    27. //{
    28. //	assert(phead);
    29. //	* phead = BuyLTNode(-1);
    30. //	(*phead)->prev = *phead;
    31. //	(*phead)->next = *phead;
    32. //	(*phead)->data = 0;
    33. //}
    34.  
    35. //打印链表
    36. void LTPrint(LTNode* phead)
    37. {
    38. 	assert(phead);
    39. 	printf("guard<==>");
    40. 	LTNode* cur = phead->next;
    41. 	while (cur != phead) {
    42. 		if(cur!=phead->prev)
    43. 			printf("%d<==>", cur->data);
    44. 		else
    45. 			printf("%d\n", cur->data);
    46. 		cur = cur->next;
    47. 	}
    48. }
    49.  
    50. //头插
    51. void LTPushFront(LTNode* phead, LTDataType x)
    52. {
    53. 	LTInsert(phead->next, x);
    54. }
    55.  
    56. //void LTPushFront(LTNode* phead, LTDataType x)
    57. //{
    58. //	assert(phead);
    59. //	LTNode* newnode = BuyLTNode(x);
    60. //	LTNode* first = phead->next;
    61. //	//下面两块代码的顺序可以颠倒，因为使用指针first储存了原来链表第一个元素的地址
    62. //	newnode->next = first;
    63. //	first->prev = newnode;
    64. //
    65. //	phead->next = newnode;
    66. //	newnode->prev = phead;
    67. //}
    68.  
    69. //void LTPushFront(LTNode* phead, LTDataType x)
    70. //{
    71. //	assert(phead);
    72. //	LTNode* newnode = BuyLTNode(x);
    73. //
    74. //	newnode->next = phead->next;
    75. //	phead->next->prev = newnode;
    76. //
    77. //	newnode->prev = phead;
    78. //	phead->next = newnode;
    79. //}
    80.  
    81. //尾插
    82. void LTPushBack(LTNode* phead, LTDataType x)
    83. {
    84. 	assert(phead);
    85.  
    86. 	LTInsert(phead, x);
    87. }
    88. //void LTPushBack(LTNode* phead, LTDataType x)
    89. //{
    90. //	assert(phead);
    91. //	LTNode* newnode = BuyLTNode(x);
    92. //	LTNode* tail = phead->prev;
    93. //	
    94. //	newnode->next = phead;
    95. //	phead->prev = newnode;
    96. //
    97. //	tail->next = newnode;
    98. //	newnode->prev = tail;
    99. //}
    100.  
    101. //监测链表是否为空
    102. bool LTEmpty(LTNode* phead)
    103. {
    104. 	assert(phead);
    105. 	return phead->next == phead;
    106. }
    107.  
    108. //头删
    109. void LTPopFront(LTNode* phead)
    110. {
    111. 	assert(phead);
    112. 	assert(!LTEmpty(phead));
    113.  
    114. 	LTErase(phead->next);
    115. }
    116.  
    117. //void LTPopFront(LTNode* phead)
    118. //{
    119. //	assert(phead);
    120. //	assert(!LTEmpty(phead));
    121. //
    122. //	LTNode* first = phead->next;
    123. //	LTNode* second = first->next;
    124. //
    125. //	second->prev = phead;
    126. //	phead->next = second;
    127. //	free(first);
    128. //}
    129.  
    130.  
    131. //尾删
    132. void LTPopBack(LTNode* phead)
    133. {
    134. 	assert(phead);
    135. 	assert(!LTEmpty(phead));
    136.  
    137. 	LTErase(phead->prev);
    138. }
    139.  
    140. //void LTPopBack(LTNode* phead)
    141. //{
    142. //	assert(phead);
    143. //	assert(!LTEmpty(phead));
    144. //	//LTErase(phead->prev);
    145. //
    146. //	LTNode* tail = phead->prev;
    147. //	LTNode* tailPrev = tail->prev;
    148. //
    149. //	free(tail);
    150. //	tailPrev->next = phead;
    151. //	phead->prev = tailPrev;
    152. //
    153. //}
    154.  
    155.  
    156.  
    157.  
    158. //查找值为x的节点，返回节点地址
    159. LTNode* LTFind(LTNode* phead, LTDataType x)
    160. {
    161. 	assert(phead);
    162. 	LTNode* cur = phead->next;
    163. 	while (cur != phead) {
    164. 		if (cur->data == x)
    165. 			return cur;
    166.  
    167. 		cur = cur->next;
    168. 	}
    169. 	return NULL;
    170. }
    171.  
    172. //在指定节点前插入，与LTFind搭配使用
    173. void LTInsert(LTNode* pos, LTDataType x)
    174. {
    175. 	assert(pos);
    176.  
    177. 	LTNode* prev = pos->prev;
    178. 	LTNode* newnode = BuyLTNode(x);
    179.  
    180. 	prev->next = newnode;
    181. 	newnode->prev = prev;
    182.  
    183. 	newnode->next = pos;
    184. 	pos->prev = newnode;
    185. }
    186.  
    187. // 删除指定节点
    188. void LTErase(LTNode* pos)//可以判断phead是否等于哨兵位
    189. {
    190. 	assert(pos);
    191. 	LTNode* posPrev = pos->prev;
    192. 	LTNode* posNext = pos->next;
    193. 	
    194. 	posPrev->next = posNext;
    195. 	posNext->prev = posPrev;
    196. 	free(pos);
    197. }
    198.  
    199. //销毁链表
    200. void LTDestroy(LTNode** phead)
    201. {
    202. 	assert(phead);
    203. 	assert(*phead);
    204. 	LTNode* cur = (*phead)->next;
    205. 	while (cur != *phead) {
    206. 		LTNode* next = cur->next;
    207. 		free(cur);
    208. 		cur = next;
    209. 	}
    210. 	free(*phead);
    211. 	*phead = NULL;
    212. }

    text.c测试代码

    1. #include "List.h"
    2.  
    3. void test1() {
    4. 	/*LTNode* plist;
    5. 	LTInit(&plist);*/
    6.  
    7. 	LTNode* plist = LTInit();
    8. 	LTPushFront(plist, 1);
    9. 	LTPushFront(plist, 2);
    10. 	LTPushFront(plist, 3);
    11. 	LTPushFront(plist, 4);
    12. 	LTPushBack(plist, 888);
    13. 	LTPushBack(plist, 888);
    14. 	LTPopFront(plist);
    15. 	LTPopBack(plist);
    16. 	LTNode* pos = LTFind(plist, 888);
    17. 	LTInsert(pos, 999);
    18.  
    19. 	LTErase(pos);
    20.  
    21. 	LTPrint(plist);
    22. 	LTDestroy(&plist);
    23. }
    24.  
    25. int main()
    26. {
    27. 	test1();
    28. 	return 0;
    29. }

  • 相关阅读:
    【学习笔记】go协程和通道
    【算法】蓝桥杯全攻略：从语言基础到数学算法，一站式解锁竞赛技巧
    【Linux成长史】Linux权限的详细讲解
    最新版ESP32 IDF环境搭建教程：基于CLION同时安装多个版本的IDF
    【pycharm】控制台报错：终端无法加载文件\venv\Scripts\activate.ps1
    mysql数据库增量备份方案、备份计划（InsCode AI 创作助手）
    腾讯云 Web 超级播放器开发实战
    测试的流程已经测完，仍然会导致一些 BUG 流入到线上，如何规避和解决？
    基于Streamlit的YOLOv5ToX模型转换工具（适用YOLOv5训练出来的模型转化为任何格式）
    自动对话系统
  • 原文地址：https://blog.csdn.net/m0_73800602/article/details/133937579