[数据结构与算法]数据结构系列2——双向链表和双向循环链表

引入：双向链表是在原来的单链表基础上增加了一个可以保存某节点的上一个节点的指针域的数据结构，相较于单链表而言，双向链表在查找数据的时候所花费的时间是要小于单链表的，因为其可进可退。其缺点就是增删节点比单链表麻烦，而且在创建节点的时候也需要多申请一个指针存储空间。双向循环链表，顾名思义就是在双向链表的基础上，将尾节点的“right”指针指向头结点，同时头结点的“left”指针指向尾节点，它和双向链表的不同是，其判断节点是否遍历完毕的条件不再是是否为空，而是是否回到了头结点?，优点是可以在任意位置插入数据，时间复杂度为O（1）

一、双向链表

1、双向链表的封装和创建

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//#include <xkeycheck.h>
typedef struct Node			//typedef起别名，简化代码
{
	int data;					//数据域
	struct Node* left;		//前驱节点
	struct Node* right;		//后驱节点
}NODE,*NODELINK;

//创建节点
NODELINK creatNode(int data)
{
	NODELINK newnode = (NODELINK)malloc(sizeof(NODE));		//为指针申请内存空间
	assert(newnode);			//断言处理
	newnode->data = data;		//初始化节点
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;			//将节点返回
}

//描述链表特性
typedef struct List
{
	NODELINK frontnode;
	NODELINK backnode;
	int cursize;			//万金油参数（当前链表的长度）
}LIST,*LISTLINK;

//创建带头链表（本质就是申请一个没有数据的头结点）
LISTLINK creatList()
{
	LISTLINK list = (LISTLINK)malloc(sizeof(LIST));
	assert(list);
	list->cursize = 0;
	list->frontnode = NULL;
	list->backnode = NULL;
	return list;
}

我们对双向链表进行了再封装，目的是用frontnode保存头结点的位置，backnode保存尾节点，用cursize记录当前链表中节点的个数。很多小伙伴不知道断言是什么意思，我这里解释一下，断言就是当你的计算机内存不足导致无法为指针申请空间时，我们就可以用断言进行判断，当申请到的内存为空时，assert();这条语句就会引发断点，让我们的程序中断，提醒程序员这里内存分配失败了

2、双向链表的简单操作

1、头插法插入节点

//表头法插入新节点
void pushListByHead(LISTLINK list,int data)
{
	NODELINK newnode = creatNode(data);			//利用我们写好的创建节点的函数创建节点
	if (list->cursize == 0)		
	{
		list->frontnode = newnode;
		list->backnode = newnode;
		list->cursize++;
	}
	else
	{
		newnode->right = list->frontnode;
		list->frontnode->left = newnode;
		list->frontnode = newnode;
		list->cursize++;
	}
}

这里注意，当我们的链表中没有节点的时候，也就是cursize等于0的时候，插入节点的时候需要注意将我们的表头（list）的前驱和后驱节点都修改为newnode,其他时候就正常插入就好了，插入操作完成后记得将我们的万金油参数做++运算

2、尾插法插入节点

//表尾插入节点
void pushListByTail(LISTLINK list, int data)
{
	NODELINK newnode = creatNode(data);
	if (list->cursize == 0)
	{
		list->frontnode = newnode;
		list->backnode = newnode;
		list->cursize++;

	}
	else
	{
		newnode->left = list->backnode;
		list->backnode->right = newnode;
		list->backnode = newnode;
		list->cursize++;
	}
}

表头表尾插入本质上和单链表一样，只是在做连接的时候要麻烦一点

3、指定位置插入

//指定位置插入(在posdata前面插入data)
void pushByAppoin(LISTLINK list,  int posdata, int data)
{
	NODELINK frontmove = list->frontnode;
	NODELINK pmove = NULL;		//指定位置插入需要保存插入位置的前后两个节点
	
	//遍历链表，寻找节点数据为posdata的节点	
	while (frontmove->data != posdata && frontmove != NULL)
	{
		pmove = frontmove;
		frontmove = frontmove->right;
	}
	//遍历完毕，根据frontmove判断是否查找成功
	if (frontmove == NULL)
	{
		printf("为找到指定数据，无法插入！");
		return;
	}
	else
	{
		NODELINK newnode = creatNode(data);
		pmove->right = newnode;			//注意插入顺序，画图方便理解
		newnode->left = pmove;
		newnode->right = frontmove;
		frontmove->left = newnode;
		list->cursize++;		//将cursize做++运算
	}
}

4、表头法删除

//双向链表表头法删除
void deleteFromHead(LISTLINK list)
{
	NODELINK pmove = list->frontnode->right;	//保存要删除节点的右边节点
	free(list->frontnode);		//释放内存
	list->frontnode = pmove;	//将头节点移向刚刚保存的节点
	pmove->left = NULL;		//一定要将删除后的新的头结点的左边置为NULL
	if (list->cursize == 1)			//当删除的头节点是最后一个节点时，将保存尾节点的backnode置为NULL
	{
		list->backnode = NULL;
	}
	list->cursize--;			//记得将链表节点个数做--运算
}

5、表尾法删除

//双向链表表尾法删除
void deleteFromBack(LISTLINK list)
{
	NODELINK pmove = list->backnode->left;
	free(list->backnode);
	list->backnode = pmove;
	pmove->right = NULL;
	if (list->cursize == 1)
	{
		list->frontnode = NULL;
	}
	list->cursize--;
}

直接通过backnode找到尾节点，这就是再封装的好处

6、从头往尾打印节点数据

//从头往尾部打印数据
void printDataFromHead(LISTLINK list)
{
	NODELINK pmove = list->frontnode;
	while (pmove!=NULL)
	{
		printf("%d\t", pmove->data);
		pmove = pmove->right;
	}
	printf("\n");
}

7、从尾往头打印节点数据

//从尾往头部打印数据
void printDataFromBack(LISTLINK list)
{
	NODELINK pmove = list->backnode;
	while (pmove)
	{
		printf("%d\t", pmove->data);
		pmove = pmove->left;
	}
	printf("\n");
}

8、判空处理

// 判空处理
int empty(LISTLINK list)
{
	return list->cursize == 0;
}

这里我们直接通过cursize的值来判空

3、运行测试

int main()
{
	LISTLINK list = creatList();		//创建表头
	LISTLINK list1 = creatList();
	//测试表头法和表尾法插入
	for (int i = 0; i < 10; i++)
	{
		pushListByHead(list, i);
		pushListByTail(list1, i);
	}
	//测试从头和从尾打印节点数据
	printDataFromHead(list);
	printDataFromBack(list);
	printDataFromHead(list1);
	printDataFromBack(list1);
	//测试置定位位置插入
	pushByAppoin(list, 8, 6);
	printDataFromHead(list);
	printDataFromBack(list);
	//测试头部删除并打印
	deleteFromHead(list);
	printDataFromHead(list);
	//测试尾部删除并打印
	deleteFromBack(list);
	printDataFromHead(list);
	return 0;
}

4、运行结果

?根据测试代码我们发现我们的代码写的没有问题，小伙伴们可以参考

二、双向循环链表

1、双向循环链表的实现

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


typedef struct Node
{
	int data;					//数据域
	struct Node* left;		//前驱节点
	struct Node* right;		//后驱节点
}NODE, * NODELINK;

//创建节点
NODELINK createNode(int data)
{
	NODELINK newnode = (NODELINK)malloc(sizeof(NODE));
	assert(newnode);
	newnode->data = data;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

//创建环形链表
NODELINK creatList()
{
	NODELINK headnode = (NODELINK)malloc(sizeof(NODE));
	assert(headnode);
	headnode->left = headnode;		//将头结点的left指向自己
	headnode->right = headnode;		//将头结点的right指向自己
	return headnode;
}

我这里写的双向循环链表的实现过程与上面是双向链表的实现过程相比，少了再封装的过程（感兴趣的小伙伴可以尝试写一下喔），剩下的唯一的不同就是在创建头结点的过程中将left,right指针指向了自己，在后续的操作中就可以构成环形结构

2、双向循环链表的简单操作

1、表头法插入节点

//头插法插入节点
void insertDataFromHead(NODELINK list, int data)
{
	NODELINK newnode = createNode(data);
	assert(newnode);	
	list->right->left = newnode;		
	newnode->right = list->right;
	newnode->left = list;
	list->right = newnode;
}

关于数据结构有关的操作，不好理解的小伙伴我强烈建议画图理解 ，瞬间就豁然开朗的感觉真的很爽

2、表尾法插入节点

//尾插法插入节点
void insertDataFromBack(NODELINK list, int data)
{
	NODELINK newnode = createNode(data);
	assert(newnode);
	list->left->right = newnode;
	newnode->left = list->left;
	newnode->right = list;
	list->left = newnode;
}

3、指定位置插入

//指定位置插入(在posdata数据的前面插入data)
void insertDataByAppoin(NODELINK list, int posdata, int data)
{
	NODELINK tail = list->right;		//定义两个移动的节点
	NODELINK front = list;
	while (tail != list&&tail->data!=posdata)	//注意遍历完毕的条件
	{
		front = tail;
		tail = tail->right;
	}
	if (tail == list)
	{
		printf("未找到指定数据，请确认数据是否正确！！\n");
		return;
	}
	else  
	{
		NODELINK newnode = createNode(data);
		front->right = newnode;
		newnode->left = front;
		newnode->right = tail;
		tail->left = newnode;
	}
	
}

4、表头法删除

//表头法删除
void deleteDataFromHead(NODELINK list)
{
	NODELINK deletenode = list->right;
	deletenode->right->left = list;
	list->right = deletenode->right;
	free(deletenode);
	deletenode = NULL;
}

5、表尾法删除

//表尾法删除
void deleteDataFromBack(NODELINK list)
{
	NODELINK deletenode = list->left;
	deletenode->left->right = list;
	list->left = deletenode->left;
	free(deletenode);
	deletenode = NULL;
}

6、指定位置删除

//指定位置删除
void deleteDataByAppoin(NODELINK list, int data)
{
	NODELINK tail = list->right;
	NODELINK front = list;
	while (tail != list && tail->data != data)
	{
		front = tail;
		tail = tail->right;
	}
	if (tail == list)
	{
		printf("未找到指定数据，请确认数据是否正确！！\n");
		return;
	}
	else
	{
		front->right = tail->right;
		tail->right->left = front;
	}
}

7、从左往右打印数据

//从左往右遍历双向链表，并打印数据
void printDataToRight(NODELINK list)
{
	NODELINK pmove = list->right;
	while (pmove != list)
	{
		printf("%d\t", pmove->data);
		pmove = pmove->right;
	}
	printf("\n");
}

8、从右往左打印数据

//从右往左遍历双向链表，并打印数据
void printDataToLeft(NODELINK list)
{
	NODELINK pmove = list->left;
	while (pmove != list)
	{
		printf("%d\t", pmove->data);
		pmove = pmove->left;
	}
	printf("\n");
}

3、运行测试

int main()
{
	//创建链表（本质就是创造一个没有数据的头结点）
	NODELINK list = creatList();
	NODELINK list1 = creatList();
	//测试头插法和往左往右打印
	for (int i = 0; i < 10; i++)
	{
		insertDataFromHead(list, i);
	}
	printDataToRight(list);
	printDataToLeft(list);
	//测试尾插法和往左往右打印
	for (int i = 0; i < 10; i++)
	{
		insertDataFromBack(list1, i);
	}
	printDataToRight(list1);
	printDataToLeft(list1);
	//测试指定位置插入
	insertDataByAppoin(list, 8, 9);
	printDataToRight(list);
	//测试表头法删除
	deleteDataFromHead(list);
	printDataToRight(list);
	//测试表尾法删除
	deleteDataFromBack(list);
	printDataToRight(list);
	//测试指定位置删除
	deleteDataByAppoin(list, 6);
	printDataToRight(list);
	return 0;
}

4、运行结果

?根据测试代码可知，我们的代码没毛病

三、总结

对双向链表和双向循环链表不了解的小伙伴们可以多看几遍我写的代码，理解意思了之后敲一遍，发现问题了就对照着查看哪里错误了，如果实在找不到问题所在，就可以进行调试，不会的小伙伴可以翻阅我以前写的博客，有一篇详细教了大家怎么用VS2019进行调试。最后祝看到这篇博客的你学业有成，步步高升，祝给我一键三连的小伙伴，多年以后还有头发