【数据结构】双向链表（真正的零基础）

链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过指针的链接来实现的！在上篇我们学习了单向链表，而单向链表虽然空间利用率高，插入和删除也只需改变指针就可以达到！但是我们在每次查找、删除、访问.....时，都受到单向链表的一个特性干扰：单向不可逆，只能以遍历的形式去使用，这样使得需要从头到尾找到特定的节点再进行操作！今天我们来学习另外一种链表结构：双向链表。既然是零基础，我会从小白的角度进行讲解！放心食用！

目录

                                                            一.链表的分类

                                                   二.带头双向循环链表

                                                                               二.（1）链表节点设置

                                                                      二.（2）链表新增节点

                                                             二.（3）链表初始化 

                                                    二.（4）链表扩容节点

                                                    二.（5）链表打印

                                                    二.（6）在目标节点前面插入

                                                    二.（7）在目标节点后面插入

                                                    二.（8）链表头删

                                                    二.（9）链表尾删

                                                    二.（10）链表头插

                                                    二.（11）链表尾插

                                                    二.（12）删除中间目标节点

                                                    二.（13）释放双链表

               三.总结

               四.代码合并

---

一.链表的分类

这里就不介绍哈是链表了，如果对此感到疑惑，可以看我上一篇投稿，咱直接进入分类！

链表主要可以分为以下3大类：

单向链表：

单向链表是链表中最简单的一种，它由一系列节点组成，每个节点包含两个部分：指针域与数据域。指针域用来指向下一个节点的地址，数据域用来存储数据。以下是抽象草图，方便巧记：

双向链表：

 双向链表与单向链表不同，它的每个节点有两个指针（next跟prev）跟一个数据域，两个指针分别指向前一个节点和后一个节点。同样，如图巧记：

循环链表：
 循环链表是一种特殊的单链表，它的最后一个节点的指针指向头节点，形成一个“环”，如图：

在进行下面的学习之前，针对链表的各种分类，我们需要理清几个名词：

头指针：

头指针本质上是结构体类型的指针，指向一个节点，这个节点一般是 第一个节点 或者 头节点

头结点：

简单理解为在 第一个节点 前面还有一个节点，这个节点就称为头节点。头节点一般不存储数据

带头：

头指针指向头节点就称为带头节点，如图：

不带头： 

头指针指向第一个节点就称为不带头节点，如图：

针对这几种分类：带头或者不带头、单向或者双向、循环或者非循环 

我们总共可以组合八种链表，我们主要学习 无头双向非循环链表     带头双向循环链表    这两种！

八种链表结构中其中这两种最具代表性，另外六种便自然理解了！上一篇我们已经学完了第一种，今天我们来学习第二种！

注意：双链表一般需要改变四个指针的指向，因此建议大家画图理解！这样就可以轻松操作了！

二.带头双向循环链表

理解了上面几个名词后，我们就能轻易理解哈是带头双向循环链表了！

带头：无非就是第一个节点前还有一个头节点嘛！

双向：节点里面有两个指针，两个指针分别指向一前一后的节点

循环：尾节点的后指针指向头节点，头节点的前指针指向尾节点，达到封闭，形成循环！

二.（1）链表节点设置

不论怎样，我们都需要先创建一个结构体作为接下来各种功能的节点基础， 这个结构体里面有两个指针，一个数据域。这里为了缩短结构体类型，我们用 typedef 重定义以下，需要注意的是typedef重定义的这个结构体里面，结构体指针必须写完整，因为此处还属于声明阶段，后续才可以正常缩写。代码如下：

typedef struct Pointdef
{struct Pointdef* next;//指向下一个节点struct Pointdef* prev;//指向上一个节点int data;//数据域
}Pointdef;

二.（2）链表新增节点

因为我们不管初始化还是各种增添功能，都需要节点，所以我们先完成开辟节点的函数，让这个函数返回指向这个开辟好的节点指针，然后才可以进行初始化操作，代码如下：

//开辟新节点
Pointdef* Newspoint(int x)
{Pointdef* news = (Pointdef*)malloc(sizeof(Pointdef));if (news == NULL){perror("malloc");return NULL;}//初始化新节点news->next = NULL;news->prev = NULL;news->data = x;return news;
}

我们刚开辟好的节点还没有连接，只是一个结构体大小，因此它的prev跟next指针都指向NULL，x就是初始化节点的数据域，如下图理解：

二.（3）链表初始化 

上面我们先调用 新增节点 的函数，在外面开辟一个节点作为头节点（如果有问题，可以先看下面的合并代码！），接下来对这个头节点进行初始化，将它作为头节点，此时头节点的next跟prev指针都应该指向自己（因为是循环链表，此时只有一个节点）。代码如下：

//链表初始化
void Initialize(Pointdef* head)
{head->next = head;head->prev = head;
}

二.（4）链表扩容节点

此时我们已经初始化了链表，下面我们给它新增几个节点，调用新增函数，改变节点指针指向，代码如下：

//链表扩容节点
Pointdef* tail = head;
for (int i = 2; i <= 5; i++)
{Pointdef* news = Newspoint(i);//连接tail->next = news;news->prev = tail;news->next = head;head->prev = news;tail = tail->next;
}

二.（5）链表打印

与单向链表访问区别不大，只需要注意是这里的链表是循环的，需要控制打印的条件不能是当前指针不能指向头节点，否则就是死循环了，代码如下： 

//链表打印
void Printf(Pointdef* head)
{Pointdef* tail = head->next;while (tail != head){printf("%d <= ", tail->data);tail = tail->next;}printf("NULL\n");
}

二.（6）在目标节点前面插入

我们已经写好了一条双链表，那么我们只需要找到目标节点然后连接四个指针就行了，代码如下：

这里我们假设目标节点是 tail ，新节点 news  新节点前面的节点是 prev

//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{assert(tail);Pointdef* prev = tail->prev;Pointdef* news = Newspoint(x);prev->next = news;news->prev = prev;news->next = tail;tail->prev = news;}

二.（7）在目标节点后面插入

将找到的目标节点作为参数，然后在函数中改变它的前后四个指针就行，如图：

//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{assert(tail);//目标节点的下一个节点不能是空，否则就是尾插了assert(tail->next);Pointdef* news = Newspoint(x);Pointdef* next = tail->next;tail->next = news;news->prev = tail;news->next = next;next->prev = news;
}

 二.（8）链表头删

头删咱直接将头节点作为参数就行了，再记录第二个节点方便释放，然后用四个指针连接头节点和第二个节点，最后记得释放第一个节点的空间，如图：

//链表头删
void Outomit(Pointdef* head,int x)
{assert(head);assert(head->next);Pointdef* tail = head->next->next;Pointdef* next = head->next;head->next = tail;tail->prev = head;free(next);next = NULL;
}

二.（9）链表尾删

这个咱就不多说了！就是先记录倒数第二个节点，将它作为尾节点就行了，同样记得释放空间，直接上代码：

//链表尾删
void Tailomit(Pointdef* head, int x)
{assert(head);Pointdef* prev = head->prev->prev;Pointdef* tail = head->prev;prev->next = head;head->prev = prev;free(tail);tail = NULL;
}

二.（10）链表头插

但凡插入节点的都具有很大的相似之处，无非就是将这个节点插入某处，通过记录附近节点的位置，再把新增节点的左右节点与它进行连接，看代码：

//链表头插
void Headinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail = head->next;Pointdef* news = Newspoint(x);head->next = news;news->prev = head;news->next = tail;tail->prev = news;
}

二.（11）链表尾插

//链表尾插
void Tailinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail = head->prev;Pointdef* news = Newspoint(x);tail->next = news;news->prev = tail;head->prev = news;news->next = head;
}

二.（12）删除中间目标节点

删除节点我们肯定要先找到目标节点，我们在链表中可以通过以下两种方式寻找：指针域  数据域，在上面的前后插入中，我们选择的指针查找方式，下面我们进行数据查找方式来删除：

//链表中间节点删除
void Omit(Pointdef* tail)
{Pointdef* pc = tail->prev;Pointdef* pt = tail->next;pc->next = pt;pt->prev = pc;free(tail);tail = NULL;
}

二.（13）释放双链表

咋从第一个节点释放到尾就OK了！注意：链表的空间不是连续的，因此需要一个个销毁！

//双链表销毁
void Undermine(Pointdef* head)
{assert(head);Pointdef* cur = head->next;Pointdef* tail = cur->next;while (cur != head){tail = cur->next;free(cur);cur = tail;}free(head);head=NULL;printf("释放完毕\n");
}

三.总结

针对以上实现的双链表，其实针对整个链表，都有以下特点：

1：首先我们要有设计好开辟节点的函数，然后知道如何连接这些节点

2：头插、尾插、中间插其实都有很大的共性，只是目标地点稍微差异，这点大家可以画图理解！

3：删除某个节点需要及时释放该空间，避免空间泄漏。需要注意是先连接，再释放

4：针对为何单向链表很多涉及二级指针，而双向链表大多是一级指针？

因为单向链表有很多地方需要改变头指针（单向链表将第一个节点作为头节点）的指向，而双向链表是固定了哨兵节点，因此其它操作其实是针对结构体里面的指针操作的。该知识的原理是：对形参的改变不影响实参，如需改变形参，需要使用二级指针

5：双向链表为哈要从第一个节点开始释放？

双向链表的头节点是链表结构的一部分，不是数据节点，应该先释放数据节点，再释放链表结构

四.代码合并

流程文件（可以使用打印来进行功能的测试！）

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"int main()
{int x = 4;//链表新增节点Pointdef* head=Newspoint(1);//链表初始化void Initialize(head);//链表扩容节点Pointdef* tail = head;for (int i = 2; i <= 5; i++){Pointdef* news = Newspoint(i);//连接tail->next = news;news->prev = tail;news->next = head;head->prev = news;tail = tail->next;}//链表打印Printf_t(head);//在目标节点前面插入                      tail = (head->next)->next;x = 6;FrontInsertion(tail, x);//在目标节点后面插入                OutInsertion(tail, x);//                                  测试点Printf_t(head);//链表头删x = 7;Outomit(head,x);//链表尾删x = 8;Tailomit(head, x);//                                  测试点Printf_t(head);//链表头插x = 1;Headinsert(head, x);//链表尾插x = 9;Tailinsert(head, x);//                                  测试点Printf_t(head);//链表中间节点删除x = 4;tail = head -> next;while (tail->data != x){tail = tail->next;}Omit(tail);//                                   测试点Printf_t(head);//双链表销毁Undermine(head);return 0;
}

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>typedef struct Pointdef
{struct Pointdef* next;//指向下一个节点struct Pointdef* prev;//指向上一个节点int data;//数据域
}Pointdef;//链表新增节点
Pointdef* Newspoint(int x);
//链表初始化
void Initialize(Pointdef* head);
//链表打印
void Printf_t(Pointdef* head);
//在目标节点前面插入
void FrontInsertion(Pointdef* tail, int x);
//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x);
//链表头删
void Outomit(Pointdef* head ,int x);
//链表尾删
void Tailomit(Pointdef* head, int x);
//链表头插
void Headinsert(Pointdef* head, int x);
//链表尾插
void Tailinsert(Pointdef* head, int x);
//链表中间节点删除
void Omit(Pointdef* tail);
//双链表销毁
void Undermine(Pointdef* head);

函数执行文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"//链表新增节点
Pointdef* Newspoint(int x)
{Pointdef* news = (Pointdef*)malloc(sizeof(Pointdef));if (news == NULL){perror("malloc");return NULL;}//初始化新节点news->next = NULL;news->prev = NULL;news->data = x;return news;
}//链表初始化
void Initialize(Pointdef* head)
{head->next = head;head->prev = head;
}//链表打印
void Printf_t(Pointdef* head)
{Pointdef* tail = head->next;while (tail != head){printf("%d <= ", tail->data);tail = tail->next;}printf("NULL\n");
}//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{assert(tail);Pointdef* prev = tail->prev;Pointdef* news = Newspoint(x);prev->next = news;news->prev = prev;news->next = tail;tail->prev = news;}//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{assert(tail);//目标节点的下一个节点不能是空，否则就是尾插了assert(tail->next);Pointdef* news = Newspoint(x);Pointdef* next = tail->next;tail->next = news;news->prev = tail;news->next = next;next->prev = news;
}//链表头删
void Outomit(Pointdef* head,int x)
{assert(head);assert(head->next);Pointdef* tail = head->next->next;Pointdef* next = head->next;head->next = tail;tail->prev = head;free(next);next = NULL;
}//链表尾删
void Tailomit(Pointdef* head, int x)
{assert(head);Pointdef* prev = head->prev->prev;Pointdef* tail = head->prev;prev->next = head;head->prev = prev;free(tail);tail = NULL;
}//链表头插
void Headinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail = head->next;Pointdef* news = Newspoint(x);head->next = news;news->prev = head;news->next = tail;tail->prev = news;
}//链表尾插
void Tailinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail = head->prev;Pointdef* news = Newspoint(x);tail->next = news;news->prev = tail;head->prev = news;news->next = head;
}//链表中间节点删除
void Omit(Pointdef* tail)
{Pointdef* pc = tail->prev;Pointdef* pt = tail->next;pc->next = pt;pt->prev = pc;free(tail);tail = NULL;
}//双链表销毁
void Undermine(Pointdef* head)
{assert(head);Pointdef* cur = head->next;Pointdef* tail = cur->next;while (cur != head){tail = cur->next;free(cur);cur = tail;}free(head);head = NULL;printf("释放完毕\n");
}