数据结构之双向链表(赋源码)

数据结构之双向链表(源码)

线性表

双向链表是线性表链式存储结构的一种，若对链式存储结构举行分类可以分为八种。

• 带头、不带头：指的是该连链表有无头节点，头节点不存放任何内容，它不愿定是链表必备的元素，而一个链表拥有一个头节点就可以对后续的插入、删除等操作举行统一而不必要判空等环境。
  
• 单向、双向：双向链表与单向链表的区别在于，它多了一个指针用来存放上一个节点的指针，如许就可以通过一个节点恣意的向前、向后遍历。
  
• 循环、不循环：链表的循环结构是将不循环链表的尾节点从指向空指针改为指向头指针。完成链表的自循环。
  

本篇所述：带头双向循环链表，简称双链表，双链表和单链表（不带头单向不循环链表）是八种链表中常用的两个链表，
双向链表

双链表结构

双链表是一个带头双向循环链表，更据它的特性不能想出，在一个双链表的一个节点里它的指针域用来存放前一个节点的所在和存放下一个节点的所在

1. typedef int ListNodeDataType;
2. typedef struct ListNode
3. {
4.         ListNodeDataType data;
5.         struct ListNode* prev;
6.         struct ListNode* next;
7. }ListNode;

复制代码

prev是前驱指针存放前一个节点的所在，next是后继指针存放下一个节点的指针，而双链表是循环链表，尾节点没有下一个节点，它是指向头节点，头节点的prec指针指向尾节点。
功能实现

1. //初始化
2. void ListNodeInit2(ListNode** pphead);
3. ListNode* LTInit();
4. //打印
5. void ListPrint(ListNode* phead);
6. //尾插
7. void ListNodePushBack(ListNode* phead, ListNodeDataType x);
8. //头插
9. void ListNodePushFront(ListNode* phead, ListNodeDataType x);
10. //尾删
11. void ListNodePopBack(ListNode* phead);
12. //头删
13. void ListNodePopFront(ListNode* phead);
14. //查找
15. ListNode* ListNodeFind(ListNode* phead, ListNodeDataType x);
16. //指定位置删除
17. void ListNodeErase(ListNode* pos);
18. //指定位置插入(之后）
19. void ListNodeInsert(ListNode* pos, ListNodeDataType x);
20. //销毁
21. void ListDestory(ListNode* phead);
22. void ListDestory2(ListNode** pphead);

复制代码

创建节点、初始化、打印

创建节点

1. //创建节点
2. ListNode* ListBuyNode(ListNodeDataType x)
3. {
4.         ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
5.         if (newnode == NULL)
6.         {
7.                 perror("malloc :");
8.                 exit(1);
9.         }
10.         newnode->data = x;
11.         newnode->next = newnode;
12.         newnode->prev = newnode;
13. }

复制代码

我们说双链表是由一个一个的节点组成，而节点里存放的有数据，前驱指针用来存放上一个节点的所在和后继指针
用来存放下一个节点的所在，在创建节点时，使用malloc函数开辟空间即可，realloc得当对一块连续存储的空间开辟新的更大的空间，而节点用不是realloc函数，它们在物理空间上不愿定是连续的。
使用malloc函数开辟完空间后别忘了判断是否开辟成功，这是为了养成一个精良的风俗，如今的盘算机想要开辟空间是否，一样平常都是内存被用完了 。
最后，将x值放入节点里，由于它只是一个节点，没有前驱节点，和后继节点，而双向链表是循环链表所以让这两个指针指向自己，实现自循环，而不会去指向空指针。
初始化

1. //初始化
2. ListNode* LTInit()
3. {
4.         ListNode* phead = ListBuyNode(-1);
5.         return phead;
6. }
7. //  初始化
8. void ListNodeInit2(ListNode** pphead)
9. {
10.         *pphead = ListBuyNode(-1);
11. }

复制代码

  初始化头节点，使双链表带头，为了后续插入、删除等操作同意而设置的，数据域一样平常无意义，在链表里不愿定有头节点。
  初始化双链表有两种写法：

• 创建头节点让将其所在返回
  
  
  
  • 不必要传递参数，调用创建节点函数后将开辟的空间返回即可
    
  • 头节点不必要存储有效信息，所以在调用ListBuyNode函数是恣意传递了一个整形变量。
    
  
  
• 将头节点声明后传递它的所在给ListNodeInit2初始化函数，在函数内完成空间的开辟。
  
  
  
  • 必要传递参数，且是二级指针，指向双链表的变量已经是一级指针，想要改变一级指针的内容必须取出其所在，使用二级指针接收。
    
  • 传递的是二级指针在函数内对形参的开辟，影响到了实参，不必要将所在返回。
    
  
  

   再重述一遍，指向双链表的变量是一级指针，也就是头指针它是链表不可缺少的元素，链表里有头节点他就指向头节点，没有头节点它就指向第一个节点。想要对头指针修改，得传递它的所在，才能使函数内对形参的改变影响到实参。而一级指针的所在必要二级指针接收。
  打印

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

复制代码

提前将打印功能的实现，是为了方便后续对双链表，插入数据、删除数据举行更方便的观察，而不是每一次调用插入、删除等函数都使用vs的调试功能。
首先、在打印单链表时，同样使用了循环，创建了一个临时指针来指向第一个节点，打印单链表数据的接收据件是pcur指向空时停止。而双链表是一个循环链表它没有一个节点的指针是指向空的。
所以这里以pcur指向头节点时为循环竣事条件 pcur != phead， 它并不存放有效数据，不用打印它。
在打印时必要从第一个节点开始打印所以pcur指针的起始位置是 ListNode* pcur = phead->next;，通过将pcur的下一个节点的所在赋给它，完成自循环 pcur = pcur->next;。
查找

1. //查找
2. ListNode* ListNodeFind(ListNode* phead, ListNodeDataType x)
3. {
4.         assert(phead);
5.         ListNode* pcur = phead->next;
6.         while (pcur != phead)
7.         {
8.                 if (pcur->data == x)
9.                 {
10.                         return pcur;
11.                 }
12.                 pcur = pcur->next;
13.         }
14.         return NULL;
15. }

复制代码

查找，数据有着比力重要的职位，涉及到了指定位置（之前）插入，和指定位置删除等。
双链表的查找很好理解，想要查找一个元素，只必要将链表里每一个数据一一比力巨细，若两者刚好相称，这就是必要查找的数据，然后将其所在返回即可，若跳出循环后并没有找到对应的数据，返回空指针。
使用assert断言，防止传递的头指针为空，并在函数内对空指针解引用从而引发一系列报错。
循环遍历每一个节点时，并不会查找头节点，将临时指针的起始位置设为第一个节点 ListNode* pcur = phead->next;，在循环内使用if语句举行判断，形参x和pcur内的data巨细是否相称，相称将其所在返回，若不等继承循环判断，出了循环后没有找到，返回空指针即可。
插入

插入函数，传递的都是一级指针，为啥不传递二级指针捏，执行对节点的插入并不会影响到头指针的指向，传递一级指针即可。
插入分为：

• 头插、尾插
  
• 指定位置之前插入、指定位置之后插入
  

在实现节点的插入时实现必要考虑的是，我插入如这个节点会影响到那些节点，该如何选择插入的顺序将影响最小化。
尾插

1. //尾插
2. void ListNodePushBack(ListNode* phead, ListNodeDataType x)
3. {
4.         assert(phead);
5.         ListNode* newnode = ListBuyNode(x);
6.         newnode->next = phead;
7.         newnode->prev = phead->prev;
8.         phead->prev->next = newnode;
9.         phead->prev = newnode;
10. }

复制代码

第一步：使用assert断言判断，头指针是否为空，为空运行步伐就会报错。
第二步：如图，想要在尾节点插入一个新的节点，那就必要创建新的节点调用 ListBuyNode函数。
第三步：首先尾插一个节点会影响到的节点有：phead（头节点）、phead->prev。
以及待插入的newnode新节点，会影响到phead的prev指针、phead->next的next指针，newnode的next、prev指针，
此中影响最小的是新节点newnode的两个指针，先改变它们的指向，让其prev指向最后一个节点，next指向头指针

然后再改变phead->prev指向的节点，也就是尾节点，先改变尾节点是由于提前将尾节点的prev指针改为newnode，那就无法通过头指针找到尾节点了。phead->prev->next = newnode;，这里让尾节点的next指针的指向从头节点改为newnode。
所以先改变头指针之外的节点，然后再改变头指针。
改变头指针里prev的指向，让其指向新的节点，如许就完成了全部节点的改变，成功插入了新的节点。
头插

1. //头插
2. void ListNodePushFront(ListNode* phead, ListNodeDataType x)
3. {
4.         assert(phead);
5.         ListNode* newnode = ListBuyNode(x);
6.         newnode->next = phead->next;
7.         newnode->prev = phead;
8.         phead->next->prev = newnode;
9.         phead->next = newnode;
10. }

复制代码

头插与尾插及其雷同，只是改变了插入如新节点的位置。
第一步：使用assert断言判断，头指针是否为空，为空运行步伐就会报错。
第二步：第二步：如图，想要在尾节点插入一个新的节点，那就必要创建新的节点调用 ListBuyNode函数。
通过代码观察可以发现，再头插和尾插里的第一步和第二步千篇一律，当然指定位置之后插入的逻辑也是一样的。
最主要的区别照旧它们影响的节点不同。对新节点举行头插，主要影响到头节点phead和头节点的下一个节点（第一个节点）phead->next。
有了尾插的经验，插入头节点时。首先改变新节点的next、prev指针的指向让prev指向头节点 newnode->prev = phead;，和next指针指向第一个节点 newnode->next = phead->next;，完成了头节点的改变，接着就改变，第一个节点的prev指针，让它指向newnode，最后改变头节点的next指针让其指向newnode。

指定位置之后插入

1. //指定位置插入(之后）
2. void ListNodeInsert(ListNode* pos, ListNodeDataType x)
3. {
4.         assert(pos);
5.         //pos newnode pos->next
6.         ListNode* newnode = ListBuyNode(x);
7.         newnode->next = pos->next;
8.         newnode->prev = pos;
9.         pos->next->prev = newnode;
10.         pos->next = newnode;
11. }

复制代码

指定位置之后插入，一开始的断言的创建新节点的操作理解是一样的，最主要的区别是，指定位置插入影响的节点不同，而指定位置之后插入的实现，我只能说与头插基本上没有区别，在代码上只是将phead指针改为了pos指针。
首先，在pos之后插入新的节点newnode，它会影响到pos节点，pso->next两个节点，此中必要改变pos的next指针的指向，以及pos->next->prev指针的指向，必要它们指向新的节点newnode，而newnode的next指针必要指向pos的下一个节点，pos->next，和newnode的prev指针必要指向pos节点。如许就完成了对新节点的插入。其逻辑与头插无异。
删除

判空

1. bool ListEmpty(ListNode* phead)
2. {
3.         assert(phead);
4.         return phead->next == phead;
5. }

复制代码

在对删除双链表时有一种特殊环境，就是只有一个头节点，这时双链表被看作是空链表，这与前文实现的单链表不同，单链表是必要将全部节点删除才为空，因为它没有头节点，这才将全部节点删除。
对于这种特殊环境做出了判断，当头节点的next指针指向自己的时候说明双链表里只有一个头节点，此时双链表为空，返回true，双链表不为空的话返回false。
再删除函数里都必要调用这种方法，以免错误的将头节点删除。
使用assert断言，举行判断 assert(!ListEmpty(phead));，若双链表为空返回true，!true，而为假，运行代码时直接报警告。
尾删

1. //尾删
2. void ListNodePopBack(ListNode* phead)
3. {
4.         assert(phead);
5.         assert(!ListEmpty(phead));
6.         //phead phead->prev  phead->prev->prev
7.         ListNode* del = phead->prev;
8.         phead->prev = del->prev;
9.         del->prev->next = phead;
10.         free(del);
11.         del = NULL;
12. }

复制代码

尾删，首先考虑的是删除尾节点会影响到那些节点，而这些节点有必要做出那些改变，改变的顺序。
影响的节点：删除尾节点会影响到头节点 phead，待删除的节点phead->perv，尾节点的前一个节点phead->prev->prev.
为了避免出现过多的结构体访问操作符从而低落代码的可读性，以及方边后续的删除操作，这里将 ListNode* del = phead->prev;
删除节点重定名，也就是del节点。如许 phead->prev->prev，又为 del->prev。

如图必要对del节点举行删除，首先必要改变 del->prev节点的next指针，然后再改变头节点的prev指针，这是为了先将头节点的prev指针修改后而找不到del节点，但不过我们以及提前将del节点保存的所以不用担心它的发生。
接下来就是修改指针的指向了，先修改 del前一个节点的指向del->prev，删除尾节点后他就是新的尾，将它的next指向头节点 del->prev->next = phead;，然后修改头节点的prec指针让其指向新的尾节点，最后将del节点释放即可，释放完别忘了将其置为空，他此时但是一个野指针~。
头删

1. //头删
2. void ListNodePopFront(ListNode* phead)
3. {
4.         assert(phead);
5.         assert(!ListEmpty(phead));
6.         //phead phead->next phead->next->next
7.         ListNode* del = phead->next;
8.         phead->next = del->next;
9.         del->next->prev = phead;
10.         free(del);
11.         del = NULL;
12. }

复制代码

头删的逻辑与尾删雷同，首先删除头节点会影响到那些节点：phead、phead->next、phead->next->next，这三个节点，同样为了避免出现过多的结构体访问操作符，以及后续的操作，将 phead->next，保存下来赋给del指针。

将这两个指针撇开重新指向新的节点

按照图示，必要将 del->next，的prev指针指向头节点，将头节点的next指针指向新的next节点。
将指针的指向修改完后，将del释放即完成了头删操作，别忘了将del置空。
指定位置删除

1. //指定位置删除
2. void ListNodeErase(ListNode* pos)
3. {
4.         assert(pos);
5.         assert(!ListEmpty(pos));
6.         //pos->prev pos pos->next
7.         pos->prev->next = pos->next;
8.         pos->next->prev = pos->prev;
9.         free(pos);
10.         pos = NULL;
12. }

复制代码

指定位置删除的思索逻辑与头删尾删一样，首先考虑删除指定的节点pos会影响到那些节点：pos->prev pos pos->next，这三个节点

将 pos->prev 节点的next指针撇开和， pos->next的prec指针撇开，如许该是容易理解的多。

• 然后改变其指向，让pos->prev 节点的next指针指向 pos->next节点。
  
• 让 pos->next节点的prev指针指向 pos->prev 节点。
  
• 最后将pos释放，置空即可。
  

销毁

1. //销毁
2. void ListDestory(ListNode* phead)
3. {
4.         ListNode* pcur = phead->next;
5.         while (pcur != phead)
6.         {
7.                 ListNode* nextnode = pcur->next;
8.                 free(pcur);
9.                 pcur = nextnode;
10.         }
11.         phead = NULL;
12.         pcur = NULL;
13. }
15. void ListDestory2(ListNode** pphead)
16. {
17.         ListNode* pcur = (*pphead)->next;
18.         while(pcur != *pphead)
19.         {
20.                 ListNode* nextnode = pcur->next;
21.                 free(pcur);
22.                 pcur = nextnode;
23.         }
24.         *pphead = NULL;
25.         pcur = NULL;
26. }

复制代码

接口：

销毁函数的功能是将双链表全部内容全部清除，包括头节点。所以不许要调用判空函数。而销毁函数的两种方法一是传递二级指针，而是传递一级指针，这里与之前的初始化函数雷同，分为了两种环境。而更推荐使用一级指针。
其原因是为了包管双链表接口的同等性，接口：现阶段不考虑吧过多的话，接口就是指函数。
包管接口的同等性是为了当实现的函数功能过多时，一些函数传递一级指针，一些函数传递二级指针，为了防止调用者的肴杂，所以这里将双链表的全部功能均采用一级指针来实现。
销毁：

在举行销毁时必要创建一个临时变量用来遍历全部节点举行销毁，这里销毁的逻辑与单链表的销毁的逻辑时一样的，然后再循环内遍历销毁时必要使用一个next指针一便于将pcur释放后重新找到下一个节点释放，循环竣事条件为 pcur != *pphead。
最后将节点释放完后将pcur置为空，此时它为空指针。
缺陷

前文说过，必要对头节点举行更改就必要传递它的所在，也就是二级指针，而这里使用一级指针来实现对双链表的销毁就丢失了这种特性，所以在销毁完双链表后，还必要手动的将头节点置为空。
总结

总的来说，在实现双链表的算法时，在插入和删除上优先考虑的是插入一个节点会影响到那些节点、删除一个节点又会影响到那些节点，以及被影响节点的指针的指向。这里最好画图加以理解。
在插入、删除、查找等功能里均使用assert断言，如许做的目的是进步函数的健壮性、而不是在传递空指针时函数无法解决而产生一系列未知异常的环境。
还强调了在实现函数功能是统一双链表的同等性、如许固然包管了全部函数传递的都是一级指针，但不能否认的是如许又会丢失一些功能，必要手动去实现，如传递一级指针，将一个双链表销毁后必要手动置空。
源码

List.h

1. #pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <stdbool.h>typedef int ListNodeDataType;
2. typedef struct ListNode
3. {
4.         ListNodeDataType data;
5.         struct ListNode* prev;
6.         struct ListNode* next;
7. }ListNode;
8. //初始化
9. void ListNodeInit2(ListNode** pphead);
10. ListNode* LTInit();
11. //打印
12. void ListPrint(ListNode* phead);
13. //尾插
14. void ListNodePushBack(ListNode* phead, ListNodeDataType x);
15. //头插
16. void ListNodePushFront(ListNode* phead, ListNodeDataType x);
17. //尾删
18. void ListNodePopBack(ListNode* phead);
19. //头删
20. void ListNodePopFront(ListNode* phead);
21. //查找
22. ListNode* ListNodeFind(ListNode* phead, ListNodeDataType x);
23. //指定位置删除
24. void ListNodeErase(ListNode* pos);
25. //指定位置插入(之后）
26. void ListNodeInsert(ListNode* pos, ListNodeDataType x);
27. //销毁
28. void ListDestory(ListNode* phead);
29. void ListDestory2(ListNode** pphead);

复制代码

List.c

1. #define _CRT_SECURE_NO_WARNINGS#include "List.h"ListNode* ListBuyNode(ListNodeDataType x){        ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));        if (newnode == NULL)        {                perror("malloc :");                exit(1);        }        newnode->data = x;        newnode->next = newnode;        newnode->prev = newnode;}ListNode* LTInit(){        ListNode* phead = ListBuyNode(-1);        return phead;}void ListNodeInit2(ListNode** pphead){        *pphead = ListBuyNode(9);}//打印
2. void ListPrint(ListNode* phead)
3. {
4.         ListNode* pcur = phead->next;
5.         while (pcur != phead)
6.         {
7.                 printf("%d->", pcur->data);
8.                 pcur = pcur->next;
9.         }
10.         printf("\n");
11. }
12. //尾插
13. void ListNodePushBack(ListNode* phead, ListNodeDataType x)
14. {
15.         assert(phead);
16.         ListNode* newnode = ListBuyNode(x);
17.         newnode->next = phead;
18.         newnode->prev = phead->prev;
19.         phead->prev->next = newnode;
20.         phead->prev = newnode;
21. }
22. //头插
23. void ListNodePushFront(ListNode* phead, ListNodeDataType x)
24. {
25.         assert(phead);
26.         ListNode* newnode = ListBuyNode(x);
27.         newnode->next = phead->next;
28.         newnode->prev = phead;
29.         phead->next->prev = newnode;
30.         phead->next = newnode;
31. }
32. bool ListEmpty(ListNode* phead)
33. {
34.         assert(phead);
35.         return phead->next == phead;
36. }
37. //尾删
38. void ListNodePopBack(ListNode* phead)
39. {
40.         assert(phead);
41.         assert(!ListEmpty(phead));
42.         //phead phead->prev  phead->prev->prev
43.         ListNode* del = phead->prev;
44.         phead->prev = del->prev;
45.         del->prev->next = phead;
46.         free(del);
47.         del = NULL;
48. }
49. //头删
50. void ListNodePopFront(ListNode* phead)
51. {
52.         assert(phead);
53.         assert(!ListEmpty(phead));
54.         //phead phead->next phead->next->next
55.         ListNode* del = phead->next;
56.         phead->next = del->next;
57.         del->next->prev = phead;
58.         free(del);
59.         del = NULL;
60. }
62. //查找
63. ListNode* ListNodeFind(ListNode* phead, ListNodeDataType x)
64. {
65.         assert(phead);
66.         ListNode* pcur = phead->next;
67.         while (pcur != phead)
68.         {
69.                 if (pcur->data == x)
70.                 {
71.                         return pcur;
72.                 }
73.                 pcur = pcur->next;
74.         }
75.         return NULL;
76. }
77. //指定位置删除
78. void ListNodeErase(ListNode* pos)
79. {
80.         assert(pos);
81.         assert(!ListEmpty(pos));
82.         //pos->prev pos pos->next
83.         pos->prev->next = pos->next;
84.         pos->next->prev = pos->prev;
85.         free(pos);
86.         pos = NULL;
88. }
89. //指定位置插入(之后）
90. void ListNodeInsert(ListNode* pos, ListNodeDataType x)
91. {
92.         assert(pos);
93.         //pos newnode pos->next
94.         ListNode* newnode = ListBuyNode(x);
95.         newnode->next = pos->next;
96.         newnode->prev = pos;
97.         pos->next->prev = newnode;
98.         pos->next = newnode;
99. }
100. //销毁
101. void ListDestory(ListNode* phead)
102. {
103.         ListNode* pcur = phead->next;
104.         while (pcur != phead)
105.         {
106.                 ListNode* nextnode = pcur->next;
107.                 free(pcur);
108.                 pcur = nextnode;
109.         }
110.         phead = NULL;
111.         pcur = NULL;
112. }
114. void ListDestory2(ListNode** pphead)
115. {
116.         ListNode* pcur = (*pphead)->next;
117.         while(pcur != *pphead)
118.         {
119.                 ListNode* nextnode = pcur->next;
120.                 free(pcur);
121.                 pcur = nextnode;
122.         }
123.         *pphead = NULL;
124.         pcur = NULL;
125. }

复制代码

test.c

1. #define _CRT_SECURE_NO_WARNINGS
2. #include "List.h"
3. void rest()
4. {
5.         ListNode* head = NULL;
6.         //ListNodeInit2(&head);
7.         head = LTInit();
8.         //尾插
9.         ListNodePushBack(head, 1);
10.         ListNodePushBack(head, 2);
11.         ListNodePushBack(head, 3);
12.         ListNodePushBack(head, 4);
13.         ListPrint(head);
14.         //头插
15.         //ListNodePushFront(head, 1);
16.         //ListNodePushFront(head, 2);
17.         //ListNodePushFront(head, 3);
18.         //ListNodePushFront(head, 4);
19.         //ListPrint(head);
21.         //尾删
22.         //ListNodePopBack(head);
23.         //ListPrint(head);
24.         //ListNodePopBack(head);
25.         //ListPrint(head);
26.         //ListNodePopBack(head);
27.         //ListPrint(head);
28.         //ListNodePopBack(head);
29.         //ListPrint(head);
30.        
31.         //头删
32.         //ListNodePopFront(head);
33.         //ListPrint(head);
34.         //ListNodePopFront(head);
35.         //ListPrint(head);
36.         //ListNodePopFront(head);
37.         //ListPrint(head);
38.         //ListNodePopFront(head);
39.         //ListPrint(head);
40.         ListNode* ret = ListNodeFind(head,4);
41.         if (ret != NULL)
42.         {
43.                 printf("有了！\n");
44.         }
45.         else
46.         {
47.                 printf("没有！\n");
48.         }
49.         //ListNodeErase(ret);
50.         //ListNodeInsert(ret, 6);
51.         ListPrint(head);
53.         //ListDestory2(&head);
54.         ListDestory(head);
55.         head = NULL;
57. }
58. int main()
59. {
60.         rest();
61.         return 0;
62. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。