双向带头循环链表的实现

双向带头循环链表是结构最复杂的链表，但是操作最简单

其基本结构如下：

typedef int Datatype;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	Datatype data;
}ListNode;

双向带头循环链表的结点由三个部分组成：

1.指向前一个结点的指针

2.指向后一个结点的指针

3.此结点的数据

与单链表相比，双向带头循环链表具有的优点：

双向带头循环链表的结点存储有前一个结点的地址，因此在尾部删除元素要比单链表方便。在尾删时不用从前向后遍历寻找倒数第二个结点。

双向带头循环链表在查找尾结点时也不用遍历查找，因为其头结点的prev指向尾结点，这也是循环的体现

缺点：

与单链表相比，双向带头循环链表需要存储前一个结点的地址，占用空间更大

双向带头循环链表的基本操作：

1：删除头部元素

void ListPopFront(ListNode* head)
{
	assert(head);
	assert(head->next != head);//防止误删哨兵位结点
	ListNode* pop = head->next;
	ListNode* next = pop->next;
	head->next = next;
	next->prev = head;
	free(pop);
}

如果只有2个结点，则pop为第二个结点，next为第三个结点（就是head）。这样的话头删也是可以实现的，删除之后就只剩下了一个哨兵位

2：删除尾部元素

void ListPopTail(ListNode* head)
{
	assert(head && head->next != head);
	ListNode* tail = head->prev;
	ListNode* newtail = tail->prev;
	head->prev = newtail;
	newtail->next = head;
	free(tail);
}

3：查找结点的位置

ListNode* SeekPos(ListNode* head, Datatype pos)
{
	assert(head && head->next != head);
	ListNode* cur = head->next;
	while (cur!=head)
	{
		if (cur->data == pos)
			return cur;
		cur = cur->next;
	}
    return NULL;
}

这里需要注意的是遍历循环链表的结束条件是cur==head

4:指定位置前插入结点

ListNode* BuyNode(Datatype x)
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	tmp->data = x;
	return tmp;
}
void ListInsert(ListNode* pos, Datatype x)
{
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyNode(x);
	prev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
	newnode->prev = prev;
}

可以复用该函数，实现头插和尾插

void TestList()
{
	ListNode* phead=(ListNode*)malloc(sizeof(ListNode));
	phead->next = phead;
	phead->prev = phead;
	ListInsert(phead->next, 1);//头插
	ListInsert(phead, 2);//尾插
}

5：删除指定位置的结点

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

同样可以复用该函数，实现头删和尾删

void TestList()
{
	ListNode* phead=(ListNode*)malloc(sizeof(ListNode));
	phead->next = phead;
	phead->prev = phead;
	ListErase(phead->next);//头删
	ListErase(phead->prev);//尾删
}