【数据结构】双向链表-EW帮帮网

一、双向链表
- 1、概念与结构
- 2、双向链表结构的定义
- 3、创建新节点
- 4、双向链表的初始化
- 5、双向链表的打印
- 6、尾插
- 7、头插
- 8、尾删
- 9、头删
- 10、查找
- 11、在`pos`位置之后插入数据
- 12、删除`pos`位置的结点
- 13、销毁链表
二、源代码

一、双向链表

1、概念与结构

双向链表中每个节点包含数据以及指向前一个节点和后一个节点的指针，它允许在链表中双向遍历，既可以向前也可以向后访问节点，在插入和删除操作上更灵活高效。

带头双向循环链表如图所示
双向链表和单链表的结构有所不同，从上图就可以就看出单链表和双向链表之间的区别，单链表的内部只有两个成员一个是存储的数据data，一个是存储下一个节点的指针next，而双向链表在此基础上增加了一个指向前一个节点的指针prev。

注意：双向链表中的头节点head不存储任何的数据。
在这里插入图片描述
双向链表主要完成的功能与单链表大致相同，主要有头插、尾插、头删、尾删、查找节点、在指定位置插入节点、删除指定位置的节点等。

2、双向链表结构的定义

上面我们已经描述了双链表的结构所以代码如下：

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

我们这里和实现单链表的时候一样，依旧采用取别名的形式，将int取为LTDataType，方便后续对代码的一键修改。

3、创建新节点

//创建新的结点
ListNode* LTBuyNode(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)
	{
		perror("malloc fail!");
		return 1;
	}
	newNode->data = x;
	newNode->prev = newNode->next = newNode;//创建新节点时要指向自己

	return newNode;
}

4、双向链表的初始化

这里双向链表就和单链表有所不同了，当单链表为空时指向第一个结点的指针为空，而当双向链表为空时，链表中只有一个头结点，并且它会自己指向自己。

//双向链表的初始化
ListNode* LTInit()
{
	ListNode* phead = LTBuyNode(-1);

	return phead;
}

这里双向链表的头结点不储存数据，所以初始化时将数据存成-1即可。

测试结果：
在这里插入图片描述
从测试结果上可以看出prev和next都指向它自己。

5、双向链表的打印

//双向链表的打印
void LTPrint(ListNode* phead)
{
	ListNode* pcur = phead->next;//head指向第一个结点
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

6、尾插

//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newNode = LTBuyNode(x);
	//newNode phead->prev(尾结点) phead
	newNode->prev = phead->prev;//新结点的前一个结点是尾结点
    newNode->next = phead;//新节点的下一个结点是头结点

    phead->prev->next = newNode;//链接旧尾结点与新尾结点
    phead->prev = newNode;//更换头节点指向的尾结点
}

测试代码：

#include "List.h"

void test()
{
	ListNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPrint(plist);
}

int main()
{
	test();

	return 0;
}

测试结果：
在这里插入图片描述

通过内存及通过测试结果，我们都能发现尾插成功了。

7、头插

//头插
void LTPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newNode = LTBuyNode(x);
	newNode->next = phead->next;//将新节点与旧的第一结点链接起来
	newNode->prev = phead;//将新节点与头节点链接起来

	phead->next->prev = newNode;//改变旧的第一个结点的prev指针的指向
	phead->next = newNode;//改变头节点的next指针的指向
}

测试代码：

#include "List.h"

void test()
{
	ListNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushFront(plist, 3);
	LTPrint(plist);
}

int main()
{
	test();

	return 0;
}

测试结果：
在这里插入图片描述

8、尾删

首先，我们在进行尾删的时候要确保链表不为空，因此我们可以将判空的部分单独封装成一个函数，这里我们会用到bool类型，所以我们要加上#include <stdbool.h>头文件。

//判空
bool LTEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead;//只剩下一个结点的时候链表为空
}

删除的时候，我们不能删除头节点，所以在链表只剩一个结点时，链表就为空。

//尾删
void LTPopBack(ListNode* phead)
{
	assert(!LTEmpty(phead));
	ListNode* del = phead->prev;
	//del del->prev phead
	phead->prev = del->prev;
	del->prev->next = phead;

	free(del);
	del = NULL;
}

测试代码：

#include "List.h"

void test()
{
	ListNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushFront(plist, 3);
	LTPrint(plist);
	LTPopBack(plist);
	LTPopBack(plist);
	LTPrint(plist);
}

int main()
{
	test();

	return 0;
}

测试结果：
在这里插入图片描述
这时当我们再多删几次，我们期望代码能够在链表为空时断言报错。
结果：

可以看到代码执行成功报错了，符合我们的预期。

9、头删

头节点删除的是头结点之后的第一个结点。

//头删
void LTPopFront(ListNode* phead)
{
	assert(!LTEmpty(phead));
	ListNode* del = phead->next;
	//del phead del->next
	phead->next = del->next;
	del->next->prev = phead;

	free(del);
	del = NULL;
}

测试代码：

#include "List.h"

void test()
{
	ListNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushFront(plist, 3);
	LTPrint(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPrint(plist);
}

int main()
{
	test();

	return 0;
}

测试结果：
在这里插入图片描述
可以看到这段代码可以胜任我们的任务，这里不用担心指向NULL的情况因为我们这个是循环双向链表。

10、查找

//查找
ListNode* LTFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

11、在`pos`位置之后插入数据

//在pos位置之后插入数据
void LTInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newNode = LTBuyNode(x);
	//pos newNode pos->next（头结点）
	newNode->next = pos->next;
	newNode->prev = pos;

	pos->next->prev = newNode;//改变头结点的指向
	pos->next = newNode;
}

测试代码：

#include "List.h"

void test()
{
	ListNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushFront(plist, 3);
	LTPrint(plist);
	ListNode* find = LTFind(plist, 2);
	LTInsert(find, 3);
	LTInsert(find, 5);
	LTPrint(plist);
}

int main()
{
	test();

	return 0;
}

测试结果：
在这里插入图片描述
这里插入pos位置之前的数据，和在pos之后插入数据基本相同，这里就不再过多赘述。

12、删除`pos`位置的结点

//删除pos位置的结点
void LTErase(ListNode* pos)
{
	assert(pos);

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}

测试代码：

#include "List.h"

void test()
{
	ListNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushFront(plist, 3);
	LTPrint(plist);
	ListNode* find = LTFind(plist, 2);
	LTErase(find);
	LTPrint(plist);
}

int main()
{
	test();

	return 0;
}

测试结果：
在这里插入图片描述

13、销毁链表

//销毁链表
void LTDestroy(ListNode* phead)
{
	ListNode* pcur = phead;
	while (pcur != phead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

结果：
在这里插入图片描述
从内存可以看出链表已经彻底销毁了。

二、源代码

List.h

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

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;
//创建新的结点
ListNode* LTBuyNode(LTDataType x);
//双向链表的初始化
ListNode* LTInit();
//双向链表的打印
void LTPrint(ListNode* phead);
//尾插
void LTPushBack(ListNode* phead, LTDataType x);
//头插
void LTPushFront(ListNode* phead, LTDataType x);
//判空
bool LTEmpty(ListNode* phead);
//尾删
void LTPopBack(ListNode* phead);
//头删
void LTPopFront(ListNode* phead);
//查找
ListNode* LTFind(ListNode* phead, LTDataType x);
//在pos位置之后插入数据
void LTInsert(ListNode* pos, LTDataType x);
//删除pos位置的结点
void LTErase(ListNode* pos);
//销毁链表
void LTDestroy(ListNode* phead);

List.c

#include "List.h"

//创建新的结点
ListNode* LTBuyNode(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)
	{
		perror("malloc fail!");
		return 1;
	}
	newNode->data = x;
	newNode->prev = newNode->next = newNode;

	return newNode;
}
//双向链表的初始化
ListNode* LTInit()
{
	ListNode* phead = LTBuyNode(-1);

	return phead;
}
//双向链表的打印
void LTPrint(ListNode* phead)
{
	ListNode* pcur = phead->next;//head指向第一个结点
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newNode = LTBuyNode(x);
	//newNode phead->prev(尾结点) phead
	newNode->prev = phead->prev;//新结点的前一个结点是尾结点
	newNode->next = phead;//新节点的下一个结点是头结点

	phead->prev->next = newNode;//链接旧尾结点与新尾结点
	phead->prev = newNode;//更换头节点指向的尾结点
}
//头插
void LTPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newNode = LTBuyNode(x);
	newNode->next = phead->next;//将新节点与旧的第一结点链接起来
	newNode->prev = phead;//将新节点与头节点链接起来

	phead->next->prev = newNode;//改变旧的第一个结点的prev指针的指向
	phead->next = newNode;//改变头节点的next指针的指向
}
//判空
bool LTEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead;//只剩下一个结点的时候链表为空
}
//尾删
void LTPopBack(ListNode* phead)
{
	assert(!LTEmpty(phead));
	ListNode* del = phead->prev;
	//del del->prev phead
	phead->prev = del->prev;
	del->prev->next = phead;

	free(del);
	del = NULL;
}
//头删
void LTPopFront(ListNode* phead)
{
	assert(!LTEmpty(phead));
	ListNode* del = phead->next;
	//del phead del->next
	phead->next = del->next;
	del->next->prev = phead;

	free(del);
	del = NULL;
}
//查找
ListNode* LTFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在pos位置之后插入数据
void LTInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newNode = LTBuyNode(x);
	//pos newNode pos->next（头结点）
	newNode->next = pos->next;
	newNode->prev = pos;

	pos->next->prev = newNode;//改变头结点的指向
	pos->next = newNode;
}
//删除pos位置的结点
void LTErase(ListNode* pos)
{
	assert(pos);

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}
//销毁链表
void LTDestroy(ListNode* phead)
{
	ListNode* pcur = phead;
	while (pcur != phead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

总结：
以上就是本期博客分享的全部内容啦！如果觉得文章还不错的话可以三连支持一下，你的支持就是我前进最大的动力！
技术的探索永无止境! 道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～

【数据结构】双向链表

目录

一、双向链表

1、概念与结构

2、双向链表结构的定义

3、创建新节点

4、双向链表的初始化

5、双向链表的打印

6、尾插

7、头插

8、尾删

9、头删

10、查找

11、在`pos`位置之后插入数据

12、删除`pos`位置的结点

13、销毁链表

二、源代码

网站公告

今日签到

热门文章

最新发布

【数据结构】双向链表

目录

一、双向链表

1、概念与结构

2、双向链表结构的定义

3、创建新节点

4、双向链表的初始化

5、双向链表的打印

6、尾插

7、头插

8、尾删

9、头删

10、查找

11、在pos位置之后插入数据

12、删除pos位置的结点

13、销毁链表

二、源代码

网站公告

今日签到

热门文章

最新发布

11、在`pos`位置之后插入数据

12、删除`pos`位置的结点