• 【数据结构】——双链表（增删查改）

     

    目录

    前言：

    一：双链表的定义

    ​编辑 二：双向链表的实现

    2.1：链表的构造

    2.2：创建头节点

    2.3：创建节点 

    2.4：链表的尾插 

    2.5：链表的打印

    2.6：链表的尾删

    2.7：链表的头插

    2.8：链表的头删

    2.9：链表的查找 

    2.10：在目标位置前面插入

    2.11：删除目标位置结点

    2.12：链表的销毁

     总代码：

    test.c

    List.c

     List.h

     

    前言：

    双链表的引入是因为单链表要访问某个结点的前驱结点时，只能从头开始遍历，访问后驱结点的复杂度为O(1)，访问前驱结点的复杂度为O(n)。为了克服上述缺点，引入了双链表。

    双链表的引进，对于链表的操作有了极大的遍历；

    一：双链表的定义

    链表由单向的链变成了双向链。

    双向链表(double linked list)是在单链表的每个结点中再设置一个指向其前驱结点的指针域。 

     二：双向链表的实现

    2.1：链表的构造

    包含了一个数据域，两个指针域（指向前后驱节点）

    1. // 带头+双向+循环链表增删查改实现
    2. typedef int LTDataType;
    3. typedef struct ListNode
    4. {
    5. 	LTDataType data;		//数据
    6. 	struct ListNode* next;	//下一个指针域
    7. 	struct ListNode* prev;	//上一个指针域
    8. }ListNode;

     

    2.2：创建头节点

    双向链表一般都是带头节点的，在链表中，带了头节点对于链表分割这一问题有了简单化；

    动态开辟出一块空间，前后指针都指向自己；

    1. //初始化链表头头节点
    2. ListNode* ListInit()
    3. {
    4. 	 ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    5. 	 assert(phead);
    6. 	 phead->data = -1;
    7. 	 phead->next = phead;
    8. 	 phead->prev = phead;
    9. 	 return phead;
    10. }

    2.3：创建节点 

    这里置NULL，和单链表的置NULL，是一样的意思，对后续的操作提供便利；

    1. // 创建返回链表的结点.
    2. ListNode* ListCreate(LTDataType x)
    3. {
    4. 	 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    5. 	 assert(newnode);
    6. 	 newnode->data = x;
    7. 	 newnode->next = NULL;
    8. 	 newnode->prev = NULL;
    9. 	 return newnode;
    10. }

    2.4：链表的尾插 

    单链表的尾插还需要考虑是否存在第一个节点，这里直接插入即可；

    注意操作顺序

    1. // 双向链表尾插
    2. void ListPushBack(ListNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5. 	ListNode* newnode = ListCreate(x);
    6.  
    7. 	struct ListNode* tail = phead->prev;
    8. 	// phead tail  newnode
    9.  
    10. 	//newnode->prev = phead->prev;
    11. 	//newnode->next = phead;
    12. 	//phead->prev->next = newnode;
    13. 	//phead->prev = newnode;
    14.  
    15. 	//注意前后顺序
    16. 	newnode->prev = tail;
    17. 	tail->next = newnode;
    18. 	newnode->next = phead;
    19. 	phead->prev = newnode;
    20.  
    21. }

    2.5：链表的打印

    这里的关键就是从哪里开始？如何判断结束（因为是循环）？

    我们可以从头结点的下一个开始打印，当遇到头结点即是结束；

    1. // 双向链表打印
    2. void ListPrint(ListNode* phead)
    3. {
    4. 	assert(phead);
    5. 	struct ListNode* cur = phead->next;
    6. 	printf("哨兵位<=>");
    7. 	while (cur != phead)
    8. 	{
    9. 		printf("%d<=>", cur->data);
    10. 		cur = cur->next;
    11. 	}
    12. 	printf("\n");
    13. }

     

    2.6：链表的尾删

    要多一个断言判断：如果只有一个头指针就不用操作了；

    保存尾结点的前驱，释放尾结点即可

    1. // 双向链表尾删
    2. void ListPopBack(ListNode* phead)
    3. {
    4. 	assert(phead);
    5. 	assert(phead->next != phead);	//只有头指针不删
    6.  
    7. 	struct ListNode* cur = phead->prev;
    8. 	struct ListNode* curPrev = cur->prev;	//尾节点的上一个
    9. 	phead->prev = curPrev;
    10. 	curPrev->next = phead;
    11. 	free(cur);
    12. 	cur = NULL;
    13. }

     

    2.7：链表的头插

    和尾插操作相似，定义头节点的下一个结点，进行链接即可；

    注意顺序；

    1. // 双向链表头插
    2. void ListPushFront(ListNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5.  
    6. 	ListNode* newnode = ListCreate(x);
    7. 	struct ListNode* cur = phead->next;
    8.  
    9. 	newnode->next = cur;	
    10. 	cur->prev = newnode;
    11. 	newnode->prev = phead;
    12. 	phead->next = newnode;
    13. }

     

    2.8：链表的头删

    删除操作一般都需要判断一下是否只有头节点。判断双向链表的条件是：phead->next != phead;

    1. // 双向链表头删
    2. void ListPopFront(ListNode* phead)
    3. {
    4. 	assert(phead);
    5. 	assert(phead->next != phead);	//只有头指针不删
    6.  
    7. 	ListNode* cur = phead->next;
    8. 	ListNode* next = cur->next;
    9.  
    10. 	phead->next = next;
    11. 	next->prev = phead;
    12.  
    13. 	free(cur);
    14. 	cur = NULL;
    15. }

    2.9：链表的查找 

    找到该结点后，返回的是指针，而不是数据，返回该指针位置，方便后续操作

    1. // 双向链表查找
    2. ListNode* ListFind(ListNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5. 	
    6. 	ListNode* cur = phead->next;
    7. 	while (cur != phead)
    8. 	{
    9. 		if (cur->data == x)
    10. 			return cur;
    11. 		cur = cur->next;
    12. 	}
    13. 	return NULL;
    14. }

    2.10：在目标位置前面插入

    1. // 双向链表在pos的前面进行插入
    2. void ListInsert(ListNode* pos, LTDataType x)
    3. {
    4. 	assert(pos);	//检查pos位置是否有效
    5. 	ListNode* newnode = ListCreate(x);
    6.  
    7. 	newnode->next = pos;	//将newnode节点next prev 链接前后节点
    8. 	newnode->prev = pos->prev;
    9. 	pos->prev->next = newnode;
    10. 	pos->prev = newnode;
    11. }

     

    2.11：删除目标位置结点

    1. // 双向链表删除pos位置的节点
    2. void ListErase(ListNode* pos)
    3. {
    4. 	assert(pos);
    5. 	
    6. 	ListNode* posPrev = pos->prev;
    7. 	ListNode* next = pos->next;
    8.  
    9. 	posPrev->next = next;
    10. 	next->prev = posPrev;
    11. 	free(pos);
    12. 	pos = NULL;
    13. }

     

    2.12：链表的销毁

    1. // 双向链表销毁
    2. void ListDestory(ListNode* phead)
    3. {
    4. 	assert(phead);
    5. 	ListNode* cur = phead->prev;
    6. 	while (cur != phead)		//将除了头结点的都销毁
    7. 	{
    8. 		ListNode* curPrev = cur->prev;
    9. 		free(cur);
    10. 		cur = curPrev;
    11. 	}
    12. 	free(phead);    //再释放头结点
    13. 	//phead = NULL;
    14. }

     总代码：

    test.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"List.h"
    3.  
    4.  
    5. void test1()
    6. {
    7. 	ListNode* plist = NULL;
    8. 	plist = ListInit();
    9. 	ListPushBack(plist, 1);
    10. 	ListPushBack(plist, 2);
    11. 	ListPushBack(plist, 3);
    12. 	ListPushBack(plist, 4);
    13. 	ListPrint(plist);
    14.  
    15. 	ListPopBack(plist);
    16. 	ListPrint(plist);
    17.  
    18. 	ListPopBack(plist);
    19. 	ListPrint(plist);
    20.  
    21. 	ListPopBack(plist);
    22. 	ListPrint(plist);
    23.  
    24. 	ListPopBack(plist);
    25. 	ListPrint(plist);
    26.  
    27. }
    28.  
    29.  
    30. void test2()
    31. {
    32. 	ListNode* plist = NULL;
    33. 	plist = ListInit();
    34.  
    35. 	ListPrint(plist);
    36. 	//ͷ
    37. 	ListPushFront(plist, 6);
    38. 	ListPrint(plist);
    39.  
    40. 	//ͷɾ
    41. 	ListPopFront(plist);
    42. 	ListPrint(plist);
    43.  
    44. }
    45.  
    46. void test3()
    47. {
    48. 	ListNode* plist = NULL;
    49. 	plist = ListInit();
    50. 	ListPushBack(plist, 1);
    51. 	ListPushBack(plist, 2);
    52. 	ListPushBack(plist, 3);
    53. 	ListPushBack(plist, 4);
    54. 	ListPrint(plist);
    55. 		
    56. 	//βɾ
    57. 	ListPopBack(plist);
    58. 	ListPopBack(plist);
    59. 	ListPopBack(plist);
    60.  
    61. 	ListNode* pos = ListFind(plist,1);
    62.  
    63. 	ListInsert(pos, 666);
    64. 	ListPrint(plist);
    65.  
    66. 	ListErase(pos);
    67. 	ListPrint(plist);
    68.  
    69. 	ListDestory(plist);
    70. }
    71. int main()
    72. {
    73. 	//test1();
    74. 	//test2();
    75. 	test3();
    76. 	return 0;
    77. }

    List.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"List.h"
    3.  
    4.  
    5. //初始化链表头头节点
    6. ListNode* ListInit()
    7. {
    8. 	 ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    9. 	 assert(phead);
    10. 	 phead->data = -1;
    11. 	 phead->next = phead;
    12. 	 phead->prev = phead;
    13. 	 return phead;
    14. }
    15.  
    16. // 创建返回链表的头结点.
    17. ListNode* ListCreate(LTDataType x)
    18. {
    19. 	 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    20. 	 assert(newnode);
    21. 	 newnode->data = x;
    22. 	 newnode->next = NULL;
    23. 	 newnode->prev = NULL;
    24. 	 return newnode;
    25. }
    26.  
    27. // 双向链表尾插
    28. void ListPushBack(ListNode* phead, LTDataType x)
    29. {
    30. 	assert(phead);
    31. 	ListNode* newnode = ListCreate(x);
    32.  
    33. 	struct ListNode* tail = phead->prev;
    34. 	// phead tail  newnode
    35.  
    36. 	//newnode->prev = phead->prev;
    37. 	//newnode->next = phead;
    38. 	//phead->prev->next = newnode;
    39. 	//phead->prev = newnode;
    40.  
    41. 	//注意前后顺序
    42. 	newnode->prev = tail;
    43. 	tail->next = newnode;
    44. 	newnode->next = phead;
    45. 	phead->prev = newnode;
    46.  
    47. }
    48.  
    49. // 双向链表打印
    50. void ListPrint(ListNode* phead)
    51. {
    52. 	assert(phead);
    53. 	struct ListNode* cur = phead->next;
    54. 	printf("哨兵位<=>");
    55. 	while (cur != phead)
    56. 	{
    57. 		printf("%d<=>", cur->data);
    58. 		cur = cur->next;
    59. 	}
    60. 	printf("\n");
    61. }
    62.  
    63. // 双向链表尾删
    64. void ListPopBack(ListNode* phead)
    65. {
    66. 	assert(phead);
    67. 	assert(phead->next != phead);	//只有头指针不删
    68.  
    69. 	struct ListNode* cur = phead->prev;
    70. 	struct ListNode* curPrev = cur->prev;	//尾节点的上一个
    71. 	phead->prev = curPrev;
    72. 	curPrev->next = phead;
    73. 	free(cur);
    74. 	cur = NULL;
    75. }
    76.  
    77. // 双向链表头插
    78. void ListPushFront(ListNode* phead, LTDataType x)
    79. {
    80. 	assert(phead);
    81.  
    82. 	ListNode* newnode = ListCreate(x);
    83. 	struct ListNode* cur = phead->next;
    84.  
    85. 	newnode->next = cur;	
    86. 	cur->prev = newnode;
    87. 	newnode->prev = phead;
    88. 	phead->next = newnode;
    89. }
    90.  
    91. // 双向链表头删
    92. void ListPopFront(ListNode* phead)
    93. {
    94. 	assert(phead);
    95. 	assert(phead->next != phead);	//只有头指针不删
    96.  
    97. 	ListNode* cur = phead->next;
    98. 	ListNode* next = cur->next;
    99.  
    100. 	phead->next = next;
    101. 	next->prev = phead;
    102.  
    103. 	free(cur);
    104. 	cur = NULL;
    105. }
    106.  
    107. // 双向链表查找
    108. ListNode* ListFind(ListNode* phead, LTDataType x)
    109. {
    110. 	assert(phead);
    111. 	
    112. 	ListNode* cur = phead->next;
    113. 	while (cur != phead)
    114. 	{
    115. 		if (cur->data == x)
    116. 			return cur;
    117. 		cur = cur->next;
    118. 	}
    119. 	return NULL;
    120. }
    121.  
    122. // 双向链表在pos的前面进行插入
    123. void ListInsert(ListNode* pos, LTDataType x)
    124. {
    125. 	assert(pos);	//检查pos位置是否有效
    126. 	ListNode* newnode = ListCreate(x);
    127.  
    128. 	newnode->next = pos;	//将newnode节点next prev 链接前后节点
    129. 	newnode->prev = pos->prev;
    130. 	pos->prev->next = newnode;
    131. 	pos->prev = newnode;
    132. }
    133.  
    134. // 双向链表删除pos位置的节点
    135. void ListErase(ListNode* pos)
    136. {
    137. 	assert(pos);
    138. 	
    139. 	ListNode* posPrev = pos->prev;
    140. 	ListNode* next = pos->next;
    141.  
    142. 	posPrev->next = next;
    143. 	next->prev = posPrev;
    144. 	free(pos);
    145. 	pos = NULL;
    146. }
    147.  
    148. // 双向链表销毁
    149. void ListDestory(ListNode* phead)
    150. {
    151. 	assert(phead);
    152. 	ListNode* cur = phead->prev;
    153. 	while (cur != phead)		//将除了头节点的都销毁
    154. 	{
    155. 		ListNode* curPrev = cur->prev;
    156. 		free(cur);
    157. 		cur = curPrev;
    158. 	}
    159. 	free(phead);
    160. 	//phead = NULL;
    161. }

     List.h

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

     以上就是我对【数据结构|双向链表|增删改查】的介绍，不足之处，还望指点。

     

  • 相关阅读:
    虚拟机（三）VMware Workstation 桥接模式下无法上网
    SpringSecurity6从入门到上天系列第七篇：讲明白SpringBoot的自动装配完善上篇文章中的结论
    C++ STL有用？如何调试？
    [笔记]CentOS7 vsftpd安装及配置使用
    RPA是什么？推荐让电商运营10倍提效的自动化工具
    static关键字总结-C/C++
    04.JavaScript（深浅拷贝、异常处理、改变this执行）
    听我一句劝好吗？放下那些老掉牙的性能优化笔记吧！又不是没有新的，跟不上时代的学了也没法直接用呀！
    我，PolarDB云原生数据库，5年来实现这些重磅技术创新
    Node.js 入门（1）：Node 简介和安装
  • 原文地址：https://blog.csdn.net/m0_67367079/article/details/134507170