• 手撕双链表

    > 作者简介：დ旧言~，目前大一，现在学习Java，c，c++，Python等
    > 座右铭：松树千年终是朽，槿花一日自为荣。
    > 望小伙伴们点赞👍收藏✨加关注哟💕💕 

     🌟前言       

            前面我们已经学习了顺序表和单链表，顺序表可以存储动态的数据，但是一旦元素过少，而又要开辟空间，这样就造成空间的浪费，而单链表以节点为单位存储，不支持随机访问，只能从头到尾遍历访问，为了解决上面两个问题，人们发现了双链表，把一个一个元素以链子的形式存储，可以存储相互的地址，那双链表如何实现呢，今天咱们就实现一下--《双链表》。

    🌙主体

    咱们从三个方面实现双链表，动态管理，头插头删尾插尾删，增删查改。

    在程序中为了实现双链表，需要创建头文件List.h ，创建源文件Test.c，List.c。

     🌠动态管理

    💤初始化动态双链表

    既然实现双链表，初始化动态的双链表必不可少，从两个方面实现初始化动态的双链表。

    1.首先我们在List.h定义动态的双链表，省得我们再定义节点（双链表）。

    1. //定义数据类型
    2. typedef int LTDataType;
    3. //定义双链表初始化
    4. typedef struct ListNode
    5. {
    6. 	//上一个
    7. 	struct ListNode* next;
    8. 	//下一个
    9. 	struct ListNode* prev;
    10. 	LTDataType data;
    11. }LTNode;

    2.对双链表进行初始化

    我们要明白，这里不像单链表一样，形成节点就行，还需要初始化。

    💦这里采用malloc开辟空间

    💦采用预指令判断空间是否开辟完成（没有开辟空间返回-1）

    💦之后就是简单的初始数据

    💦记得返回值

    1. //初始化
    2. LTNode* BuyLTNode(LTDataType x)
    3. {
    4. 	//开辟空间
    5. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    6. 	//判断开辟的空间是否为空
    7. 	if (node == NULL)
    8. 	{
    9. 		perror("malloc fail");
    10. 		exit(-1);
    11. 	}
    12. 	//初始化
    13. 	node->data = x;
    14. 	node->next = NULL;
    15. 	node->prev = NULL;
    16. 	return node;
    17. }
    18.  
    19. //形成双链表
    20. LTNode* LTInit()
    21. {
    22. 	//使头为0
    23. 	LTNode* phead = BuyLTNode(0);
    24. 	//构成循环
    25. 	phead->next = phead;
    26. 	phead->prev = phead;
    27.  
    28. 	return phead;
    29. }

     💤释放双链表内存 

    双链表的内存释放与单链表的内存释放有一定的区别，这里我们分开两类，清理与销毁

    清理的代码如下：

    1. //清理
    2. void ListClear(LTNode* phead)
    3. {
    4. 	//断言
    5. 	assert(phead);
    6. 	
    7. 	//清理全部数据，保留头结点
    8. 	LTNode* cur = phead->next;
    9. 	
    10. 	//循环销毁
    11. 	while (cur != phead)
    12. 	{
    13. 		LTNode* next = cur->next;
    14. 		free(cur);
    15. 		cur = NULL;
    16. 		cur = next;
    17. 	}
    18. }

    销毁的代码如下：

    1. //销毁
    2. void ListDestory(LTNode** pphead)
    3. {
    4. 	//断言
    5. 	assert(*pphead);
    6.  
    7. 	//调用清理（函数）
    8. 	ListClear(*pphead);
    9. 	
    10. 	//释放内存
    11. 	free(*pphead);
    12. 	*pphead = NULL;
    13. }

    🌠头插头删尾插尾删

    💤打印元素

     打印元素就太简单了，直接上代码

    1. //打印数据
    2. void LTPrint(LTNode* phead)
    3. {
    4. 	//断言
    5. 	assert(phead);
    6.  
    7. 	printf("phead<=>");
    8. 	
    9. 	LTNode* cur = phead->next;
    10. 	//注意循环的结束的语句
    11. 	while (cur != phead)
    12. 	{
    13. 		printf("%d<=>", cur->data);
    14. 		cur = cur->next;
    15. 	}
    16. 	
    17. 	printf("\n");
    18. }

    💤尾插（重点）

    有了这个图就对指向的改变就轻轻松松

    1. //尾插（重点）
    2. void LTPushBack(LTNode* phead, LTDataType x)
    3. {
    4. 	//断言
    5. 	assert(phead);
    6.  
    7. 	LTNode* tail = phead->prev;
    8. 	
    9. 	//给添加的元素创建节点
    10. 	LTNode* newnode = BuyLTNode(x);
    11.  
    12.     //新开辟的元素下一个节点指向尾
    13. 	newnode->prev = tail;
    14. 	//尾的上一个节点指向新的元素
    15.     tail->next = newnode;
    16.  
    17.     //新元素的上一个节点指向头
    18. 	newnode->next = phead;
    19.     //头的下一节点指向新的元素节点
    20. 	phead->prev = newnode;
    21.  
    22. 	//本质上与尾插相似 （双向链表在pos的前面进行插入）
    23. 	//LTInsert(phead, x);
    24. }

    💤尾删（重点）

    双链表重在画图，希望小伙伴们能看得懂。

    1. //尾删
    2. void LTPopBack(LTNode* phead)
    3. {
    4. 	//断言
    5. 	assert(phead);
    6. 	//防止没有头指向没有元素
    7. 	assert(phead->next != phead);
    8.  
    9. 	//找到尾
    10. 	LTNode* tail = phead->prev;
    11. 	//找到尾前面一个元素
    12. 	LTNode* tailPrev = tail->prev;
    13. 	
    14. 	//释放内存
    15. 	free(tail);
    16.  
    17. 	//（把尾的上一个元素）的上一个指针 指向头
    18. 	tailPrev->next = phead;
    19. 	//头的下一个指针指向尾的前一个元素
    20. 	phead->prev = tailPrev;
    21.  
    22. 	// 双向链表删除pos位置的结点(本质上与尾删相似)
    23. 	//LTErase(phead->prev);
    24. }

     💤头插（重点）

    博主在这里采用三种方法，希望大家至少学会一种

    1. //头插
    2. void LTPushFront(LTNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5.  
    6. 	//方法一
    7. 	//初始化
    8. 	//LTNode* newnode = BuyLTNode(x);
    9. 	//newnode->next = phead->next;
    10. 	//phead->next->prev = newnode;
    11. 	//phead->next = newnode;
    12. 	//newnode->prev = phead;
    13.  
    14. 	//方法二
    15. 	//初始化
    16. 	LTNode* newnode = BuyLTNode(x);
    17. 	LTNode* first = phead->next;
    18. 	phead->next = newnode;
    19. 	newnode->prev = phead;
    20. 	newnode->next = first;
    21. 	first->prev = newnode;
    22.  
    23. 	//方法三
    24. 	// 双向链表删除pos位置的结点(本质上就是头插)
    25. 	//LTInsert(phead->next, x);
    26. }

     💤头删（重点）

    双链表会自带梢兵位（这个到后期博主会讲）

    1. //头删（重点）
    2. void LTPopFront(LTNode* phead)
    3. {
    4. 	//断言
    5. 	assert(phead);
    6. 	//头指向不能为空
    7. 	assert(phead->next != phead);
    8.  
    9. 	//找到梢兵位的节点
    10. 	LTNode* first = phead->next;
    11. 	//找到头后面一个元素
    12. 	LTNode* second = first->next;
    13.  
    14. 	//释放内存
    15. 	free(first);
    16.  
    17. 	//梢兵位的节点指向头后面一个元素
    18. 	phead->next = second;
    19. 	//后面一个元素指向梢兵位的节点
    20. 	second->prev = phead;
    21.  
    22. 	//双向链表删除pos位置的结点(本质上和头删一样)
    23. 	//LTErase(phead->next);
    24. }

      🌠增删查改

     💤统计双链表元素个数

    这个函数还是比较简单的，注意循环的停止条件。

    1. //统计双链表元素个数
    2. int LTSize(LTNode* phead)
    3. {
    4. 	//断言
    5. 	assert(phead);
    6.  
    7. 	int size = 0;
    8. 	LTNode* cur = phead->next;
    9. 	while (cur != phead)
    10. 	{
    11. 		++size;
    12. 		cur = cur->next;
    13. 	}
    14.  
    15. 	return size;
    16. }

     💤双向链表在pos的前面进行插入

    这里大家就看图理解就行啦

    1. // 双向链表在pos的前面进行插入
    2. void LTInsert(LTNode* pos, LTDataType x)
    3. {
    4. 	//断言
    5. 	assert(pos);
    6.  
    7. 	LTNode* posPrev = pos->prev;
    8. 	//为插入的元素开辟空间
    9. 	LTNode* newnode = BuyLTNode(x);
    10.  
    11. 	posPrev->next = newnode;
    12. 	newnode->prev = posPrev;
    13. 	newnode->next = pos;
    14. 	pos->prev = newnode;
    15. }

     💤双向链表删除pos位置的结点

    这里大家就看图理解就行啦

    1. // 双向链表删除pos位置的结点
    2. void LTErase(LTNode* pos)
    3. {
    4. 	//断言
    5. 	assert(pos);
    6. 	LTNode* posPrev = pos->prev;
    7. 	LTNode* posNext = pos->next;
    8.  
    9. 	//释放内存
    10. 	free(pos);
    11.  
    12. 	posPrev->next = posNext;
    13. 	posNext->prev = posPrev;
    14. }

    🌙代码总结

    🌠主函数

    1. //包含文件
    2. #include"List.h"
    3.  
    4. void TestList1()
    5. {
    6. 	LTNode* plist = LTInit();
    7. 	LTPushBack(plist, 1);
    8. 	LTPushBack(plist, 2);
    9. 	LTPushBack(plist, 3);
    10. 	LTPushBack(plist, 4);
    11. 	LTPushBack(plist, 5);
    12. 	LTPrint(plist);
    13.  
    14. 	LTPushFront(plist, 10);
    15. 	LTPushBack(plist, 10);
    16.  
    17. 	LTPrint(plist);
    18. }
    19.  
    20. void TestList2()
    21. {
    22. 	LTNode* plist = LTInit();
    23. 	LTPushBack(plist, 1);
    24. 	LTPushBack(plist, 2);
    25. 	LTPushBack(plist, 3);
    26. 	LTPushBack(plist, 4);
    27. 	LTPushBack(plist, 5);
    28. 	LTPrint(plist);
    29.  
    30. 	LTPopBack(plist);
    31. 	//LTPopFront(plist);
    32. 	LTPrint(plist);
    33.  
    34. 	//LTPopFront(plist);
    35. 	//LTPopFront(plist);
    36. 	//LTPopFront(plist);
    37. 	//LTPopFront(plist);
    38. 	LTPrint(plist);
    39. }
    40.  
    41. //void TestList3()
    42. //{
    43. //	LTNode* plist = LTInit();
    44. //	LTPushBack(plist, 1);
    45. //	LTPushBack(plist, 2);
    46. //	LTPushBack(plist, 3);
    47. //	LTPushBack(plist, 4);
    48. //	LTPushBack(plist, 5);
    49. //	LTPrint(plist);
    50. //
    51. //	LTPushFront(plist, 10);
    52. //	LTPushFront(plist, 20);
    53. //	LTPushFront(plist, 30);
    54. //	LTPushFront(plist, 40);
    55. //	LTPrint(plist);
    56. //}
    57. //
    58. //void TestList4()
    59. //{
    60. //	LTNode* plist = LTInit();
    61. //	LTPushBack(plist, 1);
    62. //	LTPushBack(plist, 2);
    63. //	LTPushBack(plist, 3);
    64. //	LTPushBack(plist, 4);
    65. //	LTPushBack(plist, 5);
    66. //	LTPrint(plist);
    67. //
    68. //	LTPopFront(plist);
    69. //	LTPrint(plist);
    70. //
    71. //	LTPopBack(plist);
    72. //	LTPrint(plist);
    73. //}
    74.  
    75. int main()
    76. {
    77. 	TestList1();
    78.  
    79. 	return 0;
    80. }

    🌠List.h头文件

    1. //包含头文件
    2. #include
    3. #include
    4. #include
    5.  
    6. //定义数据类型
    7. typedef int LTDataType;
    8. //定义双链表初始化
    9. typedef struct ListNode
    10. {
    11. 	//上一个
    12. 	struct ListNode* next;
    13. 	//下一个
    14. 	struct ListNode* prev;
    15. 	LTDataType data;
    16. }LTNode;
    17.  
    18. //初始化
    19. LTNode* BuyLTNode(LTDataType x);
    20.  
    21. //形成双链表
    22. LTNode* LTInit();
    23.  
    24. //打印数据
    25. void LTPrint(LTNode* phead);
    26.  
    27. //尾插（重点）
    28. void LTPushBack(LTNode* phead, LTDataType x);
    29. //尾删（重点）
    30. void LTPopBack(LTNode* phead);
    31. //头插（重点）
    32. void LTPushFront(LTNode* phead, LTDataType x);
    33. //头删（重点）
    34. void LTPopFront(LTNode* phead);
    35.  
    36. //统计双链表元素个数
    37. int LTSize(LTNode* phead);
    38. // 双向链表查找（在双链表中不合适）
    39. LTNode* LTFind(LTNode* phead, LTDataType x);
    40.  
    41. // 双向链表在pos的前面进行插入
    42. void LTInsert(LTNode* pos, LTDataType x);
    43. // 双向链表删除pos位置的结点
    44. void LTErase(LTNode* pos);
    45.  
    46. //清理
    47. void ListClear(LTNode* phead);
    48. //销毁
    49. void ListDestory(LTNode** pphead);

    🌠List.c源文件

    1.  
    2.  
    3. //包含文件
    4. #include"List.h"
    5.  
    6. //初始化
    7. LTNode* BuyLTNode(LTDataType x)
    8. {
    9. 	//开辟空间
    10. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    11. 	//判断开辟的空间是否为空
    12. 	if (node == NULL)
    13. 	{
    14. 		perror("malloc fail");
    15. 		exit(-1);
    16. 	}
    17. 	//初始化
    18. 	node->data = x;
    19. 	node->next = NULL;
    20. 	node->prev = NULL;
    21. 	return node;
    22. }
    23.  
    24. //形成双链表
    25. LTNode* LTInit()
    26. {
    27. 	//使头为0
    28. 	LTNode* phead = BuyLTNode(0);
    29. 	//构成循环
    30. 	phead->next = phead;
    31. 	phead->prev = phead;
    32.  
    33. 	return phead;
    34. }
    35.  
    36. //打印数据
    37. void LTPrint(LTNode* phead)
    38. {
    39. 	//断言
    40. 	assert(phead);
    41.  
    42. 	printf("phead<=>");
    43. 	
    44. 	LTNode* cur = phead->next;
    45. 	//注意循环的结束的语句
    46. 	while (cur != phead)
    47. 	{
    48. 		printf("%d<=>", cur->data);
    49. 		cur = cur->next;
    50. 	}
    51. 	
    52. 	printf("\n");
    53. }
    54.  
    55. //尾插（重点）
    56. void LTPushBack(LTNode* phead, LTDataType x)
    57. {
    58. 	//断言
    59. 	assert(phead);
    60.  
    61. 	LTNode* tail = phead->prev;
    62.  
    63. 	//给添加的元素创建节点
    64. 	LTNode* newnode = BuyLTNode(x);
    65.  
    66. 	//新开辟的元素下一个节点指向尾
    67. 	newnode->prev = tail;
    68. 	//尾的上一个节点指向新的元素
    69. 	tail->next = newnode;
    70.  
    71. 	//新元素的上一个节点指向头
    72. 	newnode->next = phead;
    73. 	//头的下一节点指向新的元素节点
    74. 	phead->prev = newnode;
    75.  
    76. 	//本质上与尾插相似 （双向链表在pos的前面进行插入）
    77. 	//LTInsert(phead, x);
    78. }
    79.  
    80. //尾删
    81. void LTPopBack(LTNode* phead)
    82. {
    83. 	//断言
    84. 	assert(phead);
    85. 	//防止没有头指向没有元素
    86. 	assert(phead->next != phead);
    87.  
    88. 	//找到尾
    89. 	LTNode* tail = phead->prev;
    90. 	//找到尾前面一个元素
    91. 	LTNode* tailPrev = tail->prev;
    92. 	
    93. 	//释放内存
    94. 	free(tail);
    95.  
    96. 	//（把尾的上一个元素）的上一个指针 指向头
    97. 	tailPrev->next = phead;
    98. 	//头的下一个指针指向尾的前一个元素
    99. 	phead->prev = tailPrev;
    100.  
    101. 	// 双向链表删除pos位置的结点(本质上与尾删相似)
    102. 	//LTErase(phead->prev);
    103. }
    104.  
    105. //头插
    106. void LTPushFront(LTNode* phead, LTDataType x)
    107. {
    108. 	assert(phead);
    109.  
    110. 	//方法一
    111. 	//初始化
    112. 	//LTNode* newnode = BuyLTNode(x);
    113. 	//newnode->next = phead->next;
    114. 	//phead->next->prev = newnode;
    115. 	//phead->next = newnode;
    116. 	//newnode->prev = phead;
    117.  
    118. 	//方法二
    119. 	//初始化
    120. 	LTNode* newnode = BuyLTNode(x);
    121. 	LTNode* first = phead->next;
    122. 	phead->next = newnode;
    123. 	newnode->prev = phead;
    124. 	newnode->next = first;
    125. 	first->prev = newnode;
    126.  
    127. 	//方法三
    128. 	// 双向链表删除pos位置的结点(本质上就是头插)
    129. 	//LTInsert(phead->next, x);
    130. }
    131.  
    132. //头删（重点）
    133. void LTPopFront(LTNode* phead)
    134. {
    135. 	//断言
    136. 	assert(phead);
    137. 	//头指向不能为空
    138. 	assert(phead->next != phead);
    139.  
    140. 	//找到梢兵位的节点
    141. 	LTNode* first = phead->next;
    142. 	//找到头后面一个元素
    143. 	LTNode* second = first->next;
    144.  
    145. 	//释放内存
    146. 	free(first);
    147.  
    148. 	//梢兵位的节点指向头后面一个元素
    149. 	phead->next = second;
    150. 	//后面一个元素指向梢兵位的节点
    151. 	second->prev = phead;
    152.  
    153. 	//双向链表删除pos位置的结点(本质上和头删一样)
    154. 	//LTErase(phead->next);
    155. }
    156.  
    157. //统计双链表元素个数
    158. int LTSize(LTNode* phead)
    159. {
    160. 	//断言
    161. 	assert(phead);
    162.  
    163. 	int size = 0;
    164. 	LTNode* cur = phead->next;
    165. 	while (cur != phead)
    166. 	{
    167. 		++size;
    168. 		cur = cur->next;
    169. 	}
    170.  
    171. 	return size;
    172. }
    173.  
    174. // 双向链表在pos的前面进行插入
    175. void LTInsert(LTNode* pos, LTDataType x)
    176. {
    177. 	//断言
    178. 	assert(pos);
    179.  
    180. 	LTNode* posPrev = pos->prev;
    181. 	//为插入的元素开辟空间
    182. 	LTNode* newnode = BuyLTNode(x);
    183.  
    184. 	posPrev->next = newnode;
    185. 	newnode->prev = posPrev;
    186. 	newnode->next = pos;
    187. 	pos->prev = newnode;
    188. }
    189.  
    190. // 双向链表删除pos位置的结点
    191. void LTErase(LTNode* pos)
    192. {
    193. 	//断言
    194. 	assert(pos);
    195. 	LTNode* posPrev = pos->prev;
    196. 	LTNode* posNext = pos->next;
    197.  
    198. 	//释放内存
    199. 	free(pos);
    200.  
    201. 	posPrev->next = posNext;
    202. 	posNext->prev = posPrev;
    203. }
    204.  
    205.  
    206. //清理
    207. void ListClear(LTNode* phead)
    208. {
    209. 	//断言
    210. 	assert(phead);
    211. 	
    212. 	//清理全部数据，保留头结点
    213. 	LTNode* cur = phead->next;
    214. 	
    215. 	//循环销毁
    216. 	while (cur != phead)
    217. 	{
    218. 		LTNode* next = cur->next;
    219. 		free(cur);
    220. 		cur = NULL;
    221. 		cur = next;
    222. 	}
    223. }
    224.  
    225. //销毁
    226. void ListDestory(LTNode** pphead)
    227. {
    228. 	//断言
    229. 	assert(*pphead);
    230.  
    231. 	//调用清理（函数）
    232. 	ListClear(*pphead);
    233. 	
    234. 	//释放内存
    235. 	free(*pphead);
    236. 	*pphead = NULL;
    237. }

    🌟结束语

           今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

  • 相关阅读:
    微服务框架 SpringCloud微服务架构 5 Nacos 5.3 服务多级存储模型
    微信小程序使用本地存储方法
    ARM Linux DIY（十四）摄像头捕获画面显示到屏幕
    803_div2(Rising Sand, 接受军训！
    【前沿技术RPA】 一文了解UiPath的代码审查工具Workflow Analyzer
    任意代码执行漏洞复现
    网络层学习常见问题及答案整理
    if和， && ||
    linux设备模型：bus概念及pci_bus分析
    Kafka常见问题解析
  • 原文地址：https://blog.csdn.net/AAlykk/article/details/132776974