前言

上篇文章我们介绍了链表的几种类型并且完整的讲解了单链表的实现过程，这期我们来介绍堪称链表中的战斗链表，那就是带头双向循环链表，众所周知，带头双向循环链表结构是链表中最为复杂的，但是代码实现起来也会复杂吗？答案是并不会，代码实现起来比单链表简单！

一、双向循环链表的分类

二、代码的实现

首先我们来看双向带头循环链表的结构图：

 相比于单链表我们可以发现双向带头循环链表结构复杂，但是每一个节点都可以找到之前的节点。下面我们先实现代码的主要功能和代码的结构，代码的结构与单链表的区别在于多了一个指向前一个节点的指针。如图：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DListDateType;
typedef struct DListNode
{
	struct DListNode* next;
	struct DListNode* prev;
	DListDateType data;
}DListNode;

//初始化链表
DListNode* DListNodeInit();
//尾插
void DListNodepushback(DListNode* phead, DListDateType x);
//创建新节点
DListNode* DListBuyNode(DListDateType x);
//打印链表
void DListNodePrint(DListNode* phead);
//头插
void DListNodepushfront(DListNode* phead, DListDateType x);
//尾删
void DListNodepopback(DListNode* phead);
//头删
void DListNodepopfront(DListNode* phead);
//查找
DListNode* DListNodeFind(DListNode* phead,DListDateType x);
//指定位置前插入
void DListNodeInsert(DListNode* pos, DListDateType x);
//指定pos位置删除
void DListNodeEarse(DListNode* pos);
//释放链表
void DListNodeDestroy(DListNode* phead);

与之前一样，我们需要将链表中存储的类型typedef一下，这样方便以后修改，然后我们将带头双向循环链表的名称重命名为DListNode，这样方便后续使用，我们将实现的功能有初始化，创建新节点，头插，尾插，头删，尾删，查找，指定位置前插入，指定位置删除，释放链表，打印链表这样功能。那么就先来实现第一个功能：

DListNode* DListNodeInit()
{
	DListNode* phead = DListBuyNode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

第一个功能是初始化，但是由于我们先使用了创建节点，所以我们一起讲解如图：

DListNode* DListBuyNode(DListDateType x)
{
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

创建一个新节点很简单，malloc开辟一个DListNode的空间，然后判断是否开辟成功，如果开辟失败返回空指针就退出程序并且报错，否则将节点的值给新节点，将newnode->next的指针置为NULL，将newnode->prev的指针置为NULL，然后返回这个新节点。在初始化的时候我们我们只需要创建一个头结点，这个头结点不存储有效值，只有两个指针并且两个指针初始化的时候都指向自己，为什么要指向自己呢？我们可以看到刚才的结构图，当只有一个头结点时也应该满足指向自己，并且这样初始化会给后来功能的实现带来很多的好处。初始化的函数一定要返回头结点，否则后续功能的使用还要用二级指针。

第三个功能尾插：

void DListNodepushback(DListNode* phead, DListDateType x)
{
	assert(phead);
	DListNode* newnode = DListBuyNode(x);
	DListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}

尾插的时候我们要防止有人直接传个空指针过来，这样是没有头结点的我们头节点的创建是放在初始化中所以使用前用指针接收初始化函数返回的头指针即可。尾插我们先创建一个新节点，既然是尾插一定要找尾了，尾怎么找呢？很简单，phead->prev不就是尾吗，prev是指向前一个节点的指针，next是指向后一个节点的指针， 找到尾后我把新节点的地址给刚刚的尾节点，然后将尾节点给新节点指向前一个节点的指针prev，再将新节点给头结点的前一个指针prev，最后将头指针给新节点的next就又变成了双向循环的样式。

第四个功能为打印链表：

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

打印链表肯定是从第一个节点开始打印了，在这里第一个节点不是头结点头结点只负责指向作用也就是哨兵节点所以第一个节点是phead->next，那么该如何控制打印循环条件呢？很简单最后一个节点的下一个节点是头结点，所以只需要让cur不等于头结点就可以，打印完一行链表记得换行即可。

第五个功能为头插：

void DListNodepushfront(DListNode* phead, DListDateType x)
{
	assert(phead);
	DListNode* newnode = DListBuyNode(x);
	DListNode* First = phead->next;
	newnode->next = First;
	First->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

 头插实现起来也很简单，先创建一个新节点，然后我们用First保存第一个节点的地址，让新节点指向刚刚保存的第一个节点，然后将新节点的地址给第一个节点的前一个指针prev，然后将新节点给头结点的next让头节点指向新节点，然后再将新节点的前一个指针prev指向头节点即可。

第六个功能为尾删：

void DListNodepopback(DListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	DListNode* tail = phead->prev;
	DListNode* firsttail = tail->prev;
	free(tail);
	phead->prev = firsttail;
	firsttail->next = phead;

}

尾删的实现需要将尾节点的前一个节点指向头节点，所以我们用firsttail保存尾节点的前一个节点，然后直接释放尾节点，然后将刚刚保存的前一个节点的地址给头结点的前一个节点，然后将头结点给刚刚保存节点的next就完成了尾删。尾删需要注意的是不可以将头节点删掉，否则后续无法插入。当只有一个节点的时候可以删除吗？答案是可以，只有一个节点的时候直接释放这个节点，然后将phead自己给phead->prev，firsttail就是phead，将phead给phead->next与我们初始化的时候相同。

第七个功能为头删：

void DListNodepopfront(DListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	DListNode* First = phead->next;
	DListNode* Second = First->next;
	free(First);
	phead->next = Second;
	Second->prev = phead;
}

 头删与尾删一样，都不可以删除头结点，先将第一个节点保存起来，然后为了等会在释放第一个节点的过程中不会找不到第一个节点以后的节点所以我们将第一个节点的后一个节点的地址给second保存。然后我们释放第一个节点，将第二个节点的地址给头结点的next，然后再将第二个节点的前一个节点指向头结点。同样只有一个节点的时候可以删除吗？答案是可以，这就是双向带头循环链表的好处，只有一个节点的时候将第一个节点给first，第一个节点后是phead头节点，将头结点给second，然后释放第一个节点，将头结点给phead自己，再将phead给头结点的prev同样是指向自己恢复了初始化状态。

第八个功能为查找：

DListNode* DListNodeFind(DListNode* phead, DListDateType x)
{
	DListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

 查找与单链表几乎相同，不同的是我们将第一个节点给cur让cur去遍历，结束条件同理是cur不等于头指针，在这期间找到要找的节点就返回其地址，否则就继续遍历当循环退出时还没找到则返回空指针。

第九个功能为指定位置前插入：此功能可以复用头插尾插使代码更简单。

void DListNodeInsert(DListNode* pos, DListDateType x)
{
	assert(pos);
	DListNode* newnode = DListBuyNode(x);
	DListNode* prev = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
	prev->next = newnode;
	newnode->prev = prev;
}

在指定位置前插入需要判断此位置是否是空指针如果是空指针则不可以插入，创建一个新节点，然后将指定位置的前一个节点给prev保存下来，将指定位置节点的地址给新节点让新节点指向它，然后将新节点 的地址给指定位置节点的前一个指针，再将新节点给指定位置前一个节点的next，最后将指定位置的前一个节点的地址给新节点的前一个指针即可。以下是复用头插尾插代码：

/void DListNodepushfront(DListNode* phead, DListDateType x)
//{
//	DListNodeInsert(phead->next, x);
//}

//void DListNodepushback(DListNode* phead, DListDateType x)
//{
//	DListNodeInsert(phead, x);
//}

 头插的时候要从第一个节点开始，尾插要从头结点开始，因为头结点的前一个节点就是最后一个节点。

第十个功能为指定位置删除：

void DListNodeEarse(DListNode* pos)
{
	assert(pos);
	assert(pos != pos->next);
	DListNode* prev = pos->prev;
	DListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}

指定位置删除的时候位置不能为空指针并且不可以删除头结点。将指定位置的前一个节点用prev保存，然后将指定位置的后一个节点用next保存，这样是为了防止删除位置节点的时候找不到位置节点的前一个节点和后一个节点，如果找不到就不能将前后两个节点连接。直接释放位置节点，然后将刚刚保存的位置节点的后一个节点给刚刚保存的位置的节点的前一个节点的next，然后再将位置节点的前一个节点的地址给位置节点的后一个节点的prev。同样，此功能也可以复用头删尾删，如图：

//void DListNodepopfront(DListNode* phead)
//{
//	DListNodeEarse(phead->next);
//}

//void DListNodepopback(DListNode* phead)
//{
//	DListNodeEarse(phead->prev);
//
//}

 头删的时候要删第一个节点，尾删的时候要删最后一个节点也就是phead->prev.

总结

双向带头循环链表的结构看似复杂，实际上在实现的时候确很简单，比单链表方便很多所以是链表中的“战斗机”！