[数据结构与算法]带头节点的双向循环链表（C语言）

概念：双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同，双向链表也有带头结点结构和不带头结点结构两种，带头结点的双向链表更为常用；另外，双向链表也可以有循环和非循环两种结构，循环结构的双向链表更为常用。

接下来来实现一种最为常用的带头节点的双向循环链表。类似与如下图的结构：

1.初始化：

首先得给出每个节点的结构，需要借助结构体：

typedef int DataType;
typedef struct ListNode{
	struct ListNode *prev;//前驱指针
	DataType val;//数值域
	struct ListNode *next;//后继指针
}ListNode;

?以下代码链表的所有节点存储位置都是在堆上的，所以一开始先给出一个ListNode类型的指针，给其赋值为空，再通过初始化让这个指针指向在堆上申请出来的链表的头节点，具体代码如下：

ListNode *pplist = NULL;
pplist = ListCreate();

ListNode* ListCreate(){//创建头节点
	ListNode *pos = BuyListNode(0);//调用创建一个节点的函数，拿到新申请出来的节点的地址
	pos->prev = pos;//前驱指针指向自己
	pos->next = pos;//后继指针指向自己
	return pos;//返回该头节点的地址
}
ListNode* BuyListNode(DataType x){//创建一个节点
	ListNode *pos = (ListNode *)malloc(sizeof(ListNode));//在堆上申请一个节点
	if (pos == NULL){//判断是否申请成功
		perror("malloc");//输出错误信息
		exit(0);//退出程序
	}
	pos->prev = NULL;//给新申请的节点的前驱指针赋值为空
	pos->val = x;//给新申请的节点数值域赋值
	pos->next = NULL;//给新申请的节点的后继指针赋值为空
	return pos;//返回新申请的节点的地址
}

创建头节点的时候可以改写为传入二级指针（根据自己爱好），但是在申请一个单独的节点的时候，一般按照上述有返回值的写法，因为让哪个指针指向新申请的节点是不能确定的。还要注意一点，头节点的数据域可以不给值（在这段代码中，我给的是0），而且头节点的两个指针域指向自身，如下图:

2. 初始化完成后，就可以进行双向循环链表的增、删、改、查操作了。

头插：头插就是把新申请的节点连接在头节点之后，注意不要着急断开原来的链表，应该先把新申请的节点的指针域赋值好之后，在断开原来的链表，防止原来的数据丢失。具体操作如下代码：

void ListPushFront(ListNode* plist, DataType x){//头插
	assert(plist);
	ListNode *pos = BuyListNode(x);//先获取新申请的节点的地址
	pos->prev = plist;//让新申请的节点的前驱指针指向头节点
	pos->next = plist->next;//让新申请的头节点的后继指针指向原链表中头节点的下一个节点
	plist->next->prev = pos;//原链表中头节点的下一个节点的前驱指针指向新申请的节点
	plist->next = pos;//头节点的后继指针指向新申请的节点
}

上一篇博客（不带头结点的单链表）中，头插需要传递二级指针，这里为什么不传二级指针呢？因为此时头指针的指向不会改变，永远指向头节点（除非链表销毁），所以传递一级指针就可以找到链表的头节点的前驱指针和后继指针，此时只需要修改这两个指针的指向。

下图中默认原链表中头节点后有节点，调用函数后，形成了临时变量plist，它和pplist一样指向头节点，此时只需要通过plist找到头节点即可。

头删:?删除头节点后的第一个节点，需要注意先记录下这个节点的位置，用于释放空间，具体代码如下：

void ListPopFront(ListNode* plist){//头删
	assert(plist);
	if (plist->prev == plist){
		printf("没有元素\n");
		return;
	}
	ListNode* cur = plist->next;//记录头节点后的节点的位置
	plist->next = cur->next;//头节点的后继指针指向原链表中头节点后的第二个节点
	cur->next->prev = plist;//让头节点后第二个节点的前驱指针指向头节点
	free(cur);//释放空间
}

尾删、尾插的代码逻辑和上述代码类似，不在赘述。

查找：从头节点后第一个节点开始找，遍历整个链表。退出条件为:cur==plist。

ListNode* ListFind(ListNode* plist, DataType x){//查找
	assert(plist);
	ListNode *cur = plist->next;//从第一个节点开始查找
	while (cur!=plist){//把整个链表遍历一遍
		if (cur->val==x){
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

写完这些后，还有两个函数可以实现，就是在任意位置之前插入和删除任意位置的节点，当写完这两个函数后，就会发现：头插、尾插、头删、尾删都可以用这两个函数一次实现，那么双向循环链表的删除和插入操作其实就只用实现两个函数就可以了，完整代码以及测试结果如下所示(采用多文件):

1.ListNode.h

#include <stdio.h>
#include <windows.h>
#include <assert.h>
typedef int DataType;
typedef struct ListNode{
	struct ListNode *prev;//前驱指针
	DataType val;//数值域
	struct ListNode *next;//后继指针
}ListNode;
extern ListNode* ListCreate();
extern ListNode* BuyListNode(DataType x);
extern void ListPushFront(ListNode* plist, DataType x);
extern void ListPopFront(ListNode* plist);
extern void ListPushBack(ListNode* plist, DataType x);
extern void ListPopBack(ListNode* plist);
extern void ListDestory(ListNode** plist);
extern void ListInsert(ListNode* pos, DataType x);
extern void ListErase(ListNode* pos);
extern void ListPrint(ListNode* plist);
extern ListNode* ListFind(ListNode* plist, DataType x);

2.ListNode.c

#include "ListNode.h"
ListNode* ListCreate(){//创建头节点
	ListNode *pos = BuyListNode(0);//调用创建一个节点的函数，拿到新申请出来的节点的地址
	pos->prev = pos;//前驱指针指向自己
	pos->next = pos;//后继指针指向自己
	return pos;//返回该头节点的地址
}
ListNode* BuyListNode(DataType x){//创建一个节点
	ListNode *pos = (ListNode *)malloc(sizeof(ListNode));//在堆上申请一个节点
	if (pos == NULL){//判断是否申请成功
		perror("malloc");//输出错误信息
		exit(0);//退出程序
	}
	pos->prev = NULL;//给新申请的节点的前驱指针赋值为空
	pos->val = x;//给新申请的节点数值域赋值
	pos->next = NULL;//给新申请的节点的后继指针赋值为空
	return pos;//返回新申请的节点的地址
}
void ListPushFront(ListNode* plist, DataType x){//头插
	assert(plist);
	/*ListNode *pos = BuyListNode(x);//先获取新申请的节点的地址
	pos->prev = plist;//让新申请的节点的前驱指针指向头节点
	pos->next = plist->next;//让新申请的头节点的后继指针指向原链表中头节点的下一个节点
	plist->next->prev = pos;//原链表中头节点的下一个节点的前驱指针指向新申请的节点
	plist->next = pos;*///头节点的后继指针指向新申请的节点
	ListInsert(plist->next, x);
}
void ListPopFront(ListNode* plist){//头删
	assert(plist);
	if (plist->prev == plist){
		printf("没有元素\n");
		return;
	}
	/*ListNode* cur = plist->next;//记录头节点后的节点的位置
	plist->next = cur->next;//头节点的后继指针指向原链表中头节点后的第二个节点
	cur->next->prev = plist;//让头节点后第二个节点的前驱指针指向头节点
	free(cur);*///释放空间
	ListErase(plist->next);
}
void ListPopBack(ListNode* plist){//尾删
	assert(plist);
	if (plist->prev == plist){
		printf("没有元素");
		return;
	}
	/*ListNode *cur = plist->prev;
	cur->prev->next = plist;
	plist = cur->prev;
	free(cur);*/
	ListErase(plist->prev);
}
void ListPushBack(ListNode* plist, DataType x){//尾插
	assert(plist);
	/*ListNode *pos = BuyListNode(x);
	pos->prev = plist->prev;
	pos->next = plist;
	plist->prev->next = pos;
	plist->prev = pos;*/
	ListInsert(plist, x);
}
ListNode* ListFind(ListNode* plist, DataType x){//查找
	assert(plist);
	ListNode *cur = plist->next;//从第一个节点开始查找
	while (cur!=plist){//把整个链表遍历一遍
		if (cur->val==x){
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void ListInsert(ListNode* pos, DataType x){//任意位置之前插入
	assert(pos);
	ListNode *cur = BuyListNode(x);
	cur->prev=pos->prev;
	cur->next =pos ;
	pos->prev->next = cur;
	pos -> prev = cur;
}
void ListErase(ListNode* pos){//任意位置删除
	assert(pos);
	if (pos->prev == pos){
		printf("没有元素\n");
		return;
	}
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}
void ListPrint(ListNode* plist){//打印
	assert(plist);
	if (plist->prev == plist){
		printf("没有元素\n");
		return;
	}
	ListNode *cur = plist->next;
	while (cur!=plist){
		printf("->%d", cur->val);
		cur = cur->next;
	}
	printf("\n");
}
void ListDestory(ListNode** plist){//销毁
	assert(plist);
	assert(*plist);
	ListNode *cur = (*plist)->next;
	while (cur!=*plist){
		(*plist)->next = cur->next;
		free(cur);
		cur = (*plist)->next;
	}
	free(*plist);
	*plist = NULL;
}

3.main.c

#include "ListNode.h"
int main(){
	ListNode *pplist = NULL;
	pplist = ListCreate();
	ListPushFront(pplist, 6);
	ListPushBack(pplist, 9);
	ListPushFront(pplist, 7);
	ListPushBack(pplist, 8);
	ListPrint(pplist);
	ListPopFront(pplist);
	ListPopBack(pplist);
	ListPrint(pplist);
	ListInsert(ListFind(pplist, 6),96);
	ListPrint(pplist);
	ListErase(ListFind(pplist, 96));
	ListPrint(pplist);
	system("pause");
	return 0;
}

?