1.什么是雙向鏈表?雙向循環(huán)鏈表?

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

(2)雙向循環(huán)鏈表將雙向鏈表的頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，其稱為雙向循環(huán)鏈表。

2.雙向循環(huán)鏈表的實現(xiàn)

(1)結(jié)構(gòu)

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

(2)創(chuàng)建新鏈表

ListNode* BuyListNode(LTDataType x)//建立新節(jié)點
{
	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)//刪除某位置的節(jié)點
{
	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");
}