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

【数据结构】双向链表

2023-07-03

void next prev
前面我们已经学完了单向链表，知道了单向链表如何进行增删查改等基本功能，而今天，我们将要学习双向链表。目录1.链表的分类2.双向链表定义3.双向链表接口的实现所有接口函数一览创建返回链表头节点初始化链表双向链表打印双向链表尾插双向链表尾删双向链表头插双向链表头删双向链表在pos的前面进行插入双向链表删

前面我们已经学完了单向链表，知道了单向链表如何进行增删查改等基本功能，而今天，我们将要学习双向链表。

目录

1.链表的分类

2.双向链表定义

3.双向链表接口的实现

所有接口函数一览

创建返回链表头节点

初始化链表

双向链表打印

双向链表尾插

双向链表尾删

双向链表头插

双向链表头删

双向链表在pos的前面进行插入

双向链表删除pos位置的节点

求双向链表长度

双向链表销毁

4.完整代码

回忆上次学习的单向链表结构图：

 下面还要详细的介绍一下各种链表示意图，上期遗漏了这部分内容

1.链表的分类

1. 单向或者双向

 2. 带头或者不带头

 3. 循环或者非循环

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

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。

由于上期我们已经学完了无头单向非循环链表，因此这期我们来学习带头双向循环链表。

2.双向链表定义

和单向链表一样，双向链表每个节点都是由结构体组成的数据类型，但是双向链表结构体中增加了一个指向前一个节点的指针。

  1. typedef int LTDataType; //方便修改数据类型
  2.  
  3. typedef struct ListNode
  4. {
  5. struct ListNode* next;//指向下一个节点的指针
  6. struct ListNode* prev;//指向前一个节点的指针
  7. LTDataType data; //存储的数据
  8. }LTNode;

我们今天要将的是带哨兵卫头节点的双向循环链表，它的头节点不存储有效数据，头节点中的prev指针指向最后一个节点

 当链表为空时，指针的指向关系图：

3.双向链表接口的实现

所有接口函数一览

下面是双向链表中经常要用到的一些接口函数：

  1. //初始化
  2. LTNode* ListInit();
  3. //打印
  4. void printList(LTNode* phead);
  5. //尾插
  6. void ListPushBack(LTNode* phead, LTDataType x);
  7. //头插
  8. void ListPushFront(LTNode* phead, LTDataType x);
  9. //尾删
  10. void ListPopBack(LTNode* phead);
  11. //头删
  12. void ListPopFront(LTNode* phead);
  13. //判断链表是否为空
  14. bool ListEmpty(LTNode* phead);
  15. //在pos位置前插入x
  16. void ListInsert(LTNode* pos, LTDataType x);
  17. //删除pos位置节点
  18. void ListErase(LTNode* pos);
  19. //求链表长度
  20. int ListSize(LTNode* phead);
  21. //销毁
  22. void ListDestory(LTNode* phead);

创建返回链表头节点

函数使用malloc动态分配了一个 LTNode类型的内存空间，用node进行接收。同时要检查内存分配是否成功，将新节点中的data赋值为传入的数据x，将新节点的next和prev指针都设置为NULL,最后返回新节点的地址。

  1. //创建新节点
  2. LTNode* BuyListNode(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. return node;
  14. }

初始化链表

初始化链表就是给链表创建一个头节点，这里需要使用到上面介绍完的创建新节点BuyListNode函数，因为头节点不存储有效数据，所以我们将data赋值为-1，同时头节点中的next和prev都指向自己，最后返回头节点的地址。

  1. LTNode* ListInit()
  2. {
  3. LTNode* phead = BuyListNode(-1);
  4. phead->next = phead;
  5. phead->prev = phead;
  6. return phead;
  7. }

双向链表打印

双向链表的打印和单向链表类似，注意循环的截止条件不是cur为空，而当当cur重新指向头节点的时候停止循环。因为最后一个节点的next指针指向的是头节点。

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

 

双向链表尾插

普通的方法是创建一个新的节点插入到链表的尾部，当然还有更为简单的方法，就是调用一下我们后面要讲到的 ListInsert 函数，这个函数可以在指定位置前插入一个节点并存储有效数据。如果这个指定位置是头节点的位置，那么头节点的前一个位置就是链表最后一个节点所在的位置。

下面介绍一下普通的方法吧：

 将最后一个节点命名为tail，然后根据上图修改一下phead ， tail ， newNode之间的指向关系即可

  1. //尾插
  2. void ListPushBack(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);
  5.  
  6. /*
  7. //可以直接调用void ListInsert来实现
  8. ListInsert(phead , x);
  9. //代码复用
  10. */
  11.  
  12. LTNode* newNode = BuyListNode(x);
  13. LTNode* tail = phead->prev;
  14. newNode->next = phead;
  15. newNode->prev = tail;
  16. tail->next = newNode;
  17. phead->prev = newNode;
  18. }

 

双向链表尾删

这里也可以使用两种方法来实现，普通方法是找到最后一个节点，修改指向关系，再释放掉最后一个节点的空间。简单的方法是调用一个可以删除指定位置节点的函数ListErase，将最后一个节点的位置传入到这个函数就可以进行尾删，（最后一个节点的位置是phead->prev）这个函数下面也将会给大家介绍到。

普通方法：

 将最后一个节点命名为tail，倒数第二个节点命名为tailPrev，按上图修改它们的指向关系即可。

为了防止出现尾删空链表的情况出现，我们需要使用一个ListEmpty函数来判断链表是否为空，同时使用assert断言，一旦链表为空，用户仍然使用尾删程序就会报错。头删同理如此。

  1. //尾删
  2. void ListPopBack(LTNode* phead)
  3. {
  4. assert(phead);
  5. assert(ListEmpty(phead));
  6.  
  7. /*
  8. //可以复用ListErase函数来实现后面的代码
  9. ListErase(phead->prev);
  10. */
  12.  
  13. LTNode* tail = phead->prev;
  14. LTNode* tailPrev = tail->prev;
  15. phead->prev = tailPrev;
  16. tailPrev->next = phead;
  17.  
  18. free(tail);
  19. }

双向链表头插

这里也可使用两种方法，我们介绍一下普通的方法：

 将头节点的后一个节点命名为pheadNext，然后将newNode插入到phead和pheadNext之间即可。

  1. //头插
  2. void ListPushFront(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);
  5.  
  6. /*
  7. //可以直接调用void ListInsert来实现
  8. ListInsert(phead->next , x);
  9. //代码复用
  10. */
  11.  
  12. LTNode* newNode = BuyListNode(x);
  13. LTNode* pheadNext = phead->next;
  14. phead->next = newNode;
  15. newNode->prev = phead;
  16. newNode->next = pheadNext;
  17. pheadNext->prev = newNode;
  18. }

双向链表头删

这里也可使用两种方法，我们介绍一下普通的方法：

  1. //头删
  2. void ListPopFront(LTNode* phead)
  3. {
  4. assert(phead);
  5. assert(ListEmpty(phead));
  6.  
  7. /*
  8. //可以复用ListErase函数来实现后面的代码
  9. ListErase(phead->next);
  10. */
  11.  
  12. LTNode* next = phead->next;
  13. phead->next = next->next;
  14. next->next->prev = phead;
  15.  
  16. free(next);
  17. }

双向链表在pos的前面进行插入

直接将pos的前一个节点命名为prev，再将newNode插入。

  1. //在pos位置前插入x
  2. void ListInsert(LTNode* pos, LTDataType x)
  3. {
  4. assert(pos);
  5.  
  6. LTNode* prev = pos->prev;
  7. LTNode* newNode = BuyListNode(x);
  8.  
  9. prev->next = newNode;
  10. newNode->prev = prev;
  11. newNode->next = pos;
  12. pos->prev = newNode;
  13. }

双向链表删除pos位置的节点

将pos前一个节点命名为prev,后一个节点命名为next,这样命名方便我们修改指针的指向。然后按照上图修改指针即可。

  1. //删除pos位置节点
  2. void ListErase(LTNode* pos)
  3. {
  4. assert(pos);
  5. LTNode* prev = pos->prev;
  6. LTNode* next = pos->next;
  7.  
  8. prev->next = next;
  9. next->prev = prev;
  10. free(pos);
  11. }

求双向链表长度

这里使用的方法是遍历整个链表。

  1. //求链表长度
  2. int ListSize(LTNode* phead)
  3. {
  4. assert(phead);
  5. LTNode* cur = phead->next;
  6. int size = 0;
  7. while (cur != phead)
  8. {
  9. ++size;
  10. cur = cur->next;
  11. }
  12. return size;
  13. }

双向链表销毁

这一步可以复用删除pos位置节点的函数ListErase，我们只要将链表的每一个节点地址都传入到这个函数，就可销毁链表。当然，最后也要将头节点给释放销毁。

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

4.顺序表和链表的区别

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

顺序表优点：下标随机访问，cpu高速缓存命中率高

顺序表缺点：头部或者中间插入删除效率低，扩容有一定程度性能消耗，可能存在一定程度空间浪费。

链表优点：任意位置插入删除O(1)复杂度，按需申请释放。

链表缺点：不支持下标随机访问。

5.完整代码

头文件： 存放函数声明部分

  1. #pragma once
  2.  
  3. #include<stdio.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6. #include<stdlib.h>
  7.  
  8. typedef int LTDataType; //方便修改数据类型
  9.  
  10. typedef struct ListNode
  11. {
  12. struct ListNode* next;//指向下一个节点的指针
  13. struct ListNode* prev;//指向前一个节点的指针
  14. LTDataType data; //存储的数据
  15. }LTNode;
  16.  
  17. //初始化
  18. LTNode* ListInit();
  19. //打印
  20. void printList(LTNode* phead);
  21. //尾插
  22. void ListPushBack(LTNode* phead, LTDataType x);
  23. //头插
  24. void ListPushFront(LTNode* phead, LTDataType x);
  25. //尾删
  26. void ListPopBack(LTNode* phead);
  27. //头删
  28. void ListPopFront(LTNode* phead);
  29. //判断链表是否为空
  30. bool ListEmpty(LTNode* phead);
  31. //在pos位置前插入x
  32. void ListInsert(LTNode* pos, LTDataType x);
  33. //删除pos位置节点
  34. void ListErase(LTNode* pos);
  35. //求链表长度
  36. int ListSize(LTNode* phead);
  37. //销毁
  38. void ListDestory(LTNode* phead);

List.c文件  存放函数定义

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2.  
  3. #include"List.h"
  4.  
  5. //创建新节点
  6. LTNode* BuyListNode(LTDataType x)
  7. {
  8. LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  9. if (node == NULL)
  10. {
  11. perror("malloc fail");
  12. exit(-1);
  13. }
  14. node->data = x;
  15. node->next = NULL;
  16. node->prev = NULL;
  17. return node;
  18. }
  19.  
  20. //初始化
  21. LTNode* ListInit()
  22. {
  23. LTNode* phead = BuyListNode(-1);
  24. phead->next = phead;
  25. phead->prev = phead;
  26. return phead;
  27. }
  28.  
  29. //判断链表是否为空
  30. bool ListEmpty(LTNode* phead)
  31. {
  32. assert(phead);
  33. return phead->next != phead;
  34. }
  35.  
  36. //打印
  37. void printList(LTNode* phead)
  38. {
  39. LTNode* cur = phead->next;
  40. while (cur != phead)
  41. {
  42. printf("%d->", cur->data);
  43. cur = cur->next;
  44. }
  45. printf("NULL\n");
  46. }
  47.  
  48. //尾插
  49. void ListPushBack(LTNode* phead, LTDataType x)
  50. {
  51. assert(phead);
  52.  
  53. /*
  54. //可以直接调用void ListInsert来实现
  55. ListInsert(phead , x);
  56. //代码复用
  57. */
  58.  
  59. LTNode* newNode = BuyListNode(x);
  60. LTNode* tail = phead->prev;
  61. newNode->next = phead;
  62. newNode->prev = tail;
  63. tail->next = newNode;
  64. phead->prev = newNode;
  65. }
  66.  
  67. //头插
  68. void ListPushFront(LTNode* phead, LTDataType x)
  69. {
  70. assert(phead);
  71.  
  72. /*
  73. //可以直接调用void ListInsert来实现
  74. ListInsert(phead->next , x);
  75. //代码复用
  76. */
  77.  
  78. LTNode* newNode = BuyListNode(x);
  79. LTNode* pheadNext = phead->next;
  80. phead->next = newNode;
  81. newNode->prev = phead;
  82. newNode->next = pheadNext;
  83. pheadNext->prev = newNode;
  84. }
  85.  
  86. //尾删
  87. void ListPopBack(LTNode* phead)
  88. {
  89. assert(phead);
  90. assert(ListEmpty(phead));
  91.  
  92. /*
  93. //可以复用ListErase函数来实现后面的代码
  94. ListErase(phead->prev);
  95. */
  97.  
  98. LTNode* tail = phead->prev;
  99. LTNode* tailPrev = tail->prev;
  100. phead->prev = tailPrev;
  101. tailPrev->next = phead;
  102.  
  103. free(tail);
  104. }
  105.  
  106. //头删
  107. void ListPopFront(LTNode* phead)
  108. {
  109. assert(phead);
  110. assert(ListEmpty(phead));
  111.  
  112. /*
  113. //可以复用ListErase函数来实现后面的代码
  114. ListErase(phead->next);
  115. */
  116.  
  117. LTNode* next = phead->next;
  118. phead->next = next->next;
  119. next->next->prev = phead;
  120.  
  121. free(next);
  122. }
  123.  
  124. //在pos位置前插入x
  125. void ListInsert(LTNode* pos, LTDataType x)
  126. {
  127. assert(pos);
  128.  
  129. LTNode* prev = pos->prev;
  130. LTNode* newNode = BuyListNode(x);
  131.  
  132. prev->next = newNode;
  133. newNode->prev = prev;
  134. newNode->next = pos;
  135. pos->prev = newNode;
  136. }
  137.  
  138. //删除pos位置节点
  139. void ListErase(LTNode* pos)
  140. {
  141. assert(pos);
  142. LTNode* prev = pos->prev;
  143. LTNode* next = pos->next;
  144.  
  145. prev->next = next;
  146. next->prev = prev;
  147. free(pos);
  148. }
  149.  
  150. //求链表长度
  151. int ListSize(LTNode* phead)
  152. {
  153. assert(phead);
  154. LTNode* cur = phead->next;
  155. int size = 0;
  156. while (cur != phead)
  157. {
  158. ++size;
  159. cur = cur->next;
  160. }
  161. return size;
  162. }
  164. //销毁
  165. void ListDestory(LTNode* phead)
  166. {
  167. assert(phead);
  168. LTNode* cur = phead->next;
  169. while (cur != phead)
  170. {
  171. LTNode* next = cur->next;
  172. ListErase(cur);
  173. cur = next;
  174. }
  175. free(phead);
  176. }

test.c文件   用于测试接口函数正确性

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2.  
  3. #include"List.h"
  4.  
  5. //尾插测试
  6. void ListTest1()
  7. {
  8. LTNode* plist = ListInit();
  10. ListPushBack(plist, 1);
  11. ListPushBack(plist, 2);
  12. ListPushBack(plist, 3);
  13. ListPushBack(plist, 4);
  14. ListPushBack(plist, 5);
  15.  
  16. printList(plist);
  17.  
  18. }
  19.  
  20. //头插测试
  21. void ListTest2()
  22. {
  23. LTNode* plist = ListInit();
  24.  
  25. ListPushFront(plist, 1);
  26. ListPushFront(plist, 2);
  27. ListPushFront(plist, 3);
  28. ListPushFront(plist, 4);
  29. ListPushFront(plist, 5);
  30.  
  31. printList(plist);
  32.  
  33. }
  34.  
  35. //尾删测试
  36. void ListTest3()
  37. {
  38. LTNode* plist = ListInit();
  39.  
  40. ListPushFront(plist, 1);
  41. ListPushFront(plist, 2);
  42. ListPushFront(plist, 3);
  43. ListPushFront(plist, 4);
  44. ListPushFront(plist, 5);
  45. printList(plist);
  46.  
  47. ListPopBack(plist);
  48. ListPopBack(plist);
  49. ListPopBack(plist);
  50. ListPopBack(plist);
  51.  
  52. printList(plist);
  53. }
  54.  
  55. //头删测试
  56. void ListTest4()
  57. {
  58. LTNode* plist = ListInit();
  59.  
  60. ListPushBack(plist, 1);
  61. ListPushBack(plist, 2);
  62. ListPushBack(plist, 3);
  63. ListPushBack(plist, 4);
  64. ListPushBack(plist, 5);
  65. printList(plist);
  66.  
  67. ListPopFront(plist);
  68. ListPopFront(plist);
  69. ListPopFront(plist);
  70. ListPopFront(plist);
  72. printList(plist);
  73. }
  74.  
  75.  
  76. void ListTest5()
  77. {
  78. LTNode* plist = ListInit();
  79.  
  80. ListPushBack(plist, 1);
  81. ListPushBack(plist, 2);
  82. ListPushBack(plist, 3);
  83. ListPushBack(plist, 4);
  84. ListPushBack(plist, 5);
  85. printList(plist);
  86.  
  87. ListDestory(plist);
  88.  
  89. //printList(plist);
  90. }
  91.  
  92. int main()
  93. {
  94. //ListTest1();
  95. ListTest1();
  96.  
  97. return 0;
  98. }

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