双向循环链表的讲解及实现（图解+代码/C语言）

本次为大家分享的是双向循环链表的增删查改等系列操作。

一、图解双向循环链表结构

二、分步实现

（1）创建并初始化

一、图解双向循环链表结构

对于单向链表来说，每一个结点由数据块和一个指针域构成，只需要指针域记录下一个结点的位置即可。而双向链表则需要两个指针，对应“双向”，其结点具体结构和结点之间的连接方式如下。

二、分步实现

下面直接逐个上代码，给大家分块演示如何实现一个双向带头循环的链表。

（1）创建并初始化

首先我们需要声明结构体的结构，对于链表的初始化，我们只需要动态申请一个结点作为头结点，让这个哨兵结点头尾相连即可。

// 双链表 // Double Link List  // DLL

typedef int DLLData
typedef struct DLLNode
{
	DLLData data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;


// 链表哨兵结点的创建
ListNode* ListCreate()
{
	ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
	guard->next = guard->prev = guard;
	return guard;
}

（2）链表元素打印

链表的打印相对简单，我们只需要打印出其中的数据即可，为了表示是双向带头循环链表，不同结点之间的数据我们用“<=>”连接表示双向，用phead放在两端表示带头循环。

// 双向链表打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* tmp = phead->next;
	printf("phead<=>");
	while (tmp != phead)
	{
		printf("%d<=>", tmp->data);
		tmp = tmp->next;
	}
	printf("pheadn");
}

（3）头插和尾插

相比与之前学的单向链表，双向循环链表的头插和尾插则简单了许多，对照下面的图。我们传入函数的是哨兵结点phead, phead->next便是头结点，即在phead之后插入结点就是头插；同理，由于链表是循环的，因此在phead之前插入就是尾插。

// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	new_node->data = x;
	new_node->next = phead->next;
	phead->next->prev = new_node;
	phead->next = new_node;
	new_node->prev = phead;
}


// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	new_node->data = x;
	phead->prev->next = new_node;
	new_node->prev = phead->prev;
	phead->prev = new_node;
	new_node->next = phead;
}

（4）判断链表为空

完成了头插尾插，接下来就是头删和尾删了。但是在删除之前我们应该先检查一下我们的链表之中是否还存在结点，当没有结点的时候我们就无法继续删除了。所以我们需要检查一下链表是否为空，为空就是除哨兵节点外没有有效节点了，只有这哨兵结点循环，因此具体实现如下。

// 检查链表为空
bool CheckVoid(ListNode* rhs)
{
	assert(rhs);
	return rhs->next == rhs;
}

（5）头删和尾删

类比之前的头插和尾插，我们很轻松就可以找到头结点和尾结点，那么头删和尾删也就解决了。

// 双向链表头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(!CheckVoid(phead));
	ListNode* new_front = phead->next->next;
	free(phead->next);
	phead->next = new_front;
	new_front->prev = phead;
}

// 双向链表尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(!CheckVoid(phead));
	ListNode* new_tail = phead->prev->prev;
	free(phead->prev);
	phead->prev = new_tail;
	new_tail->next = phead;
}

（6）查找特定元素

和单链表一样我们只需要遍历整个链表即可，但是需要注意的是我们的链表有哨兵结点，而且是循环链表，因此我们需要从phead->next开始遍历，同时当我们遍历遇到phead时，说明已经找完了整个链表都没有对应元素，要在此设置退出值。

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* tmp = phead->next;
	while (tmp != phead)
	{
		if (tmp->data == x)
			return tmp;
		tmp = tmp->next;
	}
	return NULL;
}

（7）删除特定元素

我们删除元素是基于查找函数完成的，首先通过查找函数找到对应结点，向删除函数传入该结点，由于我们是双向链表，因此只需要将找到的结点pos的前后结点连接并释放pos结点即可。

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

（8）特定元素前插入

在此选择的是在特定元素pos之前插入，想改成之后插入也十分简单，同样是和查找函数共同使用，找到之后传入pos结点和数据值即可。

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* front = pos->prev;
	ListNode* new_node = BuyNewnode(x);
	front->next = new_node;
	new_node->next = pos;
	pos->prev = new_node;
	new_node->prev = front;
}

（9）链表销毁

链表销毁只需要遍历链表逐个释放即可，可以先释放其他节点然后跳出循环释放哨兵结点，也可以将phead->next设置为NULL，成为一个伪单链表，然后循环释放所有结点。此处使用后者实现。

// 双向链表销毁
void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* tmp = phead->next, *node = phead->next;
	phead->next = NULL;
	while (tmp)
	{
		node = tmp->next;
		free(tmp);
		tmp = node;
	}
}

三、优化及整体代码

当我们完成了插入函数的在之后，对于头插和尾插，直接调用函数即可，头插是在front前插入，尾插是在phead前插入。（函数声明和结构体声明等放在头文件中即可）

#include"Double ListNode.h"

// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
	guard->next = guard->prev = guard;
	return guard;
}

// 创建一个新的结点
ListNode* BuyNewnode(LTDataType x)
{
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	new_node->data = x;
	return new_node;
}

// 双向链表销毁
void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* tmp = phead->next, *node = phead->next;
	phead->next = NULL;
	while (tmp)
	{
		node = tmp->next;
		free(tmp);
		tmp = node;
	}
}

// 双向链表打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* tmp = phead->next;
	printf("phead<=>");
	while (tmp != phead)
	{
		printf("%d<=>", tmp->data);
		tmp = tmp->next;
	}
	printf("pheadn");
}

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead, x);
}

// 双向链表尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(!CheckVoid(phead));
	ListErase(phead->prev);
}

// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

// 双向链表头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(!CheckVoid(phead));
	ListErase(phead->next);
}

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* tmp = phead->next;
	while (tmp != phead)
	{
		if (tmp->data == x)
			return tmp;
		tmp = tmp->next;
	}
	return NULL;
}

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* front = pos->prev;
	ListNode* new_node = BuyNewnode(x);
	front->next = new_node;
	new_node->next = pos;
	pos->prev = new_node;
	new_node->prev = front;
}

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

// 检查链表为空
bool CheckVoid(ListNode* rhs)
{
	assert(rhs);
	return rhs->next == rhs;
}