雙向鏈表的概念

在前面學習鏈表的時候，不知道大家有沒有過感受，鏈表是通過next鏈接起來的，這種鏈接是頭去鏈接尾，但是在尾部就不是那么好往前找到頭，

比如這么一個結構，如果說現在讓輸出1，2，3，4，5是不是很容易，直接順序遍歷，然后列印data域即可，但是如果需要反著列印的時候大家是不是就難受了，心想：如果5到4有鏈接，4到3有鏈接，3到2有鏈接，2到一有鏈接，如果是這樣的結構，就列印十分方便了，
上面心中所想的結構其實就是雙向鏈表了，
如下：
至于雙向帶頭回圈的鏈表：就是將頭尾相連的雙向鏈表了，這種鏈表結構就非常強大了，我們可以從任一點出發找到別的點，

算了來張百度百科的圖片

現在來創建一個雙向鏈表的結構：
其實就是多了一個prev指標的鏈表結構，

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LDataType data;
}ListNode;

雙向鏈表的相關函式

初始化創建

注意創建就是指需要有一個頭節點，對于雙向鏈表來說，起碼得有一個節點的，不然的話那算？算空氣，這個節點首先就是自己鏈接自己的，

ListNode* ListCreate()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

新建一個節點

ListNode* BuyListNode(LDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

頭插

頭插的兩種方式，一種是復用后面的在pos位置插入(對于頭插來說pos就是phead->next，注意這里不是phead，phead->next才是指頭插)，另一種直接實作

復用

void ListPushFront(ListNode* phead, LDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

不復用

void ListPushFront(ListNode* phead, LDataType x)
{
	assert(phead);
	assert(phead->next != phead);//只有一個頭節點的時候不要洗掉了
	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

尾插

尾插也是兩種實作，依舊是使用pos插入，此時pos是phead,頭是連著尾的

復用

void ListPushBack(ListNode* phead, LDataType x)
{
	assert(phead);
	ListInsert(phead, x);
}

不復用

void ListPushBack(ListNode* phead, LDataType x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

頭刪

頭刪的時候注意要討論不要洗掉最后的一個節點

復用

void ListPopFront(ListNode* phead)
{
	ListErase(phead->next);//復用頭刪
}

不復用

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* first = phead->next;
	ListNode* firstNext = first->next;
	phead->next = firstNext;
	firstNext->prev = phead;
	free(first);
}

尾刪

尾刪同理，至少保留一個節點~~

void ListPopBack(ListNode* phead)
{
	ListErase(phead->prev);
}

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

列印節點

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

查找

ListNode* ListFind(ListNode* phead, LDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;//指向頭節點的next才是真實的值域
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

pos處插入節點

前面使用的頭插尾插就是復用這個地方，對于為什么頭插是phead->next，尾插是phead

void  ListInsert(ListNode* pos, LDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newNode = BuyListNode(x);
	prev->next = newNode;
	newNode->prev = prev;
	pos->prev = newNode;
	newNode->next = pos;
}

pos處洗掉節點

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

判斷是否為空

int ListEmpty(ListNode* phead)
{
	return phead->next == phead ? 1 : 0;
}

判斷大小

int ListSize(ListNode* phead)
{
	assert(phead);
	int len = 0;
	ListNode* cur = phead->next;//指向頭節點的next才是真實的值域
	while (cur != phead)
	{
		len++;
		cur = cur->next;
	}
	return len;
}

銷毀操作

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