深圳幻海软件技术有限公司 欢迎您！
更多

数据结构——双向链表

2023-03-14

next 结点 prev
🍇系列专栏：🌙数据结构🍉 欢迎关注：👍点赞🍃收藏🔥留言🍎博客主页：🌙_麦麦_的博客_CSDN博客-领域博主🌙如果我们都不能够拥有黑夜，又该怎样去仰望星空？ 目录一、前言二、正文——双向链表的实现2.1模块化2.2数据类型与结构体定义 2.3链表的初始化

🍇系列专栏：🌙数据结构

🍉 欢迎关注：👍点赞🍃收藏🔥留言

🍎 博客主页：🌙_麦麦_的博客_CSDN博客-领域博主
🌙如果我们都不能够拥有黑夜，又该怎样去仰望星空？ 

目录

一、前言

二、正文——双向链表的实现

2.1模块化

2.2 数据类型与结构体定义

 2.3链表的初始化

 2.4链表的打印

2.5 链表的查找

 2.6判断链表是否只有哨兵卫

2.7申请新的结点 

2.8 链表的尾插

 2.9链表的尾删

 2.10链表的头插

2.11链表的头删

2.12链表的插入【pos之前】

2.13链表的删除 

2.14链表的销毁

 三、双向链表完整代码（含测试模块）

3.1 List.h

3.2 List.c

3.3 text.c

四、结语

一、前言

        在笔者的前两篇文章具体讲解的单链表的实现，即无头单向非循环。但是除此之外，链表还有另外七种类型，本篇文章将主要介绍双向链表的实现，即带头双向链表。相信有的小伙伴一定会问那另外六种需不需要讲解呢，要不要掌握呢？其实，条条大路通罗马，在掌握的单链表和双链表这两大基础链表，其他的链表的实现和运用也是轻而易举，毫不费力。

        因此，就让我们一起实现双向链表叭！

       

二、正文——双向链表的实现

2.1模块化

         相信看过博主前几篇文章的小伙伴对“模块化”已经熟悉的不能再熟悉了，为了后期代码的修改和维护能够更加简便，我们这次双向链表的实现依旧采取模块化的方式。本次的程序共分为3个文件，分别是：List.c[具体功能的实现]、List.h[[函数、变量的声明]]、Text.c[测试部分]。

2.2 数据类型与结构体定义

        在进行链表功能的实现之前，首先是要对数据类型进行定义和结构体定义。

        数据类型采取的是整形的形式，与前文的单链表相同。

        结构体定义这一块则与单链表的定义有所不同。由于单链表是单向链表，故每个结点只需存放下一个结点的地址，而无需存放上一个结点的地址。而双向链表，顾名思义是双向的，通过一个结点我们能够找到它的上一个结点和下一个结点。因此在对结构体进行定义的时候我们就需要两个结构体指针，分别用于存放该结点的上下结点。

        具体代码实现如下：

  1. //数据类型与结构体定义
  2. typedef int LTDataType;
  3. typedef struct ListNode
  4. {
  5. struct ListNode* next;    //存放下一个结点
  6. struct ListNode* prev;    //存放上一个结点
  7. LTDataType data;          //数据类型  
  8. }LTNode;

 2.3链表的初始化

        在进行完数据类型和结构体定义，还需要做一些准备工作，来帮助我们更好的实现和测试后续的链表功能。而准备工作大致分为以下几点：链表的初始化，链表的打印，链表的查找，判断链表是否只有哨兵卫，申请新的结点。

        我们先从链表的初始化开始吧。首先毫无疑问的是先建立的链表的哨兵卫，为了表现链表双向的特性，接下来我们还要将哨兵卫的上下结点指向它本身。

        具体代码如下：

  1. //链表初始化
  2. LTNode* LTInit();
  3.  
  4. //链表初始化
  5. LTNode* LTInit()
  6. {
  7. LTNode* phead =BuyListNode(-1);
  8. phead->next = phead;    //下一个结点指向本身
  9. phead->prev = phead;    //上一个结点指向本身
  10. return phead;
  11. }

 2.4链表的打印

        链表的打印是为了更好的测试我们后续的插入、删除是否完成。那么该如何实现链表的打印呢？

        双向链表的打印与单链表也是有所不同的。对于单链表的打印，我们只需从从头指针开始遍历链表，直至为空。而对于双向链表来说，遍历链表是不可行的，这是由它的结构决定的。双向链表的链接是循环的，单凭遍历的话，是永远也不可能将这个链表打印结束的，因此我们就需要做一点小小的改变，让遍历链表的指针【cur】从哨兵卫的下一个结点开始遍历，直至遍历到哨兵卫停止，这样就可以将链表的数据全部打印出来了。

        具体代码如下：

  1. //链表的打印[声明]
  2. void LTPrint(LTNode* phead);
  3.  
  4. //链表的打印[具体实现]
  5. void LTPrint(LTNode* phead)
  6. {
  7. assert(phead);
  8. LTNode* cur = phead->next;
  9. while (cur != phead)
  10. {
  11. if (cur->next == phead)
  12. {
  13. printf("<->%d<->", cur->data);
  14. }
  15. else
  16. {
  17. printf("<->%d", cur->data);
  18. }
  19. cur = cur->next;
  20. }
  21. printf("\n");
  22. }

2.5 链表的查找

        为了后续链表指定位置的插入和删除，我们需要找到指定数据所指向的结点，为了提高代码的复用，我们将链表的查找单独封装成一个函数。

        那么该如何去编写呢？这里的代码其实与单向链表差不多，即遍历链表，直至找到数据所对应的结点，并将其地址返回即可。相对而言还是很简单的。

        具体代码实现如下：

  1. //链表的查找[声明]
  2. LTNode* LTFind(LTNode* phead, LTDataType x);
  3.  
  4. //链表的查找[实现]
  5. LTNode* LTFind(LTNode* phead, LTDataType x)
  6. {
  7. assert(phead);
  8. LTNode* cur = phead->next;
  9. while (cur != phead)
  10. {
  11. if (cur->data == x)
  12. {
  13. return cur;
  14. }
  15. cur = cur->next;
  16. }
  17. return NULL;
  18. }

 2.6判断链表是否只有哨兵卫

        这一部分是为了链表的删除的准备的，对于单链表而言，当链表为空的时候，就不能进行数据的删除了，而对于双向链表来说，有了哨兵卫的存在，自然就不存在链表为空的情况，相应的，就是当双向链表只存在哨兵卫的时候，就不能进行数据的删除了。

        那么如何判断链表是否只有哨兵卫呢？方法其实很简单，只需要判断所给的头指针的上下结点是否指向本身即可，当然两条件选其一即可。

        具体代码实现如下：

  1. //判断链表是否只有哨兵卫[声明]
  2. bool LTEmpty(LTNode* phead);
  3.  
  4. //判断链表是否只有哨兵卫[实现]
  5. bool LTEmpty(LTNode* phead)
  6. {
  7. assert(phead);
  8. return phead->next == phead;
  9. }
  10.

2.7申请新的结点 

        这一部分主要是为了链表的插入而准备的，无论是头插、尾插还是指定位置的插入都需要申请新的结点，而重复的书写未免使代码显得冗杂，因此将“申请新的结点”这一功能单独分离出来并封装成一个函数，大大提高代码的简洁性。

        而这一功能的实现与单链表大同小异，都是使用内存函数来向内存申请一片空间并返回指向这片空间的指针，不同的只是结构体的内容发生了改变而已。

        具体代码如下：

  1. //申请新的结点[声明]
  2. LTNode* BuyListNode(LTDataType x);
  3.  
  4. /申请新的结点[实现]
  5. LTNode* BuyListNode(LTDataType x)
  6. {
  7. LTNode* newnode = malloc(sizeof(LTNode));
  8. if (newnode == NULL)
  9. {
  10. perror("malloc error");
  11. }
  12. else
  13. {
  14. newnode->data = x;
  15. //避免野指针
  16. newnode->next = NULL;
  17. newnode->prev = NULL;
  18. return newnode;
  19. }
  20. }

2.8 链表的尾插

        准备工作准备就绪后，就开始链表的主要功能的实现啦。

        首先就是链表的尾插。我们先来看看单链表是如何进行尾插的，对于单链表，我们需要对单链表进行遍历找到最后一个结点，再对这个结点和新结点进行链接的操作。而对于双向链表，就没有这么复杂了，因为哨兵卫的上一个结点就已经指向了链表的最后一个结点，在找到这个尾结点之后，剩下的就是链接的问题了。相比于单链表要复杂一点，要将哨兵卫、尾结点、新结点这三个结点进行链接。

        具体链接和代码如下：

  1. //链表的尾插[声明]
  2. void LTPushBack(LTNode* phead, LTDataType x);
  3.  
  4. //链表的尾插[实现]
  5. void LTPushBack(LTNode* phead, LTDataType x)
  6. {
  7. assert(phead);
  8. LTNode* tail = phead->prev;
  9. //创建新的结点
  10. LTNode* newnode = BuyListNode(x);
  11. //尾结点的链接
  12. tail->next = newnode;
  13. newnode->prev = tail;
  14. //哨兵卫的链接
  15. phead->prev = newnode;
  16. newnode->next = phead;
  17. }

 2.9链表的尾删

         在讲解完链表的尾插，接着就是链表的尾删了。同样地，我们不需要对链表进行遍历来找到尾结点，只需要通过哨兵卫来找到最后一个结点，并将其置空，再将倒数第二个结点和哨兵卫进行链接。不

        具体图片和代码如下：

  1. //链表的尾删
  2. void LTPopBack(LTNode* phead);
  3.  
  4. //链表的尾删
  5. void LTPopBack(LTNode* phead)
  6. {
  7. assert(phead);
  8. //判断是否只有哨兵卫
  9. assert(!LTEmpty(phead));
  10. //改变哨兵卫的链接
  11. phead->prev = phead->prev->prev;
  12. //释放尾结点的内存
  13. free(phead->prev->next);
  14. //改变尾部链接
  15. phead->prev->next = phead;
  16. }

 2.10链表的头插

        在尾插、尾删之后，就是头插、头删了,那么该如何实现链表的头插呢。

        其步骤也很简单，先是申请一个新的结点，进而将该结点与哨兵卫与链表的头结点进行链接。需要注意的一点就是判断链表是否只有哨兵卫，若是只有哨兵卫就无须删除了。 

        具体图片和代码如下：

  1. //链表的头插[声明]
  2. void LTPushFront(LTNode* phead, LTDataType x);
  3.  
  4. //链表的头插[实现]
  5. void LTPushFront(LTNode* phead, LTDataType x)
  6. {
  7. //创建新的结点
  8. LTNode* newnode = BuyListNode(x);
  9. LTNode* first = phead->next;
  10. //改变链接关系
  11. newnode->next = first;
  12. first->prev = newnode;
  13. phead->next = newnode;
  14. newnode->prev = phead;
  15. //代码复用
  16. //LTInsert(phead->next, x);
  17. }

2.11链表的头删

        头插之后便是头删了，这一部分的代码也是相对简单的，主要思路是将哨兵卫与头结点的下一个结点链接，并将头结点的内存释放。唯一需要注意的一点就是判断链表是否只有哨兵卫，若是只有哨兵卫就无须删除了。 

  1. //链表的头删[声明]
  2. void LTPopFront(LTNode* phead);
  3.  
  4. //链表的头删[实现]
  5. void LTPopFront(LTNode* phead)
  6. {
  7. assert(phead);
  8. //改变链接关系+释放内存
  9. phead->next = phead->next->next;
  10. free(phead->next->prev);
  11. phead->next->prev = phead;
  12. }

2.12链表的插入【pos之前】

        链表的头插、头删、尾插、尾删已经全部讲解完毕了，但其实对于双向链表来说，以上四个功能并不需要，只需要通过链表的插入和删除便可以实现，也就是代码的复用。但是为了帮助小伙伴们更好的理解双向链表，便将上述功能一一实现。

        接下来就让我们进入“”链表的插入“”这一功能的实现，我们采取的是在"pos"之前进行数据的插入。对“pos”之后插入数据的感兴趣的小伙伴也可以尝试自己编写，两者的逻辑是类似的。

        具体的实现逻辑呢，就是申请一个新的结点，并将pos位置的结点、pos位置之前的结点和新结点进行链接。不过需要注意的一点是，如果你用的的指针过少，便要注意链接的顺序，若是链接顺序便可能无法找到原来结点的数据，比较保险且快捷的方法就是再另外设置一个指针用来记录链接的结点，便可以毫无顾虑的进行结点间的链接了。

注：在尾插的代码中对该段代码的复用有些独特，是通过传哨兵卫的指针进行插入，这是由于双向链表的循环特性决定的，链表的最后一个结点就是哨兵卫的前一个结点。

  1. //链表的插入(前)[声明]
  2. void LTInsert(LTNode* pos, LTDataType x);
  3.  
  4. //链表的插入(前)[实现]
  5. void LTInsert(LTNode* pos, LTDataType x)
  6. {
  7. assert(pos);
  8. LTNode* newnode = BuyListNode(x);
  9. LTNode* prev = pos->prev;
  10. //改变链接关系
  11. prev->next = newnode;
  12. newnode->prev = prev;
  13. newnode->next = pos;
  14. pos->prev = newnode;
  15. }

2.13链表的删除 

         链表的删除的实现逻辑大致就是将要删除的结点置空，并将其前后两个结点进行链接即可。不过要注意的依旧是链表是否只含有哨兵卫，若只含有哨兵卫，就无需进行链表的删除。

  1. //链表的删除[声明]
  2. void LTErase(LTNode* pos);
  3.  
  4. //链表的删除[实现]
  5. void LTErase(LTNode* pos)
  6. {
  7. assert(pos);
  8. LTNode* next = pos->next;
  9. LTNode* prev = pos->prev;
  10. //改变链接关系并释放内存
  11. prev->next = next;
  12. next->prev = prev;
  13. free(pos);
  14. }

2.14链表的销毁

        不知不觉之中，就来到了双向链表的最后一个功能：链表的销毁

        其实现逻辑：从哨兵卫的下一个结点开始遍历链表，边遍历边销毁，直至遍历到哨兵卫为止，最后将哨兵卫的内存销毁并将指针置空。

  1. //链表的销毁[声明]
  2. void LTDestroy(LTNode* phead);
  3.  
  4. //链表的销毁[实现]
  5. void LTDestroy(LTNode* phead)
  6. {
  7. assert(phead);
  8. LTNode* cur = phead->next;
  9. while (cur != phead)
  10. {
  11. LTNode* next = cur->next;
  12. free(cur);
  13. cur = next;
  14. }
  15. free(phead);
  16. phead = cur=NULL;
  17. }

 三、双向链表完整代码（含测试模块）

3.1 List.h

  1. #include<stdlib.h>
  2. #include<assert.h>
  3. #include<stdio.h>
  4. #include<stdbool.h>
  5.  
  6. //数据类型与结构体定义
  7. typedef int LTDataType;
  8. typedef struct ListNode
  9. {
  10. struct ListNode* next;//存放下一个结点
  11. struct ListNode* prev;//存放上一个结点
  12. LTDataType data;//数据类型 
  13. }LTNode;
  14.  
  15. //申请新的结点
  16. LTNode* BuyListNode(LTDataType x);
  17. //链表初始化
  18. LTNode* LTInit();
  19. //链表的打印
  20. void LTPrint(LTNode* phead);
  21. //判断链表是否只有哨兵卫
  22. bool LTEmpty(LTNode* phead);
  23. //链表的查找
  24. LTNode* LTFind(LTNode* phead, LTDataType x);
  25. //链表的尾插
  26. void LTPushBack(LTNode* phead, LTDataType x);
  27. //链表的尾删
  28. void LTPopBack(LTNode* phead);
  29. //链表的头插
  30. void LTPushFront(LTNode* phead, LTDataType x);
  31. //链表的头删
  32. void LTPopFront(LTNode* phead);
  33. //链表的插入(前)
  34. void LTInsert(LTNode* pos, LTDataType x);
  35. //链表的删除
  36. void LTErase(LTNode* pos);
  37. //链表的销毁
  38. void LTDestroy(LTNode* phead);
  39.

3.2 List.c

  1. #include "List.h"
  2.  
  3.  
  4. //申请新的结点
  5. LTNode* BuyListNode(LTDataType x)
  6. {
  7. LTNode* newnode = malloc(sizeof(LTNode));
  8. if (newnode == NULL)
  9. {
  10. perror("malloc error");
  11. }
  12. else
  13. {
  14. newnode->data = x;
  15. //避免野指针
  16. newnode->next = NULL;
  17. newnode->prev = NULL;
  18. return newnode;
  19. }
  20. }
  21. //链表初始化
  22. LTNode* LTInit()
  23. {
  24. LTNode* phead =BuyListNode(-1);
  25. phead->next = phead;//下一个结点指向本身
  26. phead->prev = phead;//上一个结点指向本身
  27. return phead;
  28. }
  29.  
  30. //判断链表是否只有哨兵卫
  31. bool LTEmpty(LTNode* phead)
  32. {
  33. assert(phead);
  34. return phead->next == phead;
  35. }
  36.  
  37. //链表的查找
  38. LTNode* LTFind(LTNode* phead, LTDataType x)
  39. {
  40. assert(phead);
  41. LTNode* cur = phead->next;
  42. while (cur != phead)
  43. {
  44. if (cur->data == x)
  45. {
  46. return cur;
  47. }
  48. cur = cur->next;
  49. }
  50. return NULL;
  51. }
  52.  
  53.  
  54. //链表的打印
  55. void LTPrint(LTNode* phead)
  56. {
  57. assert(phead);
  58. LTNode* cur = phead->next;
  59. while (cur != phead)
  60. {
  61. if (cur->next == phead)
  62. {
  63. printf("<->%d<->", cur->data);
  64. }
  65. else
  66. {
  67. printf("<->%d", cur->data);
  68. }
  69. cur = cur->next;
  70. }
  71. printf("\n");
  72. }
  73.  
  74. //链表的尾插
  75. void LTPushBack(LTNode* phead, LTDataType x)
  76. {
  77. assert(phead);
  78. LTNode* tail = phead->prev;
  79. //创建新的结点
  80. LTNode* newnode = BuyListNode(x);
  81. //尾结点的链接
  82. tail->next = newnode;
  83. newnode->prev = tail;
  84. //哨兵卫的链接
  85. phead->prev = newnode;
  86. newnode->next = phead;
  87. //代码复用
  88. //LTInsert(phead, x);
  89. }
  90.  
  91.  
  92.  
  93. //链表的尾删
  94. void LTPopBack(LTNode* phead)
  95. {
  96. assert(phead);
  97. //判断是否只有哨兵卫
  98. assert(!LTEmpty(phead));
  99. //改变哨兵卫的链接
  100. phead->prev = phead->prev->prev;
  101. //释放尾结点的内存
  102. free(phead->prev->next);
  103. //改变尾部链接
  104. phead->prev->next = phead;
  105. //代码复用
  106. //LTErase(phead->prev);
  107. }
  108.  
  109. //链表的头插
  110. void LTPushFront(LTNode* phead, LTDataType x)
  111. {
  112. //创建新的结点
  113. LTNode* newnode = BuyListNode(x);
  114. LTNode* first = phead->next;
  115. //改变链接关系
  116. newnode->next = first;
  117. first->prev = newnode;
  118. phead->next = newnode;
  119. newnode->prev = phead;
  120. //代码复用
  121. //LTInsert(phead->next, x);
  122. }
  123.  
  124. //链表的头删
  125. void LTPopFront(LTNode* phead)
  126. {
  127. assert(phead);
  128. //改变链接关系+释放内存
  129. phead->next = phead->next->next;
  130. free(phead->next->prev);
  131. phead->next->prev = phead;
  132. //代码复用
  133. //LTErase(phead->next);
  134.  
  135. }
  136.  
  137. //链表的插入(前)
  138. void LTInsert(LTNode* pos, LTDataType x)
  139. {
  140. assert(pos);
  141. LTNode* newnode = BuyListNode(x);
  142. LTNode* prev = pos->prev;
  143. //改变链接关系
  144. prev->next = newnode;
  145. newnode->prev = prev;
  146. newnode->next = pos;
  147. pos->prev = newnode;
  148. }
  149.  
  150. //链表的删除
  151. void LTErase(LTNode* pos)
  152. {
  153. assert(pos);
  154. LTNode* next = pos->next;
  155. LTNode* prev = pos->prev;
  156. //改变链接关系并释放内存
  157. prev->next = next;
  158. next->prev = prev;
  159. free(pos);
  160. }
  161.  
  162. //链表的销毁
  163. void LTDestroy(LTNode* phead)
  164. {
  165. assert(phead);
  166. LTNode* cur = phead->next;
  167. while (cur != phead)
  168. {
  169. LTNode* next = cur->next;
  170. free(cur);
  171. cur = next;
  172. }
  173. free(phead);
  174. phead = cur=NULL;
  175. }

3.3 text.c

  1. #include "List.h"
  2.  
  3. //测试代码1：尾插
  4. text1()
  5. {
  6. LTNode* phead = LTInit();
  7. LTPushBack(phead, 1);
  8. LTPushBack(phead, 2);
  9. LTPushBack(phead, 3);
  10. LTPushBack(phead, 4);
  11. LTPrint(phead);
  12. }
  13.  
  14. //测试代码2：尾删
  15. text2()
  16. {
  17. LTNode* phead = LTInit();
  18. LTPushBack(phead, 1);
  19. LTPushBack(phead, 2);
  20. LTPushBack(phead, 3);
  21. LTPushBack(phead, 4);
  22. LTPrint(phead);
  23. printf("\n");
  24. LTPopBack(phead);
  25. LTPopBack(phead);
  26. LTPrint(phead);
  27. }
  28.  
  29.  
  30. //测试代码3：头插
  31. text3()
  32. {
  33. LTNode* phead = LTInit();
  34. LTPushFront(phead, 4);
  35. LTPushFront(phead, 3);
  36. LTPushFront(phead, 2);
  37. LTPushFront(phead, 1);
  38. LTPrint(phead);
  39. }
  40.  
  41.  
  42. //测试代码4：头删
  43. text4()
  44. {
  45. LTNode* phead = LTInit();
  46. LTPushFront(phead, 4);
  47. LTPushFront(phead, 3);
  48. LTPushFront(phead, 2);
  49. LTPushFront(phead, 1);
  50. LTPopFront(phead);
  51. LTPopFront(phead);
  52. LTPrint(phead);
  53. }
  54.  
  55.  
  56. //测试代码5：插入(前)
  57. text5()
  58. {
  59. LTNode* phead = LTInit();
  60. LTPushFront(phead, 4);
  61. LTPushFront(phead, 2);
  62. LTPushFront(phead, 1);
  63. LTPrint(phead);
  64. LTNode* pos=LTFind( phead,4);
  65. LTInsert(pos, 3);
  66. LTPrint(phead);
  67. }
  68. //测试代码6：插入(前)
  69. text6()
  70. {
  71. LTNode* phead = LTInit();
  72. LTPushFront(phead, 4);
  73. LTPushFront(phead, 2);
  74. LTPushFront(phead, 1);
  75. LTPrint(phead);
  76. LTNode* pos = LTFind(phead, 4);
  77. LTInsert(pos, 3);
  78. LTPrint(phead);
  79. }
  80.  
  81. //测试代码7：删除
  82. text7()
  83. {
  84. LTNode* phead = LTInit();
  85. LTPushFront(phead, 4);
  86. LTPushFront(phead, 3);
  87. LTPushFront(phead, 2);
  88. LTPushFront(phead, 1);
  89. LTPrint(phead);
  90. LTNode* pos = LTFind(phead, 3);
  91. LTErase(pos);
  92. LTPrint(phead);
  93. }
  94. int main()
  95. {
  96. //text1();
  97. //text2();
  98. //text3();
  99. //text4();
  100. //text5();
  101. //text6();
  102. text7();
  103. }

四、结语

        至此为止，关于双向链表的讲解已经全部结束，看到这里的小伙伴快给自己点个赞，希望你们能够从本篇文章中有所收获，就是对笔者最大的支持！

        关注我 _麦麦_分享更多干货：_麦麦_的博客_CSDN博客-领域博主
        大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！

  

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览40346 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪