devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

双向链表的功能实现_创建双向链表

作者：我家小花儿 | 2024-04-15 10:40:40

赞

踩

创建双向链表

      前言：我们已经学习并知道了单链表的实现，链表的实现方式不只是单链表一种，今天我们就来介绍一种新的结构，就是双链表结构，本质上是将节点间进行双向链接，从而使一些操作更加容易实现。

目录

1.双向链表的简介

2.双向链表的实现

带头节点的哨兵位的创建和初始化

为什么要使用哨兵位？

节点的头、尾插和头、尾删

插入和删除函数

完整程序代码及测试代码

List.h

List.cpp

Test.cpp

3.金句频道

1.双向链表的简介

        双向链表（Doubly Linked List）是一种常见的线性数据结构，它相比于单向链表多了一个指针，可以支持双向遍历。

       每个节点在双向链表中都有两个指针，一个指向前一个节点，一个指向后一个节点，因此可以从任意一个节点开始，依次遍历前一个节点和后一个节点。双向链表可以对数据进行插入和删除操作，这些操作相比较单向链表来说更加方便和高效。

 双向链表的特点包括：

1. 每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。
2. 可以从任意一个节点开始，依次遍历前一个节点和后一个节点。
3. 可以对数据进行插入和删除操作，保证了操作的高效性和方便性。
4. 相对于单向链表来说，占用更多的存储空间，因为需要多一个指针来指向前一个节点。

     

      需要注意的是，当插入或删除一个节点时，需要同时修改其前后两个节点的指针，才能保证链表结构的完整性。

2.双向链表的实现

带头节点的哨兵位的创建和初始化

为什么要使用哨兵位？

       链表中哨兵位（Sentinel）是一种特殊的节点，位于链表头部或尾部，不存储任何实际的数据。引入哨兵位的主要目的是为了简化链表的操作，提高代码的可读性和可维护性。

使用哨兵位的优点主要包括：

1. 简化代码逻辑：引入哨兵位后，链表的头尾节点都指向哨兵位而不是NULL，这样在任何情况下，我们都不需要对头尾节点进行特判，也不需要用二级指针进行传址了(链表中引入二级指针的目的，其实就是为了在头结点为空的情况下，节点还能正常创建并使用，说白了就是为了“对NULL指针进行解引用操作”）。这样能够简化代码逻辑，减少代码复杂度，提高代码可读性和可维护性。

2. 避免空指针异常：使用哨兵位可以避免在链表为空或链表操作时出现空指针异常。如果没有哨兵位，我们需要在头尾节点为空时进行特判，否则可能会导致程序崩溃。

  1. LTNode* LTInit()
  2. {
  3. 	Listnode head = (Listnode)malloc(sizeof(LTNode));
  4. 	assert(head);//断言，防止开辟不成功
  5. 	head->data = -1;
  6. 	//初始让头结点的前驱和后继都指向自己，这样可以便与判断链表是否为空并且与尾结点指向哨兵位的操作上统一
  7. 	head->next = head->prev = head;
  8. 	return head;
  9. }

节点的头、尾插和头、尾删

        这些操作基本与单链表的操作大同小异，只是多了一个前驱结点的操作，这里需要注意以下几点：

1.注意对可能为NULL的指针进行断言避免出现野指针和堆错误问题；

2.对不再使用的空间进行及时的释放，避免内存泄漏。

  1. //头插
  2. void LTPushFront(LTNode* phead, LTDataType x)
  3. {
  4. 	
  5. 	assert(phead);
  6. 	LTNode* newnode = new LTNode(x);
  7. 	LTNode* first = phead->next;
  8.  
  9. 	phead->next = newnode;
  10. 	newnode->prev = phead;
  11.  
  12. 	newnode->next = first;
  13. 	first->prev = newnode;
  14. 	
  15.  
  16. 	//LTInsert(phead->next, x);
  17. }
  18.  
  19. //尾插
  20. void LTPushBack(LTNode* phead, LTDataType x)
  21. {
  22. 	Listnode newnode = new LTNode(x);
  23.  
  24. 	//这里最好将两个及以上解引用的操作分开
  25. 	LTNode *first = phead->prev;
  26. 	first->next = newnode;
  27. 	newnode->next = phead;
  28. 	newnode->prev = first;
  29. 	phead->prev = newnode;
  30.  
  31. 	//或者可以直接调用插入函数
  32. 	//LTInsert(phead, x);
  33. }
  34.  
  35. //头删
  36. void LTPopFront(LTNode* phead)
  37. {
  38. 	assert(phead);
  39. 	assert(!LTEmpty(phead));
  40. 	
  41. 	LTNode* p = phead->next;
  42. 	LTNode* ppnext = p->next;
  43.  
  44. 	free(p);
  45. 	phead->next=ppnext;
  46. 	ppnext->prev=phead;
  47. 	
  48. 	//LTErase(phead->next);
  49. }
  50.  
  51. //尾删
  52. void LTPopBack(LTNode* phead)
  53. {
  54. 	assert(phead);
  55. 	assert(!LTEmpty(phead));
  56. 	
  57. 	LTNode* tail = phead->prev;
  58. 	LTNode* tailPrev = tail->prev;
  59.  
  60. 	free(tail);
  61. 	tailPrev->next = phead;
  62. 	phead->prev = tailPrev;
  63. 	
  64.  
  65. 	//LTErase(phead->prev);
  66. }

       细心地朋友可能已经注意到了，这些不同的函数内部都有相同的LTInsert或LTErase函数，这不是偶然，我们将不同方式插入或删除的函数进行对比，就会发现，它们的代码具有一定的逻辑重复性，存在逻辑上互通的部分，我们可以将这个部分归纳为一个函数，像头插和尾插，我们可以写一个在任意节点前或后插入的函数，再将不同的节点需要的参数分别传入，就能实现不同的功能，尾删和头删也是同理，这样就大大简化了代码，减少了使用指针出错的可能性。

插入和删除函数

  1. // 在pos之前插入
  2. void LTInsert(LTNode* pos, LTDataType x)
  3. {
  4. 	assert(pos);//断言，判断pos是否合法
  5.  
  6. 	Listnode newnode = new LTNode(x);
  7. 	Listnode pre = pos->prev;
  8. 	pre->next = newnode;
  9. 	newnode->next = pos;
  10. 	newnode->prev = pre;
  11. 	pos->prev = newnode;
  12.  
  13. }
  14.  
  15. // 删除pos位置的值
  16. void LTErase(LTNode* pos)
  17. {
  18. 	assert(pos);
  19. 	Listnode front = pos->prev;
  20. 	Listnode behind = pos->next;
  21. 	front->next = behind;
  22. 	behind->prev = front;
  23. 	free(pos);
  24. 	pos = NULL;
  25. }

完整程序代码及测试代码

List.h

  1. #pragma once
  2.  
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<assert.h>
  6. #include<stdbool.h>
  7.  
  8. typedef int LTDataType;
  9. typedef struct ListNode
  10. {
  11. 	struct ListNode* next;
  12. 	struct ListNode* prev;
  13. 	LTDataType data;
  14. 	//C++构造函数//可不写
  15. 	ListNode(LTDataType d = 0, ListNode* pr = NULL, ListNode* ne = NULL)
  16. 	{
  17. 		data = d, prev = pr, next = ne;
  18. 	}
  19. }LTNode,*Listnode;
  20.  
  21. //创建并初始化头结点
  22. LTNode* LTInit();
  23.  
  24. //打印带头结点的单链表
  25. void LTPrint(LTNode* phead);
  26.  
  27. //判断链表是否为空
  28. bool LTEmpty(LTNode* phead);
  29.  
  30. //尾插
  31. void LTPushBack(LTNode* phead, LTDataType x);
  32.  
  33. //头插
  34. void LTPushFront(LTNode* phead, LTDataType x);
  35.  
  36. //尾删
  37. void LTPopBack(LTNode* phead);
  38.  
  39. //头删
  40. void LTPopFront(LTNode* phead);
  41.  
  42. //查找值为x的节点
  43. LTNode* LTFind(LTNode* phead, LTDataType x);
  44.  
  45. // 在pos之前插入
  46. void LTInsert(LTNode* pos, LTDataType x);
  47.  
  48. // 删除pos位置的值
  49. void LTErase(LTNode* pos);
  50.  
  51. //销毁链表
  52. void LTDestroy(LTNode* phead);

List.cpp

  1. #include <bits/stdc++.h>
  2. #include "List.h"
  3. using namespace std;
  4.  
  5. LTNode* LTInit()
  6. {
  7. 	Listnode head = (Listnode)malloc(sizeof(LTNode));
  8. 	assert(head);//断言，防止开辟不成功
  9. 	head->data = -1;
  10. 	//初始让头结点的前驱和后继都指向自己
  11. 	head->next = head->prev = head;
  12. 	return head;
  13. }
  14. void LTPrint(LTNode* phead)
  15. {
  16. 	assert(phead);
  17. 	printf("guard");
  18. 	Listnode p = phead->next;
  19. 	while (p!= phead)
  20. 	{
  21. 		printf("->%d", p->data);
  22. 		p = p->next;
  23. 	}
  24. 	printf("\n");
  25. }
  26.  
  27. // 在pos之前插入
  28. void LTInsert(LTNode* pos, LTDataType x)
  29. {
  30. 	assert(pos);//断言，判断pos是否合法
  31.  
  32. 	Listnode newnode = new LTNode(x);
  33. 	Listnode pre = pos->prev;
  34. 	pre->next = newnode;
  35. 	newnode->next = pos;
  36. 	newnode->prev = pre;
  37. 	pos->prev = newnode;
  38.  
  39. }
  40. bool LTEmpty(LTNode* phead)
  41. {
  42. 	return phead->next == phead;
  43. }
  44. void LTPushBack(LTNode* phead, LTDataType x)
  45. {
  46. 	Listnode newnode = new LTNode(x);
  47.  
  48. 	//这里最好将两个及以上解引用的操作分开
  49. 	LTNode *first = phead->prev;
  50. 	first->next = newnode;
  51. 	newnode->next = phead;
  52. 	newnode->prev = first;
  53. 	phead->prev = newnode;
  54.  
  55. 	//或者可以直接调用插入函数
  56. 	//LTInsert(phead, x);
  57. }
  58. void LTPushFront(LTNode* phead, LTDataType x)
  59. {
  60. 	
  61. 	assert(phead);
  62. 	LTNode* newnode = new LTNode(x);
  63. 	LTNode* first = phead->next;
  64.  
  65. 	phead->next = newnode;
  66. 	newnode->prev = phead;
  67.  
  68. 	newnode->next = first;
  69. 	first->prev = newnode;
  70. 	
  71.  
  72. 	//LTInsert(phead->next, x);
  73. }
  74. void LTPopBack(LTNode* phead)
  75. {
  76. 	assert(phead);
  77. 	assert(!LTEmpty(phead));
  78. 	
  79. 	LTNode* tail = phead->prev;
  80. 	LTNode* tailPrev = tail->prev;
  81.  
  82. 	free(tail);
  83. 	tailPrev->next = phead;
  84. 	phead->prev = tailPrev;
  85. 	
  86.  
  87. 	//LTErase(phead->prev);
  88. }
  89. void LTPopFront(LTNode* phead)
  90. {
  91. 	assert(phead);
  92. 	assert(!LTEmpty(phead));
  93. 	
  94. 	LTNode* p = phead->next;
  95. 	LTNode* ppnext = p->next;
  96.  
  97. 	free(p);
  98. 	phead->next=ppnext;
  99. 	ppnext->prev=phead;
  100. 	
  101. 	//LTErase(phead->next);
  102. }
  103.  
  104. LTNode* LTFind(LTNode* phead, LTDataType x)
  105. {
  106. 	assert(phead);
  107. 	Listnode p = phead->next;
  108. 	while (p!= phead)
  109. 	{
  110. 		if (p->data == x)
  111. 			return p;
  112. 		p = p->next;
  113. 	}
  114. 	return NULL;
  115. }
  116.  
  117.  
  118. // 删除pos位置的值
  119. void LTErase(LTNode* pos)
  120. {
  121. 	assert(pos);
  122. 	Listnode front = pos->prev;
  123. 	Listnode behind = pos->next;
  124. 	front->next = behind;
  125. 	behind->prev = front;
  126. 	free(pos);
  127. 	pos = NULL;
  128. }
  129. void LTDestroy(LTNode* phead)
  130. {
  131. 	
  132. 	assert(phead);
  133. 	LTNode* cur = (phead)->next;
  134. 	while (cur != phead)
  135. 	{
  136. 		LTNode* next = cur->next;
  137. 		free(cur);
  138. 		cur = next;
  139. 	}
  140. 	free(phead);
  141. 	phead = NULL;//此处传的是一级指针，在外部函数内修改没有作用,应该传二级指针或者在主函数内进行销毁,这里我们选择在主函数内单独进行置空
  142. }

Test.cpp

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

3.金句频道

      最近看到这样一句话：“当我真正开始爱自己，我睡的越来越早，也越来越喜欢锻炼。我不在纠结和焦虑，变得自信满满，去追求有意义的人和事，并为之燃烧自己的热情。我发现，人生才刚刚开始.”

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/427411
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号