• 数据结构——双链表

    fe594ea5bf754ddbb223a54d8fb1e7bc.gif

    目录

    ​一.前言

    二.双链表的基本结构

    三.准备阶段

    3.1 空间函数

    3.2 初始化函数

    3.3 打印函数

    四.链表的实现

    4.1 尾插函数（可以让我们直观认识到该结构的妙用）

    4.2 尾删函数

    4.3 头插函数

    4.4 头删函数

    4.5 pos之前插入x函数

    4.6 在pos位置删除函数

    4.7 查找函数 

    4.8 销毁函数

    五.全部代码

    ​六.结语

    8fb442646f144d8daecdd2b61ec78ecd.png一.前言

    如果有友友看了我上一篇文章：数据结构——单链表，那么本篇的双链表会让你感到非常的安逸~无压力学会。码字不易，希望大家多多支持我呀！（三连＋关注，你是我滴神！）

    二.双链表的基本结构

     两两组合下链表一共有八种结构：而我们本文的重点就是带头双向循环链表。

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

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

    三.准备阶段

    3.1 空间函数

    1. //空间函数
    2. LTNode* BuyLTNode(LTDataType x)
    3. {
    4. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    5. 	if (node == NULL)
    6. 	{
    7. 		perror("malloc fail");
    8. 		exit(-1);
    9. 	}
    10. 	node->data = x;
    11. 	node->next = NULL;
    12. 	node->prev = NULL;
    13.  
    14. 	return node;
    15. 	
    16.  
    17. }

    3.2 初始化函数

    这里得用到二级指针了，要想改变plist（LTNode*)类型的指针，初始化函数就得用到（LTNode**）去接收，但我们可以换个思路，既然我们在不用到二级指针的情况下phead只是plist的临时拷贝，那么我们也可以让初始化函数的返回类型发生变化，这样也可以达到改变plist的作用。把初始化函数赋值给plist即可。

    1. //初始化函数
    2. LTNode* LTInit()
    3. {
    4.     //创造一个新节点，该节点是双向循环节点
    5. 	LTNode*phead = BuyLTNode(-1);
    6. 	phead->next = phead;
    7. 	phead->prev = phead;
    8. 	return phead;
    9.     //最后只要把这个我们人工初始化好的节点赋值给plist就好了
    10. }

    3.3 打印函数

    cur指向哨兵位phead的后面一位节点，这样方便打印。

    1. //打印函数
    2. void LTPrint(LTNode* phead)
    3. {
    4. 	assert(phead);
    5. 	printf("phead<=>");
    6. 	LTNode* cur = phead->next;
    7. 	while (cur != phead)
    8. 	{
    9. 		printf("%d<=>", cur->data);
    10. 		cur = cur->next;
    11. 	}
    12. 	printf("\n");
    13. }

    四.链表的实现

    先来个开胃小菜：

    4.1 尾插函数（可以让我们直观认识到该结构的妙用）

    不同于单链表（有节点要找尾，没节点插入第一个），在双链表中只需要把4个指针都标明好就行，方便又易懂，不用担心是否为空链表。最后出了作用域tail和newnode就会销毁，而新节点是由malloc在堆上申请的，所以还在。

    另外还有一点，这样不需要用到二级指针，因为我们有带头节点，这样phead是永远指向它的。

    1. void LTPushBack(LTNode* phead, LTDataType x)
    2. {
    3. 	assert(phead);//这里肯定要断言一下的，因为就算是初始化也会有作为头部的哨兵位。
    4. 	LTNode* newnode = BuyLTNode(x);
    5. 	LTNode* tail = phead->prev;
    6. 	tail->next = newnode;
    7. 	newnode->prev = tail;
    8. 	newnode->next = phead;
    9. 	phead->prev = newnode;
    10. 	
    11.  
    12. }

    4.2 尾删函数

       要实现尾插我们得注意两点：

    • 找到指向尾节点前一个节点的指针
    • 单链表为空时不能再进行尾删
    1. //尾删函数
    2. void LTPopBack(LTNode* phead)
    3. {
    4. 	assert(phead);//避免phead初始化没完成而导致出错
    5. 	assert(phead->next!=phead);//当删除到没有节点时，不能再继续尾删
    6. 	LTNode* tail = phead->prev;
    7. 	LTNode* tailPrev = tail->prev;
    8.  
    9. 	free(tail);
    10. 	tailPrev->next = phead;
    11. 	phead->prev = tailPrev;
    12. 	
    13. }

    大家应该逐渐发现双链表的优势所在了吧，基本上不用像单链表一样考虑到特殊情况然后去修改代码，单链表需要条件判断的问题，双链表都可以应对~

    4.3 头插函数

    头插也不需要用到二级指针，因为我们要改变的并非phead本身（phead只需要指向哨兵就行），而是改变phead指向的结构体（改变哨兵节点的指向）。

    注意别这么改，虽然最后可以通过各种前驱指针找到d1，但代价太大了。

    所以我们需要标记首节点（d1)的指向，让每次头插时都能找到原先作为头节点的指针。这里需要注意的是有先后顺序，先让新节点与首节点d1(phead->next指向)相互链接再让它与哨兵节点链接，这样可以避免d1节点地址的丢失。

    1. //头插函数
    2. void PushFront(LTNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5. 	LTNode* newnode = BuyLTNode(x);
    6. 	newnode->next = phead->next;
    7. 	phead->next->prev = newnode;
    8. 	phead->next = newnode;
    9. 	newnode->prev = phead;
    10. }

    测试一下：

    1. void TestList2()
    2. {
    3. 	LTNode* plist = LTInit();
    4.  
    5. 	LTPushBack(plist, 1);
    6. 	LTPushBack(plist, 2);
    7. 	LTPushBack(plist, 3);
    8. 	LTPushBack(plist, 4);
    9. 	LTPushBack(plist, 5);
    10. 	
    11. 	LTPushFront(plist, 10);
    12. 	LTPrint(plist);
    13.  
    14.  
    15. }

    但我建议换另一种写法，上面这种写法容易出错。

    定义好一个first的指针，这样顺序怎么搞都不会玩脱。

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

    4.4 头删函数

    上图是基本思路，我们定义指针的时候不要吝啬，出手阔气一点系统不会在意这点内存滴~

    就算是只剩下一个节点，照样拿捏~

    测试一下：

    1. void TestList3()
    2. {
    3. 	LTNode* plist = LTInit();
    4.  
    5. 	LTPushBack(plist, 1);
    6. 	LTPushBack(plist, 2);
    7. 	LTPushBack(plist, 3);
    8. 	LTPushBack(plist, 4);
    9. 	LTPushBack(plist, 5);
    10.  
    11. 	LTPopFront(plist);
    12. 	
    13. 	LTPrint(plist);
    14.  
    15.  
    16. }

    1. //头删函数
    2. void LTPopFront(LTNode* phead)
    3. {
    4. 	assert(phead);
    5. 	assert(phead->next != phead);
    6. 	LTNode* first = phead->next;
    7. 	LTNode* second = first->next;
    8. 	
    9. 	phead->next = second;
    10. 	second->prev = phead;
    11. 	free(first);
    12. }

    4.5 pos之前插入x函数

    简简单单~

    1. //pos之前插入x
    2. void LTInsert(LTNode* phead,LTNode* pos, LTDataType x)
    3. {
    4. 	assert(phead);
    5. 	LTNode* newnode = BuyLTNode(x);
    6. 	LTNode* posPrev = pos->prev;
    7.  
    8. 	newnode->prev = posPrev;
    9. 	newnode->next = pos;
    10. 	pos->prev = newnode;
    11. 	posPrev->next = newnode;
    12.  
    13. }

    其实我们可以发现写好了Insert函数再搭配的Find函数（更直观）就相当于写好了头插尾插了~

    4.6 在pos位置删除函数

    1. //删除pos位置的值
    2. void LTErase(LTNode* pos)
    3. {
    4. 	assert(pos);
    5. 	
    6. 	LTNode* posPrev = pos->prev;
    7. 	LTNode* posNext = pos->next;
    8. 	free(pos);
    9. 	posPrev->next = posNext;
    10. 	posNext->prev = posPrev;
    11.  
    12. }

    该函数也可以复用，起到头删，尾删的作用~

    4.7 查找函数 

    1. //寻找函数
    2. LTNode* LTFind(LTNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5. 	LTNode* cur = phead->next;
    6. 	while (cur!=phead)
    7. 	{
    8. 		if (cur->data == x)
    9. 		{
    10. 			return cur;
    11. 		}
    12. 		else
    13. 		{
    14. 			cur = cur->next;
    15. 		}
    16. 	}
    17.  
    18. 	return NULL;
    19. 	
    20. }

    可以与Insert函数搭配使用~

    1. void TestList4()
    2. {
    3. 	LTNode* plist = LTInit();
    4.  
    5. 	LTPushBack(plist, 1);
    6. 	LTPushBack(plist, 2);
    7. 	LTPushBack(plist, 3);
    8. 	LTPushBack(plist, 4);
    9. 	LTPushBack(plist, 5);
    10.  
    11. 	LTPopFront(plist);
    12. 	
    13. 	LTPrint(plist);
    14. 	int x = 0;
    15. 	scanf("%d", &x);
    16. 	LTNode* pos = LTFind(plist, x);
    17. 	
    18. 	if (pos)
    19. 	{
    20. 		LTInsert(plist, pos, 6);
    21. 	}
    22. 	LTPrint(plist);
    23.  
    24.  
    25. }

    4.8 销毁函数

    1. //销毁函数
    2. void LTDestort(LTNode* phead)
    3. {
    4.  
    5. 	assert(phead);
    6. 	LTNode* cur = phead->next;
    7. 	while (cur != phead)
    8. 	{
    9. 		LTNode* next = cur->next;
    10. 		free(cur);
    11. 		cur = next;
    12. 	}
    13.  
    14. 	free(phead);
    15.  
    16. }

    不需要置空 ，里面的形参不会影响到外面的实参。既然里面不用置空，那我们就让外面用的置空就行了。

    1. ​
    2. void TestList4()
    3. {
    4. 	LTNode* plist = LTInit();
    5.  
    6. 	LTPushBack(plist, 1);
    7. 	LTPushBack(plist, 2);
    8. 	LTPushBack(plist, 3);
    9. 	LTPushBack(plist, 4);
    10. 	LTPushBack(plist, 5);
    11.  
    12. 	LTPopFront(plist);
    13. 	
    14. 	LTPrint(plist);
    15. 	int x = 0;
    16. 	scanf("%d", &x);
    17. 	LTNode* pos = LTFind(plist, x);
    18. 	
    19. 	if (pos)
    20. 	{
    21. 		LTInsert(plist, pos, 6);
    22. 	}
    23. 	LTPrint(plist);
    24.     LTDestory(plist);
    25.     plist = NULL;
    26.  
    27.  
    28. }
    29.  
    30. ​

    五.全部代码

     

    1. //List.h
    2. #pragma once
    3.  
    4. #include 
    5. #include 
    6. #include 
    7.  
    8. typedef int LTDataType;
    9.  
    10. typedef struct ListNode
    11. {
    12. 	struct ListNode* prev;
    13. 	struct ListNode* next;
    14. 	LTDataType data;
    15. }LTNode;
    16.  
    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. //尾删函数
    31. void LTPopBack(LTNode* phead);
    32.  
    33. //头插函数
    34. void LTPushFront(LTNode* phead, LTDataType x);
    35.  
    36. //头删函数
    37. void LTPopFront(LTNode* phead);
    38.  
    39. //寻找函数
    40. LTNode* LTFind(LTNode* phead, LTDataType x);
    41.  
    42. //pos之前插入x
    43. void LTInsert(LTNode* phead,LTNode* pos, LTDataType x);
    44.  
    45. //删除pos位置的值
    46. void LTErase(LTNode* pos);
    47.  
    48. //销毁函数
    49. void LTDestort(LTNode* phead);

    ————————————————————————————————————————

    1. //List.c
    2. #define _CRT_SECURE_NO_WARNINGS 1
    3. #include "List.h"
    4.  
    5.  
    6.  
    7. //空间函数
    8. LTNode* BuyLTNode(LTDataType x)
    9. {
    10. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    11. 	if (node == NULL)
    12. 	{
    13. 		perror("malloc fail");
    14. 		exit(-1);
    15. 	}
    16. 	node->data = x;
    17. 	node->next = NULL;
    18. 	node->prev = NULL;
    19.  
    20. 	return node;
    21.  
    22.  
    23. }
    24.  
    25. //初始化函数
    26. LTNode* LTInit()
    27. {
    28. 	LTNode* phead = BuyLTNode(-1);
    29. 	phead->next = phead;
    30. 	phead->prev = phead;
    31. 	return phead;
    32. }
    33.  
    34.  
    35.  
    36. //打印函数
    37. void LTPrint(LTNode* phead)
    38. {
    39. 	assert(phead);
    40. 	printf("phead<=>");
    41. 	LTNode* cur = phead->next;
    42. 	while (cur != phead)
    43. 	{
    44. 		printf("%d<=>", cur->data);
    45. 		cur = cur->next;
    46. 	}
    47. 	printf("\n");
    48. }
    49.  
    50.  
    51.  
    52.  
    53.  
    54.  
    55. //尾插函数
    56. void LTPushBack(LTNode* phead, LTDataType x)
    57. {
    58. 	assert(phead);//这里肯定要断言一下的，因为就算是初始化也会有作为头部的哨兵位。
    59. 	LTNode* newnode = BuyLTNode(x);
    60. 	LTNode* tail = phead->prev;
    61. 	tail->next = newnode;
    62. 	newnode->prev = tail;
    63. 	newnode->next = phead;
    64. 	phead->prev = newnode;
    65.  
    66.  
    67. }
    68.  
    69.  
    70. //尾删函数
    71. void LTPopBack(LTNode* phead)
    72. {
    73. 	assert(phead);
    74. 	assert(phead->next != phead);
    75. 	LTNode* tail = phead->prev;
    76. 	LTNode* tailPrev = tail->prev;
    77.  
    78. 	free(tail);
    79. 	tailPrev->next = phead;
    80. 	phead->prev = tailPrev;
    81.  
    82. }
    83.  
    84. 头插函数
    85. //void LTPushFront(LTNode* phead, LTDataType x)
    86. //{
    87. //	assert(phead);
    88. //	LTNode* newnode = BuyLTNode(x);
    89. //	newnode->next = phead->next;
    90. //	phead->next->prev = newnode;
    91. //	phead->next = newnode;
    92. //	newnode->prev = phead;
    93. //}
    94. //头插函数
    95. void LTPushFront(LTNode* phead, LTDataType x)
    96. {
    97. 	assert(phead);
    98. 	LTNode* newnode = BuyLTNode(x);
    99. 	LTNode* first = phead->next;
    100. 	first->prev = newnode;
    101. 	newnode->next = first;
    102. 	phead->next = newnode;
    103. 	newnode->prev = newnode;
    104. }
    105.  
    106.  
    107.  
    108. //头删函数
    109. void LTPopFront(LTNode* phead)
    110. {
    111. 	assert(phead);
    112. 	assert(phead->next != phead);
    113. 	LTNode* first = phead->next;
    114. 	LTNode* second = first->next;
    115. 	
    116. 	phead->next = second;
    117. 	second->prev = phead;
    118. 	free(first);
    119. }
    120.  
    121.  
    122. //寻找函数
    123. LTNode* LTFind(LTNode* phead, LTDataType x)
    124. {
    125. 	assert(phead);
    126. 	LTNode* cur = phead->next;
    127. 	while (cur!=phead)
    128. 	{
    129. 		if (cur->data == x)
    130. 		{
    131. 			return cur;
    132. 		}
    133. 		else
    134. 		{
    135. 			cur = cur->next;
    136. 		}
    137. 	}
    138.  
    139. 	return NULL;
    140. 	
    141. }
    142.  
    143. //pos之前插入x
    144. void LTInsert(LTNode* phead,LTNode* pos, LTDataType x)
    145. {
    146. 	assert(phead);
    147. 	LTNode* newnode = BuyLTNode(x);
    148. 	LTNode* posPrev = pos->prev;
    149.  
    150. 	newnode->prev = posPrev;
    151. 	newnode->next = pos;
    152. 	pos->prev = newnode;
    153. 	posPrev->next = newnode;
    154.  
    155. }
    156.  
    157.  
    158.  
    159. //删除pos位置的值
    160. void LTErase(LTNode* pos)
    161. {
    162. 	assert(pos);
    163. 	
    164. 	LTNode* posPrev = pos->prev;
    165. 	LTNode* posNext = pos->next;
    166. 	free(pos);
    167. 	posPrev->next = posNext;
    168. 	posNext->prev = posPrev;
    169.  
    170. }
    171.  
    172.  
    173. //销毁函数
    174. void LTDestort(LTNode* phead)
    175. {
    176.  
    177. 	assert(phead);
    178. 	LTNode* cur = phead->next;
    179. 	while (cur != phead)
    180. 	{
    181. 		LTNode* next = cur->next;
    182. 		free(cur);
    183. 		cur = next;
    184. 	}
    185.  
    186. 	free(phead);
    187.  
    188. }

    ————————————————————————————————————————

    1. //Test.c
    2. #define _CRT_SECURE_NO_WARNINGS 1
    3. #include "List.h"
    4.  
    5. void TestList1()
    6. {
    7. 	LTNode* plist = LTInit();
    8.  
    9. 	LTPushBack(plist, 1);
    10. 	LTPushBack(plist, 2);
    11. 	LTPushBack(plist, 3);
    12. 	LTPushBack(plist, 4);
    13. 	LTPushBack(plist, 5);
    14. 	LTPopBack(plist);
    15. 	LTPrint(plist);
    16.  
    17. 	LTPopBack(plist);
    18. 	LTPrint(plist);
    19.  
    20. 	LTPopBack(plist);
    21. 	LTPrint(plist);
    22.  
    23. 	LTPopBack(plist);
    24. 	LTPrint(plist);
    25.  
    26. 	LTPopBack(plist);
    27. 	LTPrint(plist);
    28.  
    29.  
    30. }
    31.  
    32. void TestList2()
    33. {
    34. 	LTNode* plist = LTInit();
    35.  
    36. 	LTPushBack(plist, 1);
    37. 	LTPushBack(plist, 2);
    38. 	LTPushBack(plist, 3);
    39. 	LTPushBack(plist, 4);
    40. 	LTPushBack(plist, 5);
    41. 	
    42. 	LTPushFront(plist, 10);
    43. 	
    44. 	LTPrint(plist);
    45.  
    46.  
    47. }
    48.  
    49. void TestList3()
    50. {
    51. 	LTNode* plist = LTInit();
    52.  
    53. 	LTPushBack(plist, 1);
    54. 	LTPushBack(plist, 2);
    55. 	LTPushBack(plist, 3);
    56. 	LTPushBack(plist, 4);
    57. 	LTPushBack(plist, 5);
    58.  
    59. 	LTPopFront(plist);
    60. 	
    61. 	LTPrint(plist);
    62.  
    63.  
    64. }
    65.  
    66. void TestList4()
    67. {
    68. 	LTNode* plist = LTInit();
    69.  
    70. 	LTPushBack(plist, 1);
    71. 	LTPushBack(plist, 2);
    72. 	LTPushBack(plist, 3);
    73. 	LTPushBack(plist, 4);
    74. 	LTPushBack(plist, 5);
    75.  
    76. 	LTPopFront(plist);
    77. 	
    78. 	LTPrint(plist);
    79. 	int x = 0;
    80. 	scanf("%d", &x);
    81. 	LTNode* pos = LTFind(plist, x);
    82. 	
    83. 	if (pos)
    84. 	{
    85. 		LTInsert(plist, pos, 6);
    86. 	}
    87. 	LTPrint(plist);
    88.  
    89.  
    90. }
    91.  
    92. int main()
    93. {
    94. 	//TestList1();
    95. 	//TestList2();
    96. 	//TestList3();
    97. 	TestList4();
    98. 	return 0;
    99. }

    4b12323f94834afd9ec146a3c10df229.jpeg六.结语

    双链表是不是非常轻松呢~不像我们学单链表那时候草木皆兵，啥都要判断一下，双链表突出的就是一个结构稳定，安逸的很~最后感谢大家的观看，友友们能够学习到新的知识是额滴荣幸，期待我们下次相见~

  • 相关阅读:
    spark集群搭建
    沐神深度学习报错 can only concatenate str (not “int“) to str
    一、Vue3基础[组件(props、事件、插槽)]
    力扣练习——48 找到小镇的法官
    全新架构升级，游戏表现超过锐龙9， 英特尔正式发布12代酷睿
    LeetCode：第305场周赛【总结】
    vuex五大核心、辅助函数
    vue2 在循环里，给字体加上随机颜色并加上随机图标且少重复
    selenium进阶设置
    RIS 系列 Beyond One-to-One: Rethinking the Referring Image Segmentation 论文阅读笔记
  • 原文地址：https://blog.csdn.net/fax_player/article/details/133187232