1.什么是雙向鏈表?雙向循環鏈表?

(1)雙向鏈表指的是構成鏈表的每個結點中設立兩個指針域：一個指向其直接前驅的指針域prev，一個指向其直接后繼的指針域next。這樣形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。

(2)雙向循環鏈表將雙向鏈表的頭結點和尾結點鏈接起來也能構成循環鏈表，其稱為雙向循環鏈表。

2.雙向循環鏈表的實現

(1)結構

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

(2)創建新鏈表

ListNode* BuyListNode(LTDataType x)//建立新節點
{
	ListNode* node = (struct ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	return node;
}

(3)初始化

void ListInit()//初始化
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

(4)尾插

void ListPushBack(ListNode* phead,LTDataType x)//尾插
{
	/*assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;*/
	ListInsert(phead, x);
}

(5)頭插

void ListPushFront(ListNode* phead, LTDataType x)//頭插
{
	assert(phead);
	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;	
}

(6)頭刪

void ListPushFront(ListNode* phead)//頭刪
{
	assert(phead);
	ListNode* first = phead->next;
	ListNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;
}

(7)尾刪

void ListPushBack(ListNode* phead)//尾刪
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

(8)查找某個值的位置

ListNode ListFind(ListNode* phead, LTDataType x)//查找值的位置
{
	assert(phead);
	ListNode*  cur = phead->next;
	while (cur !=phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

(9)插入

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

(10)刪除

void ListErase(ListNode* pos)//刪除某位置的節點
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

(11)判斷是否為空

int ListEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead ? 1 : 0;//空為1，不空為0
}

(12)鏈表的長度

int ListSize(ListNode* phead)
{
	assert(phead);
	int size = 0;
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

(13)銷毀鏈表

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = cur->next;
	}
	free(phead);
}

(14)打印鏈表

void ListPrint(ListNode* phead)//打印
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}