typedef int ListDataType;//將ListDataType先定義為int類型，根據(jù)需要可以改為不同的類型
//創(chuàng)建一個(gè)鏈表的結(jié)構(gòu)體
typedef struct ListNode
{
	ListDataType data;//存儲(chǔ)數(shù)據(jù)
	struct ListNode* next;//存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址的指針
	struct ListNode* prev;//存儲(chǔ)上一個(gè)結(jié)點(diǎn)的地址的指針
}ListNode;

ListNode* BuyListNode(ListDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//向內(nèi)存申請(qǐng)一個(gè)新的結(jié)點(diǎn)
	if (newnode == NULL)
	{
		printf("BuyListNode::%s\n", strerror(errno));//打印結(jié)點(diǎn)空間申請(qǐng)失敗的原因
		exit(-1);//終止程序
	}
	newnode->data = x;//將x放入申請(qǐng)的結(jié)點(diǎn)數(shù)據(jù)區(qū)
	newnode->next = NULL;//讓新結(jié)點(diǎn)的next指向空
	newnode->prev = NULL;//讓新結(jié)點(diǎn)的prev指向空
	return newnode;//返回新結(jié)點(diǎn)的地址
}

void ListInit(ListNode** pphead)//這里我們需要對(duì)頭結(jié)點(diǎn)進(jìn)行改變，所以傳二級(jí)指針
{
	assert(pphead);//檢測(cè)傳過(guò)來(lái)的pphead的地址是否為空
	*pphead = BuyListNode(0);//創(chuàng)建一個(gè)新的哨兵位頭結(jié)點(diǎn)
	(*pphead)->next = *pphead;//讓這個(gè)結(jié)點(diǎn)指向自己
	(*pphead)->prev = *pphead;
}

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);//創(chuàng)建一個(gè)新的哨兵位頭結(jié)點(diǎn)
	phead->next = phead;//讓這個(gè)結(jié)點(diǎn)的next指向自己
	phead->prev = phead;//讓prev指向自己
	return phead;//返回哨兵位頭結(jié)點(diǎn)的地址
}

void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;//讓cur指向哨兵位的下一個(gè)結(jié)點(diǎn)
	while (cur != phead)//鏈表打印是否結(jié)束的條件判斷
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);//檢查傳過(guò)來(lái)的頭結(jié)點(diǎn)是否為空
	ListNode* tail = phead->prev;//找到鏈表的尾結(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn)

	tail->next = newnode;//讓尾結(jié)點(diǎn)的next指向新的結(jié)點(diǎn)
	newnode->prev = tail;//讓新結(jié)點(diǎn)的prev指向之前的尾結(jié)點(diǎn)
	newnode->next = phead;//讓新的結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)
	phead->prev = newnode;//讓頭結(jié)點(diǎn)指向新的尾結(jié)點(diǎn)
}

void ListPopBack(ListNode* phead)
{
	assert(phead);
	if (phead->next == phead)//如果鏈表只有哨兵位結(jié)點(diǎn)的情況，就不能繼續(xù)刪除了
		return;

	ListNode* tail = phead->prev;//找到尾結(jié)點(diǎn)
	ListNode* tailPrev = tail->prev;//定義尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
	free(tail);//釋放要?jiǎng)h除的結(jié)點(diǎn)
	tailPrev->next = phead;//讓前一個(gè)結(jié)點(diǎn)指向哨兵位結(jié)點(diǎn)
	phead->prev = tailPrev;//讓哨兵位結(jié)點(diǎn)指向新的尾結(jié)點(diǎn)
}

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新結(jié)點(diǎn)
	newnode->next = phead->next;//新結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
	phead->next->prev = newnode;//頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)
	phead->next = newnode;//頭結(jié)點(diǎn)指向新結(jié)點(diǎn)
	newnode->prev = phead;//新結(jié)點(diǎn)prev指向頭結(jié)點(diǎn)
}

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新結(jié)點(diǎn)
	ListNode* next = phead->next;//定義next記錄頭節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的位置
	phead->next = newnode;//頭結(jié)點(diǎn)next指向新結(jié)點(diǎn)
	newnode->prev = phead;//新結(jié)點(diǎn)的prev指向頭結(jié)點(diǎn)
	next->prev = newnode;//頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的prev指向新階段
	newnode->next = next;//新結(jié)點(diǎn)的next指向原頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	if (phead->next == NULL)//只有哨兵位頭結(jié)點(diǎn)的情況
		return;
	ListNode* next = phead->next->next;//定義next指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
	free(phead->next);//釋放要?jiǎng)h除的結(jié)點(diǎn)
	phead->next = next;//讓哨兵位頭結(jié)點(diǎn)指向要?jiǎng)h除的下一個(gè)結(jié)點(diǎn)
	next->prev = phead;//讓要?jiǎng)h除的下一個(gè)結(jié)點(diǎn)的prev指向toujied
}

ListNode* ListFind(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;//讓cur指向哨兵位頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
	while (cur != phead)//鏈表循環(huán)是否結(jié)束的判斷條件
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;//找不到對(duì)于的結(jié)點(diǎn)
}

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn)
	pos->prev->next = newnode;//pos的前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn)
	newnode->prev = pos->prev;//新結(jié)點(diǎn)的prev指向pos的前一個(gè)結(jié)點(diǎn)
	newnode->next = pos;//新結(jié)點(diǎn)的next指向pos結(jié)點(diǎn)
	pos->prev = newnode;//pos的prev指向新結(jié)點(diǎn)
}

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn)
	ListNode* posPrev = pos->prev;//定義pos的前一個(gè)結(jié)點(diǎn)
	posPrev->next = newnode;//讓pos的pos前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn)
	newnode->prev = posPrev;//新結(jié)點(diǎn)的prev指向pos的前一個(gè)結(jié)點(diǎn)
	newnode->next = pos;//新結(jié)點(diǎn)的next指向pos
	pos->prev = newnode;//pos的prev指向新結(jié)點(diǎn)
}

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;//prev為pos的前一個(gè)結(jié)點(diǎn)
	ListNode* next = pos->next;//next為pos的后一個(gè)結(jié)點(diǎn)
	free(pos);//釋放posjied
	prev->next = next;
	next->prev = prev;
}

void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;//指向哨兵位結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
	while (cur != phead)//依次循環(huán)找鏈表的每一個(gè)結(jié)點(diǎn)
	{
		ListNode* next = cur->next;//記錄cur的下一個(gè)結(jié)點(diǎn)位置
		free(cur);//釋放cur位置的結(jié)點(diǎn)
		cur = next;//指向下一個(gè)結(jié)點(diǎn)
	}
	free(phead);//釋放哨兵位頭結(jié)點(diǎn)
}