【双向链表】数据结构双向链表的实现

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

前言
前一期我们已经学习过单链表了今天我们来学习链表中的双向链表

1.概念以及结构

双向链表也叫双链表是链表的一种它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

在这里插入图片描述

2.双向链表结点结构体

双向链表每个结点除了存储数据data外还有两个指针记录上一个结点和下一个结点的地址分别是前驱指针prev和后继指针next所以双向链表结点定义如下

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

3.接口实现

我们主要进行以下操作

//动态申请一个结点
LTNode* BuyListNode(LTDataType x);
//初始化链表
LTNode* LTInit();
//打印链表
void LTPrint(LTNode* phead);
// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 双向链表尾删
void LTPopBack(LTNode* phead);
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);
// 双向链表头删
void LTPopFront(LTNode* phead);
// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

3.1动态申请一个结点

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

思路

这一步跟之前单链表的操作类似大家可以看之前的讲解

3.2初始化链表

LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

思路

我们进行初始化之前需要清楚我们结构的状态我们这里写的是带头结点的双向循环链表开始时我们先定义一个phead指针它的next指向自己prev也是指向自己头结点和尾结点指向NULL空的话就不能满足我们循环的需求。

3.3打印链表

void LTPrint(LTNode* phead)
{
	assert(phead);

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

思路

原理同单链表的操作基本一致

3.4双向链表尾插

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;

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

思路

分为两种情况
链表为空那插入的结点既是尾结点也是头结点；
链表不为空将新结点和链表通过前驱指针prev和后继指针next连接起来并将尾结点改为新插入的结点让新节点与最后一个节点进行双层逻辑关系；

3.5 双向链表尾删

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);  // 判空

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;//作为新的尾结点

	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
}

思路

链表为空不操作先断言
链表结点大于1保存尾结点新尾结点等于原尾结点的上一个结点然后释放保存的尾结点的内存；

3.6双向链表头插

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

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

思路

跟尾插一样
链表为空那插入的结点既是头结点也是尾结点；
链表不为空将新结点和链表通过前驱指针prev和后继指针next连接起来并将头结点改为新插入的结点一定要注意链接顺序；

3.7双向链表头删

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); // 判空

	LTNode* first = phead->next;
	LTNode* second = first->next;

	free(first);

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

思路

思路跟之前的尾删大差不差具体对照下图第二张图就是判断删空的情况

在这里插入图片描述

3.8双向链表查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

这跟我们单链表的情况也基本一样大家可以对照学习

3.9双向链表在pos的前面进行插入

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

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

思路

还是分为两种情况考虑
当插入的位置为第一个位置时这时就相当于我们的头插操作
第二种就是正常的插入的操作具体结合下图

3.10双向链表删除pos位置的结点

void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	free(pos);

	prev->next = next;
	next->prev = prev;
}