// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

3.接口实现。

3.1创建新节点

由于我们的链表是动态增长的链表，因此当我们需要新节点时，我们都要进行malloc，因此我们写一个创建新节点的接口，方便往后接口的实现。

ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

3.2创建返回链表的头结点

这一步就是要给我们的链表创建一个哨兵位的头结点。由于是双向带头循环性，我们让头结点的next和prev指针都指向自己，这样即使只有一个头结点，仍然满足双向循环性。

//创建返回头结点
ListNode* ListCreate()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return  phead;
}

3.3打印链表

//打印链表
void ListPrint(ListNode* phead)
{
	assert(phead);
	//有头结点 cur才是第一个节点 打印时不打印头结点
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n\n");
}

在这里我们打印和单链表一样，唯一有不同的是，双向循环带头链表的终止条件不是cur == NULL，而是cur != phead，当cur等于phead，说明我们已经将链表遍历了一遍。

3.4双向链表查找

这一步也是非常简单的，只需要注意的是我们第一的头结点是不在查找范围内的。因此定义的cur也就是首元素是从phead的next指针开始。最终我们返回的是查找到指针的地址。

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (x == cur->data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

3.5双向链表在pos的前面进行插入

当我们获取pos位置时，我们要在pos位置前进行插入，过程可如下：

1、假设要将d4插入到d1和d2之间，我们首先可以创建一个last节点，保存pos位置的前驱节点。

2、让last节点的next指向d4，让d4的prev指向last。

3、让d4节点的next指向d2，让d2的prev指向d4即可。

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	ListNode* last = pos->prev;
	newnode->prev = last;
	last->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}

3.5.1 头插

特殊情况下：如果pos为首元素地址，那么我们将实现头插功能：

void ListPushFront(ListNode* phead, LTDataType x)
{
	ListInsert(phead->next, x);
}

3.5.2 尾插

如果pos位置为头指针，那么我们将实现尾插功能。

void ListPushBack(ListNode* phead, LTDataType x)
{
	ListInsert(phead, x);
}

3.6双向链表删除pos位置的节点

假设我们需要删除d2位置的节点，过程如下：

1、我们需要创建一个last指针保存pos位置的prev节点。

2、我们只需让last节点的next指向pos位置的next节点，再让pos位置的节点的下一个节点的prev指针指向last指针。

3、最后在释放掉pos位置的指针，并置空。

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* last = pos->prev;
	last->next = pos->next;
	(pos->next)->prev = last;
	free(pos);
	pos = NULL;
}

3.6.1 尾删

当pos位置是尾结点时，其功能就相当于尾删，找尾结点可用哨兵位的头结点的prev寻找。

void ListPopBack(ListNode* phead)
{
	ListErase(phead->prev);
}

3.6.2 头删

当pos位置为首元素地址时，其功能就相当于头删，找头结点可用哨兵位的头结点的next寻找。

void ListPopFront(ListNode* phead)
{
	ListErase(phead->next);
}

4.菜单

以下是我自制的一个菜单：

void menu()
{
	printf("*******************欢迎使用双向带头循环链表******************\n");
	printf("*************            1.   尾插            *************\n");
	printf("*************            2.   头插            *************\n");
	printf("*************            3.   尾删            *************\n");
	printf("*************            4.   头删            *************\n");
	printf("*************            5.查询pos位置        *************\n");
	printf("*************            6.在pos位前插入元素x  *************\n");
	printf("*************            7.删除pos位置的元素   *************\n");
	printf("*************            8.打印链表           ************* \n");
	printf("*************           -1.退出链表           ************* \n");
	printf("***********************************************************\n");
}
int main()
{
	ListNode* pList = ListCreate();
	menu();
	int option = -1;
	do
	{
		printf("请输入选项:> ");
		scanf("%d", &option);
		if (option == 1)
		{
			int x = 0;
			printf("请输入你要尾插的元素:>");
			scanf("%d",&x);
			ListPushBack(pList, x);
		}
		else if (option == 2)
		{
			int x = 0;
			printf("请输入你要头插的数字:>");
			scanf("%d", &x);
			ListPushFront(pList, x);
		}
		else if (option == 3)
		{
			//尾删
			ListPopBack(pList);
		}
		else if (option == 4)
		{
			//头删
			ListPopFront(pList);
		}
		else if (option == 5)
		{
			int x = 0;
			printf("请输入你要查找的值x:>");
			scanf("%d", &x);
			ListNode* pos = ListFind(pList, x);
			if (pos != NULL)
			{
				printf("存在数字%d\n", x);
			}
			else
			{
				printf("未找到数字%d\n", x);
			}
		}
		else if (option == 6)
		{
			int x = 0;
			int y = 0;
			printf("请分别输入pos值x和pos前所插入的值y:>");
			scanf("%d %d", &x, &y);
			ListNode* pos = ListFind(pList, x);
			if (pos != NULL)
			{
				ListInsert(pos, y);
			}
			else
			{
				printf("该链表不存在%d\n", x);
			}
		}
		else if (option == 7)
		{
			int x = 0;
			printf("请输入要删除pos位置的值:>");
			scanf("%d", &x);
			ListNode* pos = ListFind(pList, x);
			ListErase(pos);
		}
		else if (option == 8)
		{
			ListPrint(pList);
		}
	} while (option != -1);
	ListDestory(pList);
	return 0;
}