typedef int ListDataType;//將ListDataType先定義為int類型，根據需要可以改為不同的類型
//創建一個鏈表的結構體
typedef struct ListNode
{
	ListDataType data;//存儲數據
	struct ListNode* next;//存儲下一個結點的地址的指針
	struct ListNode* prev;//存儲上一個結點的地址的指針
}ListNode;

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

void ListInit(ListNode** pphead)//這里我們需要對頭結點進行改變，所以傳二級指針
{
	assert(pphead);//檢測傳過來的pphead的地址是否為空
	*pphead = BuyListNode(0);//創建一個新的哨兵位頭結點
	(*pphead)->next = *pphead;//讓這個結點指向自己
	(*pphead)->prev = *pphead;
}

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

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

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);//檢查傳過來的頭結點是否為空
	ListNode* tail = phead->prev;//找到鏈表的尾結點
	ListNode* newnode = BuyListNode(x);//創建一個新的結點

	tail->next = newnode;//讓尾結點的next指向新的結點
	newnode->prev = tail;//讓新結點的prev指向之前的尾結點
	newnode->next = phead;//讓新的結點的next指向頭結點
	phead->prev = newnode;//讓頭結點指向新的尾結點
}

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

	ListNode* tail = phead->prev;//找到尾結點
	ListNode* tailPrev = tail->prev;//定義尾結點的前一個結點
	free(tail);//釋放要刪除的結點
	tailPrev->next = phead;//讓前一個結點指向哨兵位結點
	phead->prev = tailPrev;//讓哨兵位結點指向新的尾結點
}

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創建一個新結點
	newnode->next = phead->next;//新結點的next指向頭結點的下一個結點
	phead->next->prev = newnode;//頭結點的下一個結點指向新結點
	phead->next = newnode;//頭結點指向新結點
	newnode->prev = phead;//新結點prev指向頭結點
}

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

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

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

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創建一個新的結點
	pos->prev->next = newnode;//pos的前一個結點的next指向新結點
	newnode->prev = pos->prev;//新結點的prev指向pos的前一個結點
	newnode->next = pos;//新結點的next指向pos結點
	pos->prev = newnode;//pos的prev指向新結點
}

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創建一個新的結點
	ListNode* posPrev = pos->prev;//定義pos的前一個結點
	posPrev->next = newnode;//讓pos的pos前一個結點的next指向新結點
	newnode->prev = posPrev;//新結點的prev指向pos的前一個結點
	newnode->next = pos;//新結點的next指向pos
	pos->prev = newnode;//pos的prev指向新結點
}

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

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