這篇博客，我要給大家分享雙鏈表的知識，上一篇博客，我給大家分享了有關單鏈表的知識，單鏈表相比雙鏈表而言結構比較簡單，但事實上，雙鏈表的實作比單鏈表要方便很多，下面我就來給大家聊一聊雙鏈表的那些事兒~
博客代碼已上傳至gitee：https://gitee.com/byte-binxin/data-structure/tree/master/List_2.0

帶頭雙向鏈表的結構

看下面的圖，就是我今天要給大家分享有結構——帶頭雙向鏈表，這里的頭是不存放任何資料的，就是一個哨兵衛的頭結點，
用代碼來表示每一個節點就是這樣的：

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;//指向前一個節點
	struct ListNode* next;//指向后一個節點
}LTNode;

帶頭雙向鏈表的介面實作

初始化雙鏈表

在初始化雙鏈表的程序中，我們要開好一個頭節點，作為哨兵衛的頭節點，然后回傳這個節點的指標，介面外面只要用一個節點指標接受這個回傳值就好了，具體實作如下：

LTNode* ListInit(LTNode* pHead)
{
	pHead = (LTNode*)malloc(sizeof(LTNode));
	if (pHead == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	pHead->next = pHead;
	pHead->prev = pHead;
	return pHead;
}

列印雙鏈表

雙鏈表的列印就是遍歷一遍雙鏈表，用一個cur節點指標來走，走到head的位置就停下來，
看代碼實作：

void ListPrint(LTNode* pHead)
{
	assert(pHead);

	LTNode* cur = pHead->next;
	printf("Head ");
	while (cur != pHead)
	{
		printf("<-> %d ", cur->data);
		cur = cur->next;
	}
	printf("<-> Head\n");
}

雙鏈表的銷毀

申請的節點使用完之后都要自己手動釋放，以防止記憶體泄漏這些不好的問題出現，我們實作這個介面，用一級指標接受實參，其實也是遍歷一遍鏈表，看一下代碼實作：

void ListDestroy(LTNode* pHead)
{
	assert(pHead);

	LTNode* cur = pHead->next;
	LTNode* next = cur->next;
	while (cur != pHead)
	{
		free(cur);
		cur = next;
		next = cur->next;
	}
	free(pHead);
}

注意：銷毀鏈表是介面外面要記得對鏈表置空，

雙鏈表的尾插

雙鏈表的尾插首先要開辟一個節點，由于頭插和任意位置的插入都會開辟一個節點，所以我們把這個功能封裝成一個函式BuyListNode，具體代碼實作如下：

LTNode* BuyListNode(LTDataType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	if (newNode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;

	return newNode;
}

申請完節點后，我們就要通過改變指標的指向來把這個節點連接上去，棘突步驟如下：

1. 先讓尾節點的next指向新開辟的節點newNode，然后讓newNode的prev指向尾節點
2. 讓newNode的next指向head，head的prev指向newNode

這樣我們就把新開辟的節點尾插上去了，
下面來看一下具體的代碼實作：

void ListPushBack(LTNode* pHead, LTDataType x)
{
	assert(pHead);

	LTNode* newNode = BuyListNode(x);
	LTNode* tail = pHead->prev;
	
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = pHead;
	pHead->prev = newNode;

}

來測驗一下代碼：

void TestList1()
{
	LTNode* pList = NULL;
	pList = ListInit(pList);

	ListPushBack(pList, 1);
	ListPushBack(pList, 2);
	ListPushBack(pList, 3);
	ListPushBack(pList, 4);
	ListPushBack(pList, 5);
	ListPrint(pList);
	
	ListDestroy(pList);
	pList = NULL;
}

代碼運行結果如下：

雙鏈表的尾刪

尾刪要考慮鏈表是否為空，這里鏈表為空指的是只有一個頭節點，如果只有一個頭結點我們就不能繼續對鏈表進行洗掉操作了，所以我們要對引數進行斷言防止頭被刪，

assert(pHead->next != pHead);

尾刪具體步驟如下：

1. 先找到尾節點，然后找到尾節點的前一個節點tailPrev，然后就可以free掉尾節點了
2. 接下來就是改變指標指向，讓tailPrev的next指向head，然后讓head的prev指向tailPrev即可，這樣我們就順利地完成了尾刪

代碼實作如下：

void ListPopBack(LTNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);

	LTNode* tail = pHead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = pHead;
	pHead->prev = tailPrev;

}

下面我們再來測驗一下代碼：

void TestList1()
{
	LTNode* pList = NULL;
	pList = ListInit(pList);

	ListPushBack(pList, 1);
	ListPushBack(pList, 2);
	ListPushBack(pList, 3);
	ListPushBack(pList, 4);
	ListPushBack(pList, 5);
	ListPrint(pList);

	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);
	ListDestroy(pList);
	pList = NULL;
}

代碼運行結果如下：

雙鏈表的頭插

頭插就是在head后插一個節點，首先還是要開辟一個節點，然后就是改變指標的指向，具體實作步驟如下：

1. 首先記住head的的下一個節點next，然后讓newNode的prev指向head，head的next指向newNode
2. 讓newNode的next指向next，next的prev指向newNode

代碼實作如下：

void ListPushFront(LTNode* pHead, LTDataType x)
{
	assert(pHead);
	
	LTNode* newNode = BuyListNode(x);
	LTNode* first = pHead->next;
	pHead->next = newNode;
	newNode->prev = pHead;
	newNode->next = first;
	first->prev = newNode;

}

測驗代碼如下：

void TestList1()
{
	LTNode* pList = NULL;
	pList = ListInit(pList);
	ListPushFront(pList, 1);
	ListPushFront(pList, 2);
	ListPushFront(pList, 3);
	ListPushFront(pList, 4);
	ListPrint(pList);
	
	ListDestroy(pList);
	pList = NULL;
}

代碼運行結果如下：

雙鏈表的頭刪

頭刪同樣要考慮鏈表是否為空，這里鏈表為空指的是只有一個頭節點，如果只有一個頭結點我們就不能繼續對鏈表進行洗掉操作了，所以我們要對引數進行斷言防止頭被刪，

assert(pHead->next != pHead);

頭刪具體步驟實作如下：

1. 先找到要洗掉的節點，也就是head的下一個firstNode，找到這個節點的下一個next，然后free這個節點
2. 接下來就是改變指標的指向，讓head的next指向next，讓next的prev指向head

代碼實作如下：

void ListPopFront(LTNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);

	LTNode* first = pHead->next;
	LTNode* second = first->next;

	free(first);
	pHead->next = second;
	second->prev = pHead;

}

測驗代碼如下：

void TestList1()
{
	LTNode* pList = NULL;
	pList = ListInit(pList);
	ListPushFront(pList, 1);
	ListPushFront(pList, 2);
	ListPushFront(pList, 3);
	ListPushFront(pList, 4);
	ListPrint(pList);
	
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);
	
	ListDestroy(pList);
	pList = NULL;
}

代碼運行結果如下：

雙鏈表任意位置查找

查找無非就是遍歷雙鏈表，這是還是直接上代碼實作：

LTNode* ListFind(LTNode* pHead, LTDataType x)
{
	assert(pHead);

	LTNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

雙鏈表任意位置之前插入

任意位置插入首先要開辟一個節點，然后就是按照所個位置，改變指標的指向來把這個節點連接上去，看具體代碼實作如下：

void ListInsert(LTNode* pHead, LTNode* pos, LTDataType x)
{
	assert(pHead);

	LTNode* posPrev = pos->prev;
	LTNode* newNode = BuyListNode(x);

	posPrev->next = newNode;
	newNode->prev = posPrev;
	newNode->next = pos;
	pos->prev = newNode;
}

這里我們可以在頭插和尾插部分復用這個結構，來實作頭插尾插，所以更新后的頭插尾插代碼如下：

//頭插
void ListPushFront(LTNode* pHead, LTDataType x)
{
	assert(pHead);	
	ListInsert(pHead, pHead->next, x);
}

//尾插
void ListPushBack(LTNode* pHead, LTDataType x)
{
	assert(pHead);
	ListInsert(pHead, pHead, x);
}

雙鏈表任意位置洗掉

洗掉就要考慮鏈表是否為空，防止洗掉頭節點，所以要斷言，前面都講了很多類似的，下面我們直接看這個介面是如何實作的：

//任意位置洗掉
void ListErase(LTNode* pHead, LTNode* pos)
{
	assert(pHead);
	assert(pHead->next != pHead);

	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	free(pos);
	prev->next = next;
	next->prev = prev;
}

這里同樣可以復用這串代碼來實作頭刪和尾刪，具體實作如下：

//頭刪
void ListPopFront(LTNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);
	
	ListErase(pHead, pHead->next);
}
//尾刪
void ListPopBack(LTNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);

	ListErase(pHead, pHead->prev);

}

鏈表和順序表的對比

參考下表：

總結

總的來說，單鏈表和雙鏈表也算是介紹完了，雙鏈表結構雖然比單鏈表復雜，但實作起來確比單鏈表要簡單一些，鏈表這一部分暫告一段落，接下來我會給大家分享有關堆疊和佇列的知識，歡迎大家關注，