双向循环链表

1.概念

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

视频讲解：小破站，搜索 Yi_Xiao8 数据结构系列视频

2.数据结构

typedef int ElemType;

//双链表的结点类型
typedef struct DcLinkNode{
	ElemType val;
	DcLinkNode* prev;
	DcLinkNode* next;
}DcLinkNode;

3.生成结点

DcLinkNode* BuyNode(ElemType elem,DcLinkNode* prev,DcLinkNode* next)
{
	DcLinkNode* ptr = (DcLinkNode*)calloc(sizeof(DcLinkNode), 1);
	assert(ptr != NULL);
	ptr->val = elem;
	ptr->next = next;
	ptr->prev = prev;
	return ptr;
}

4.释放结点

void FreeNode(DcLinkNode* p)
{
	free(p);
	p = NULL;
}

5.初始化双循环链表

//初始化双循环链表
DcLinkNode* InitDcLinkList()
{
	DcLinkNode* ptr = BuyNode(-1, NULL, NULL);
	ptr->next = ptr;
	ptr->prev = ptr;
	return ptr;
}

6.插入一个结点

//在pos的前面加入一个新的结点
void Insert(DcLinkNode* pos, ElemType elem)
{
	if (pos == NULL) { return; }
	DcLinkNode* ptr = BuyNode(elem, pos->prev, pos);
	pos->prev->next = ptr;
	pos->prev = ptr;
}
//在头部插入一个结点
void PushFront(DcLinkNode* head, ElemType elem)
{
	if (head == NULL) { return ; }
	Insert(head->next, elem);
}
//在尾部插入一个结点
void  PushBack(DcLinkNode* head, ElemType elem)
{
	if (head == NULL) { return; }
	Insert(head, elem);
}

7.查询一个结点

//查询一个结点
DcLinkNode* FindValue(DcLinkNode* head, ElemType elem)
{
	if (head == NULL) { return NULL; }
	DcLinkNode* ptr = head->next;
	for (; ptr != head && ptr->val != elem; ptr = ptr->next);
	return ptr == head ? NULL : ptr;
}

8.删除一个结点

//删除一个结点
void Delete(DcLinkNode* head, DcLinkNode* ptr)
{
	if (head == NULL || ptr == NULL || ptr == head) { return; }
	ptr->prev->next = ptr->next;
	ptr->next->prev = ptr->prev;
	FreeNode(ptr);
	ptr = NULL;
}
//按照值删除
void DeleteValue(DcLinkNode* head, ElemType elem)
{
	if (head == NULL) { return ; }
	DcLinkNode* ptr = FindValue(head, elem);
	Delete(head, ptr);
	ptr = NULL;
}
//头部删除
void PopFront(DcLinkNode* head)
{
	if (head == NULL || head->next == NULL) { return; }
	Delete(head, head->next);
}
//尾部删除
void PopBack(DcLinkNode* head)
{
	//错误示范 双循环链表不会出现next 为空
	//if (head == NULL || head->next == NULL) { return; } 
	if (head == NULL || head->next == head) { return; }
	Delete(head, head->prev);
}

9.打印双循环链表

//打印双向循环链表
void Print(DcLinkNode* head)
{
	if (head == NULL) { return; }
	DcLinkNode* ptr = head->next;
	//for (; ptr != head ; printf("%d ",ptr->val),ptr = ptr->next);
	while (ptr != head)
	{
		printf("%d ", ptr->val);
		ptr = ptr->next;
	}
	printf("\n");
}

10.判断链表是否为空

//判断链表空不空
bool isEmpty(DcLinkNode* head)
{
	return (head != NULL && head->next != head);
}

11.销毁双向循环链表

//销毁双项链表
void Destory(DcLinkNode** head)
{
	if (head == NULL) { return; }
	while (isEmpty(*head))
	{
		PopBack(*head);
	}
	free(*head);
	*head = NULL;
}