• 数据结构·双向链表

    目录

    链表的分类

    带头双向循环链表

    List.h

    List.c

    Test.c

    顺序表和链表的区别

    结束语

    链表的分类

    虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

              前面实现了单向链表 -- 但是在使用的过程中会发现，在尾部的操作在时间复杂度是O(N)级别，而且在扩容方面存在着较多的缺陷，导致了效率还是较低，为此我们引入了双向链表，这时才可以完美解决顺序表的所以缺陷

    1. 无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结 构的子结构 ，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。
    2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面代码实现了就知道了。

    带头双向循环链表

    List.h

    1. #pragma once
    2.  
    3. #include
    4. #include
    5. #include
    6. #include
    7.  
    8. typedef int LTDataType;	//重定义 方便改变数据类型
    9.  
    10. typedef struct ListNode
    11. {
    12. 	struct ListNode* next;
    13. 	struct ListNode* prve;
    14. 	LTDataType data;
    15. }LTNode;
    16.  
    17.  
    18. //初始话可以使用二级指针，也可以利用返回值来解决
    19. //1.二级指针初始化
    20. //void ListInit(LTNode** pphead); 
    21. //2.返回值初始化
    22. LTNode* ListInit();
    23.  
    24. //销毁链表 -- 遍历节点一个一个释放
    25. void ListDestory(LTNode* phead);
    26.  
    27. //打印
    28. void ListPrint(LTNode* phead);
    29.  
    30. //尾插
    31. void ListPushBack(LTNode* phead, LTDataType x);
    32.  
    33. //头插
    34. void ListPushFront(LTNode* phead, LTDataType x);
    35.  
    36. //判断空链表(不包括哨兵位的头节点)
    37. bool ListEmpty(LTNode* phead);
    38.  
    39. //尾删
    40. void ListPopBack(LTNode* phead);
    41.  
    42. //头删
    43. void ListPopFront(LTNode* phead);
    44.  
    45. //显示节点数量 -- 一般是单独把数量放在一个接口里面，尽量不要放在结构体里面
    46. size_t ListSize(LTNode* phead);
    47.  
    48. //查找
    49. LTNode* ListFind(LTNode* phead, LTDataType x);
    50.  
    51. //在pos之前插入
    52. void ListInsert(LTNode* pos, LTDataType x);
    53.  
    54. //删除pos节点
    55. void ListErase(LTNode* pos);

    List.c

    1. #include "List.h"
    2.  
    3. //初始化
    4. LTNode* ListInit()
    5. {
    6. 	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
    7. 	if (guard == NULL)
    8. 	{
    9. 		perror("malloc fail");
    10. 		exit(-1);
    11. 	}
    12.  
    13. 	guard->next = guard;
    14. 	guard->prve = guard;
    15.  
    16. 	return guard;
    17. }
    18.  
    19. //创立一个新的节点
    20. LTNode* BuyListNode(LTDataType x)
    21. {
    22.  
    23. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    24. 	if (node == NULL)
    25. 	{
    26. 		perror("malloc fail");
    27. 		exit(-1);
    28. 	}
    29.  
    30. 	node->next = NULL;	//新的节点置空
    31. 	node->prve = NULL;
    32. 	node->data = x;
    33.  
    34. 	return node;
    35. }
    36.  
    37.  
    38. //打印
    39. void ListPrint(LTNode* phead)
    40. {
    41. 	assert(phead); //一定不会为空因为有哨兵位的头节点
    42. 	printf("phead<=>");
    43. 	LTNode* cur = phead->next;	//当cur为哨兵位的头节点时就停下来结束打印
    44. 	while (cur != phead)
    45. 	{
    46.  
    47. 		printf("%d<=>", cur->data);
    48. 		cur = cur->next;
    49. 	}
    50. 	printf("\n");
    51. }
    52.  
    53.  
    54.  
    55. //尾插
    56. void ListPushBack(LTNode* phead, LTDataType x)
    57. {
    58. 	assert(phead);	//因为引入了哨兵位的头所以一定不会为空
    59.  
    60. 	
    61. 	//LTNode* newnode = BuyListNode(x);
    62.  
    63. 	利用头直接找到尾
    64. 	//LTNode* tail = phead->prve;
    65. 	//tail->next = newnode;
    66. 	//newnode->prve = tail;
    67. 	//newnode->next = phead;
    68. 	//phead->prve = newnode;
    69.  
    70. 	//当写好任意位置的插入时，就可以直接调用，不需要再写上面的了 -- 创建链表效率高
    71. 	ListInsert(phead, x); //在phead的前面插入一个就相当于尾插了
    72. }
    73.  
    74. //头插
    75. void ListPushFront(LTNode* phead, LTDataType x)
    76. {
    77. 	assert(phead);
    78. 	
    79. 	//1.这样子写需要注意先后顺序 -- 防止覆盖找不到下一个节点
    80. 	//LTNode* newnode = BuyListNode(x);
    81. 	//phead->next->prve = newnode;
    82. 	//newnode->next = phead->next;
    83.  
    84. 	//phead->next = newnode;
    85. 	//newnode->prve = phead;
    86.  
    87. 	//2.也可以创立一个新的指针来保存下一个节点，这样就可以随便改了
    88. 	//LTNode* newnode = BuyListNode(x);
    89. 	//LTNode* first = phead->next;
    90. 	//phead->next = newnode;
    91. 	//newnode->prve = phead;
    92. 	//newnode->next = first;
    93. 	//first->prve = newnode;
    94.  
    95. 	//同尾插一样 -- 当写好任意位置的插入时，就可以直接调用，不需要再写上面的了
    96. 	ListInsert(phead->next, x);
    97. }
    98.  
    99.  
    100. //判断空链表(不包括哨兵位的头节点)
    101. bool ListEmpty(LTNode* phead)
    102. {
    103. 	assert(phead);
    104.  
    105. 	//1.可以这样写 -- 较易理解
    106. 	//if (phead->next == NULL)
    107. 	//	return true;
    108. 	//else
    109. 	//	return false;
    110. 	
    111. 	//2.也可以直接返回
    112. 	return phead->next == phead;	//相等就是真(为空)否则就是假(不为空)
    113. }
    114.  
    115.  
    116. //尾删
    117. void ListPopBack(LTNode* phead)
    118. {
    119. 	assert(phead);
    120. 	assert(!ListEmpty(phead)); //是空返回真，！致反就为假，就报错
    121.  
    122. 	//LTNode* tail = phead->prve;
    123. 	//LTNode* prve = tail->prve;
    124.  
    125. 	//phead->prve = prve;
    126. 	//prve->next = phead;
    127. 	//free(tail);	
    128. 	//可以置空 -- 习惯，实际不起作用
    129. 	//tail = NULL;	
    130.  
    131. 	//一样一样
    132. 	ListErase(phead->prve);
    133. }
    134.  
    135.  
    136. //头删
    137. void ListPopFront(LTNode* phead)
    138. {
    139. 	assert(phead);
    140. 	assert(!ListEmpty(phead));
    141.  
    142. 	//LTNode* frist = phead->next;
    143. 	//LTNode* second = frist->next;
    144.  
    145. 	//phead->next = second;
    146. 	//second->prve = phead;
    147.  
    148. 	//free(frist);
    149. 	//frist = NULL;	
    150.  
    151. 	//一样一样
    152. 	ListErase(phead->next);
    153. }
    154.  
    155.  
    156. //显示节点数量
    157. size_t ListSize(LTNode* phead)
    158. {
    159. 	assert(phead);
    160.  
    161. 	size_t n = 0;
    162. 	LTNode* cur = phead->next;
    163. 	while (cur != phead)
    164. 	{
    165. 		++n;
    166. 		cur = cur->next;
    167. 	}
    168.  
    169. 	return n;
    170. }
    171.  
    172. //查找
    173. LTNode* ListFind(LTNode* phead,LTDataType x)
    174. {
    175. 	assert(phead);
    176.  
    177. 	LTNode* cur = phead->next;
    178. 	while (cur != phead)
    179. 	{
    180. 		if (cur->data == x)
    181. 		{
    182. 			return cur;
    183. 		}
    184. 		cur = cur->next;
    185. 	}
    186.  
    187. 	return NULL;
    188. }
    189.  
    190. //在pos之前插入
    191. void ListInsert(LTNode* pos, LTDataType x)
    192. {
    193. 	assert(pos); //因为这里不需要传原链表，所以没有判断链表是否为空
    194.  
    195. 	LTNode* prve = pos->prve;
    196. 	LTNode* newnode = BuyListNode(x);
    197.  
    198. 	// prve newnode pos 三个指针的链接
    199.  
    200. 	prve->next = newnode;
    201. 	newnode->prve = prve;
    202. 	newnode->next = pos;
    203. 	pos->prve = newnode;
    204. }
    205.  
    206.  
    207. //删除pos节点
    208. void ListErase(LTNode* pos)	//也没有传哨兵位的头节点 -- 所以不检查了
    209. {
    210. 	assert(pos);
    211.  
    212. 	LTNode* prve = pos->prve;
    213. 	LTNode* next = pos->next;
    214.  
    215. 	prve->next = next;
    216. 	next->prve = prve;
    217. 	free(pos);
    218. 	//pos->next == NULL; //这里是习惯 -- 因为不是二级指针 这里改是没用的
    219. }
    220.  
    221.  
    222. //销毁链表 -- 遍历节点一个一个释放
    223. //可以传二级指针，这样就内部置空 -- 但是也可以不置空，让调用的人自己置空（保持接口的一致性，都使用一级指针）
    224. void ListDestory(LTNode* phead)
    225. {
    226. 	assert(phead);
    227.  
    228. 	LTNode* cur = phead->next;
    229. 	while (cur != phead)
    230. 	{
    231. 		LTNode* next = cur->next;
    232. 		free(cur);
    233. 		cur = next;
    234. 	}
    235. 	free(phead);
    236. 	//phead = NULL; -- 这里置空没有用
    237. }

    Test.c

    1. #include "List.h"
    2.  
    3.  
    4. //测试
    5. void TestList1()
    6. {
    7. 	//二级指针初始化
    8. 	//LTNode* plist = NULL;
    9. 	//ListInit(&plist);
    10.  
    11. 	//返回值初始化
    12. 	LTNode* plist = ListInit();
    13. 	//尾插
    14. 	ListPushBack(plist, 1);
    15. 	ListPushBack(plist, 2);
    16. 	ListPushBack(plist, 3);
    17. 	ListPushBack(plist, 4);
    18. 	//打印
    19. 	ListPrint(plist);
    20.  
    21. 	//头插
    22. 	ListPushFront(plist, 10);
    23. 	ListPushFront(plist, 20);
    24. 	ListPushFront(plist, 30);
    25. 	ListPushFront(plist, 40);
    26. 	//打印
    27. 	ListPrint(plist);
    28.  
    29. 	//尾删
    30. 	ListPopBack(plist);
    31. 	ListPopBack(plist);
    32. 	ListPopBack(plist);
    33. 	ListPopBack(plist);
    34. 	//打印
    35. 	ListPrint(plist);
    36.  
    37. 	//头删
    38. 	ListPopFront(plist);
    39. 	//打印
    40. 	ListPrint(plist);
    41.  
    42. 	//显示节点数 -- %zu专门打印size_t类型的打印格式
    43. 	printf("%zu\n", ListSize(plist));
    44.  
    45. 	//查找并在其前面插入一个节点
    46. 	ListInsert(ListFind(plist,10),200);
    47. 	//打印
    48. 	ListPrint(plist);
    49.  
    50. 	//查找并在其删除这个节点
    51. 	ListErase(ListFind(plist, 200));
    52. 	//打印
    53. 	ListPrint(plist);
    54.  
    55. 	ListPopFront(plist);
    56. 	//打印
    57. 	ListPrint(plist);
    58.  
    59. 	//销毁链表 -- 因为内部不置空，所以外部要置空
    60. 	ListDestory(plist);
    61. 	plist = NULL;
    62. }
    63.  
    64. int main()
    65. {
    66. 	TestList1();
    67.  
    68. 	return 0;
    69. }

            到了这里关于链表的问题也差不多入门了，这也是在实际中运用广泛的一种链表了，可以很好的解决单链表的缺点，它完美的解决了增删查改的单链表的各个方面的不便。但是关于链表与顺序表之间它们又有很多方面的不同，在实际的运用也要加以区分。

    顺序表和链表的区别

    不同点                                    顺序表                                                 链表
    存储空间上                           物理上一定连续                        逻辑上连续,但物理上不一定连续
    随机访问                               支持O(1)                                          不支持：O(N)
    任意位置插入或者删除元素  可能需要搬移元素,效率低O(N)        只需修改指针指向
    插入                                     动态顺序表,空间不够时需要扩容      没有容量的概念
    应用场景                              元素高效存储+ 频繁访问                   任意位置插入和删除频繁
    缓存利用率                          高                                                       低 

    备注：缓存利用率参考存储体系结构 以及 局部原理性

    顺序表的优缺点

    优点 

    1、尾插尾删效率很高

    2、随机访问（用下标访问） 

    3、相比链表结构：cpu高速缓存命中率更高 

    缺点

    1、头部和中部插入删除效率低 -- O(N)

    2、扩容 -- 性能消耗 + 空间浪费

    链表的优缺点

    优点 

    1、任意位置插入删除效率很高 -- O(1)

    2、按需申请释放

    缺点

    1、不支持随机访问

    关于cpu告诉缓存命中率 

     

    在电脑的任务管理器中->性能->cpu中右下角可以看到

     

     

    cpu执行指令，不会直接访问内存

    1、先看数据在不在三级缓存，在(命中)。直接访问

    2、不在(不命中)，先加载到缓存，再访问

            加载的时候，由于顺序表开辟的空间是连续的空间，找到一个就相当于找到了后面的数据，而链表开辟的空间并不是连续的，所以访问到的命中率的概率就会较低

    与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell

    结束语

    上穷碧落下黄泉，两处茫茫皆不见。
                                                            唐·白居易 《长恨歌》 

  • 相关阅读:
    14 【TS类型声明 keepAlive】
    emq证书过期问题
    项目部署服务器【java】
    python如何判断字符串中的所有字符都是字母——isalpha函数的用法及实例
    设计模式：代理模式详解
    【附源码】计算机毕业设计SSM设计与实现大学常规信息管理系统
    从缺货到暴跌，芯片江湖的故事正愈演愈烈
    汽车空调工作总结
    SpringBoot中幕——配置文件properties与yml
    【Word】页眉编辑小技巧
  • 原文地址：https://blog.csdn.net/weixin_67595436/article/details/126192708