数据结构与算法 --- 双向链表

前言

本次实现的双向链表，全名叫双向带头循环链表，使用C语言实现。
总体结构如下：

所以基于上图本次实现的双向链表成员有三：data数据域，prve指向前一个节点的指针域，next指向下一个节点的指针域。

// 重命名方便存储多种类型的数据
typedef int Datetype;

// 实现双向链表，全称双向带头循环链表
typedef struct ListNode
{
	struct ListNode* next;           // 指向下一个节点的指针
	struct ListNode* prve;           // 指向前一个节点的指针
	Datetype data;                   // 存储的数据
}LNnode;

节点的结构就是双向链表的结构，这一点和单链表是一样的。

一、初始化和销毁

1.初始化

对于双向链表的初始化，不和单链表一样初始化为空，由于自带一个头节点，所以初始状态就只有一个头节点，并且也要满足双向而且循环的特点。
如下图：

初始状态直接自己指向自己即可。

// 申请节点
LNnode* LNBuynode(Datetype x)
{
	// 开一个节点大小的空间
	LNnode* newnode = (LNnode*)malloc(sizeof(LNnode));
	if (newnode == NULL)
	{
		// 提示错误
		perror("malloc!!");
		// 强制不正常退出
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prve = newnode;
	return newnode;
}

在初始化函数中调用上述函数即可。

初始化函数1：

// 初始化(1)
void LNInit(LNnode** pphead)
{
	// 传过来的pphead不能为空
	assert(pphead);
	*pphead = LNBuynode(-1);
}

初始化函数2：

//初始化(2)
LNnode* LNInit()
{
	LNnode* phead = LNBuynode(-1);
	return phead;
}

对比上述两种函数，函数一是传递一个头节点过去，进行初始化；而函数二是直接进行初始化操作，本次使用的是函数二进行初始化。

2.销毁

双向链表的销毁就是对所有的节点进行销毁，头节点也不例外。

// 销毁链表
// 销毁链表是所有节点都销毁，头节点也要销毁
void LNdestroy(LNnode* phead)
{
	assert(phead);

	// 标记头节点的下一个节点
	LNnode* pcur = phead->next;

	// 销毁除头节点的其他节点
	while (pcur != phead)
	{
		LNnode* pnext = pcur->next;
		free(pcur);
		pcur = pnext;
	}

	// 销毁头节点
	free(phead);
	phead = NULL;
}

不过销毁顺序有点不同，首先销毁除开头节点的其他节点，因为在这一步需要将头节点视作遍历条件，待节点销毁完毕之后再销毁头节点即可。

二、增删改查

1.尾插

尾插即在链表的最后一个节点之后再插入新节点，插入示意图如下：

// 尾插
void LNpush_back(LNnode* phead, Datetype x)
{
	assert(phead);

	// 首先申请节点
	LNnode* newnode = LNBuynode(x);

	// 改变各个节点中指针的指向,需要注意指向的顺序
	// 优先修改对链表没有影响的指针指向
	// 三个指针：phead，phead->prve(尾节点)，newnode(尾插节点)
	newnode->next = phead;
	newnode->prve = phead->prve;

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

2.头插

头插是在链表的第一个有效节点之前插入数据，并非是在头节点之前插入数据，插入示意图如下：

// 头插
// 头插是插入到第一个有效节点之前，并非头节点之前
void LNpush_front(LNnode* phead, Datetype x)
{
	assert(phead);

	// 申请节点
	LNnode* newnode = LNBuynode(x);

	// 改变指针指向
	// 优先更改对链表整体结构没有影响的指针
	// 三个指针：phead，phead->next(第一个节点)，newnode
	newnode->prve = phead;
	newnode->next = phead->next;

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

3.尾删

删除示意图如下：

// 尾删
void LNpop_back(LNnode* phead)
{
	// 首先对List判空
	// 链表非空才可以删除
	assert(!LNempty(phead));

	// 标记将要删除的尾节点
	LNnode* pdelete = phead->prve;

	// 改变指针指向
	// phead，pdelete(删除的尾节点)，pdelete->prve(尾节点的前一个节点)
	pdelete->prve->next = phead;
	phead->prve = pdelete->prve;

	// 销毁节点
	free(pdelete);
	pdelete = NULL;
}

4.头删

删除示意图如下：

// 头删
void LNpop_front(LNnode* phead)
{
	// 首先对List判空
	// 链表非空才可以删除
	assert(!LNempty(phead));

	// 标记将要删除的头节点
	LNnode* pdelete = phead->next;

	// 改变指针指向
	// phead，pdelete(删除的第一个节点)，pdelete->next(第二个节点)
	pdelete->next->prve = phead;
	phead->next = pdelete->next;

	// 销毁节点
	free(pdelete);
	pdelete = NULL;
}

5.pos位置之后 / 之前插入

本函数需要配合查找函数使用，pos位置之后插入（pos之前插入与之后插入高度相似）示意图如下：

pos位置之后差插入：

// 指定位置之后插入
void LNinsert_back(LNnode* pos, Datetype x)
{
	assert(pos);

	// 创建将要插入的新节点
	LNnode* newnode = LNBuynode(x);

	// 改变指针指向
	// pos，newnode，pos->next(pos的下一个节点)
	newnode->next = pos->next;
	newnode->prve = pos;

	pos->next->prve = newnode;
	pos->next = newnode;
}

pos位置之前插入：

// 指定位置之前插入
void LNinsert_front(LNnode* pos, Datetype x)
{
	assert(pos);

	// 创建将要插入的新节点
	LNnode* newnode = LNBuynode(x);

	// 改变指针指向
	// pos，newnode，pos->prve(pos的前一个节点)
	newnode->next = pos;
	newnode->prve = pos->prve;

	pos->prve->next = newnode;
	pos->prve = newnode;
}

6.删除pos位置节点

删除示意图如下：

// 删除指定位置的数据
void LNerase(LNnode* pos)
{
	assert(pos);

	// 改变指针指向
	// pos->next，pos->prve

	pos->next->prve = pos->prve;
	pos->prve->next = pos->next;
}

7.查找指定数据的节点

// 查找指定元素位置
LNnode* LNfind(LNnode* phead,Datetype x)
{
	assert(phead);

	// 标记第一个节点，方便后续遍历操作
	LNnode* pcur = phead->next;

	// 遍历
	// 遍历条件：不等于头节点继续遍历，一旦等于头节点则表示一轮遍历完毕
	while (pcur != phead)
	{
		// 找到了
		if (pcur->data == x)
		{
			// 找到返回其位置
			return pcur;
		}
		pcur = pcur->next;
	}
	
	// 没找到返回NULL
	return NULL;
}

三、其他

1.打印

// 打印
void lNPrint(LNnode* phead)
{
	// 首先打印数据只需要从第一个节点（不算头节点）开始，所以标记此节点为pcur
	LNnode* pcur = phead->next;

	// 其次打印结束条件等于头节点即可，因为链表本身是一个循环结构，需要规定中止条件
	while (pcur != phead)
	{
		// 打印每个节点的数据
		printf("%d -> ", pcur->data);
		// 当前节点数据打印完之后使pcur指向下一个节点，继续打印，直到遇见phead
		pcur = pcur->next;
	}
	printf("\n");
}

2.判空

双向链表为空，即只有一个头节点的情况下。

// 判空
// 若链表为空，则返回true，反之false
bool LNempty(LNnode* phead)
{
	// 双向链表为空即只剩下一个头节点
	assert(phead);
	return phead->next == phead;
}

四、总结

对比单链表，双向链表在实现方面要简单得多，只需要改变指针得指向即可，例如尾节点就直接能表示为phead->prve(这里phead代表头节点)，并且也能完成单链表不能完成得操作，即从尾节点遍历到第一个节点的操作，并且大多数函数的时间复杂度都是为O(1)。