【数据结构】双向链表

前言

这篇博客我们来继续探讨链表，上篇博客我们讨论了单链表，其实链表的种类有很多，但最常用的除了单链表之外，还有个双向链表，今天我们就来总结下双向链表

💓 个人主页：小张同学zkf

⏩ 文章专栏：数据结构

若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章

目录

1.链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构

我们上篇博客的单链表其实就是不带头单向不循环链表

那本篇博客的双向链表就是带头双向循环链表

2.双向链表的结构

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严 谨，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的” ，“哨兵位”存在的意义： 遍历循环链表避免死循环。

3.实现双向链表

那么双向链表如何实现那

老规矩依旧三个文件，头文件，两源文件

我们先来在头文件把各个函数声明好，先定义双向链表节点结构体

这个就是双向链表节点的结构体，里面有两个指针，一个指针指向下一个节点，一个指针指向上一个节点

接着把各个函数声明好

声明好之后，我们就开始在.c文件中进行定义

双向链表不能为空，它始终都有一个节点，是哨兵位（头结点），所以我们先定义一个申请节点的函数，申请节点空间，跟我们的单链表一样都是用malloc申请

代码如下：

头结点，我们不需要任何数据，所以传个-1就行

我们接着来初始化双向链表，那有人直接上来把俩指针置空，我们好好想想这样初始化对吗

 俩指针都置为空的话怎么循环起来那，所以初始化的话，不能将俩指针置为空，应该指向头结点（哨兵位）如图所示，所以不用管这里指针，初始化好后直接返回头结点。

好了，代码如下

初始化好后我们就开始尾插

无论尾插，还是头插，都不影响头结点的变化，就算是头插，也是在头结点之后插入，头结点永远不变

考虑好这一点，我们接下来画图分析如何尾插那

 首先，我们先通过申请节点函数，申请新节点。

我们可以看到新来的节点newnoad上一个节点指向d3,但d3的位置我们如何获取那，d3是不是就是头结点的上一个节点，所以我们可以根据头结点来获取，newnoad下一个节点是头结点，所以直接指向头结点就行了，接着是头结点phead上一个指向指向新的尾结点，d3下一个节点就是newnoad新的尾结点。

分析完了就可以写代码了

别忘了，我们把哨兵位（头结点）传进来要确保有效，不能为空，否则双向链表就无效，所以要断言头结点。

尾插玩我们来看头插，头插一定于要记得对于双向链表来说，头插是在头结点之后插入，不是再头结点之前！！！！ 

我们画图分析

由图可以清晰看出是在head后面插的，但我们要知道这个指向顺序，我们一定要先让newnoad的下一个节点指向d1，再让newnoad上一节点指向head,接着就是指向新节点的过程，我们假如让head先指向新的节点，那我们无法通过head得知d1的位置，就会很麻烦，我们可以先通过head指向d1得知d1的位置，再通过d1的上一个节点指向newnoad，最后再phead直接指向新节点就可以了，这个顺序比较方便点

OK分析完就可以写代码了

别忘了断言双链表是否有效

插完我们再来看删，我们先来看尾删

 我们尾删时先不要着急free，不然可能找不到d2的位置，我们要先通过d3找到d2,再让head的上一个节点指向它，再free掉d3，有人有疑问了，那d3位置如何找到那，d3就是head原来的prev节点，我们可以用del临时变量，来保存d3的位置，再让phead上个节点指向del上个节点d2就行了，通过del的上个节点找到d2后，再让d2的下个节点指向head，就ok了；

分析完可以写代码了

代码如下

注意这里不仅要判断双链表是否有效，还要判断链表不能为空，否则无法删除，feel完记得置空

    尾删完我们头删，我们画图分析

 头删相对来说比较简单，由图可知，我们还是先不要提前free，否则我们不好找到d2的位置，我们先通过d1把前后两个节点互指，然后再free就OK了

代码如下

我们继续来定义在指定位置之后删除的函数

我们依旧画图分析

假如我们在d2后插入新节点，我们先通过POS找到d3，然后先把newnoad上一个节点指向pos再把newnoad下一个节点指向d3，然后就是类似头插的操作，先把d3上一个操作指向newnoad，再把POS下一个节点指向newnoad, 就结束了

但我们得考虑一个特殊情况，当pos节点是尾结点时，那就是尾插，但是由于尾插函数需要传头结点，所以不能直接调用尾插函数，我们这个逻辑分析，也符合尾插的应用，所以这个特殊情况也是符合我们刚刚分析的顺序

代码如下

我们接下来定义删除节点的函数

我们画图表示

由图可知，我们只要将POS节点的前后节点互指，然后free掉POS就行了

代码如下

我们定义打印函数

打印函数就特别简单，直接遍历函数，while循环的条件就是当节点的下一个指针不指向头结点时，循环成立，如果是跳出循环

代码如下

我们定义一个查找函数

查找函数也是遍历条件个打印函数一样

代码如下

我们最后定义销毁函数

销毁函数，挨个遍历节点，然后销毁节点，最后头结点释放掉

代码如下

我们要注意一点

 销毁函数与删除函数调用完，由于传址调用，形参影响不改变实参，所以这俩函数调用完还要手动置空，这一点要注意！！！！                                                                                                         

定义完函数，别忘了用另一个源文件进行检测

以下是双向链表的所有代码

.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;


//声明双向链表中提供的方法

//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDesTroy(LTNode* phead);

void LTPrint(LTNode* phead);

//插入数据之前，链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址，因此传一级即可
//尾插
void LTPushBack(LTNode* phead, LTDataType x); 
//头插
void LTPushFront(LTNode* phead, LTDataType x); 

//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);


//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

.c 

#include"List.h"

void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//申请节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;

	return node;
}
//初始化
//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

	//phead phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next = newnode;
}

//尾删
void LTPopBack(LTNode* phead)
{
	//链表必须有效且链表不能为空（只有一个哨兵位）
	assert(phead && phead->next != phead);

	LTNode* del = phead->prev;
	//phead del->prev del
	del->prev->next = phead;
	phead->prev = del->prev;

	//删除del节点
	free(del);
	del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	
	LTNode* del = phead->next;
	
	//phead del del->next
	phead->next = del->next;
	del->next->prev = phead;

	//删除del节点
	free(del);
	del = NULL;
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{
	//pos理论上来说不能为phead，但是没有参数phead，无法增加校验
	assert(pos);
	//pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}
void LTDesTroy(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur指向phead，而phead还没有被销毁
	free(phead);
	phead = NULL;
}

test.c

#include"List.h"

void ListTest01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPrint(plist);

	LTNode* find = LTFind(plist, 3);
	//LTInsert(find, 66);
	LTErase(find);
	find = NULL;

	LTPrint(plist);
	LTDesTroy(plist);
	//plist = NULL;
	

	//if (find == NULL)
	//{
	//	printf("找不到！\n");
	//}
	//else {
	//	printf("找到了！\n");
	//}

	//LTPushFront(plist, 1);
	//LTPrint(plist);
	//LTPushFront(plist, 2);
	//LTPrint(plist);
	//LTPushFront(plist, 3);
	// 
	//
	测试尾删
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);

	测试头删
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
}

int main()
{
	ListTest01();
	return 0;
}

结束语

本篇博客有关双向链表的实现总结结束，中间有什么问题，可以评论区发出来，中间有些细节，可能没有那么深入，欢迎大家来补充

OK，感谢观看！！！