🎉🎉想快速入門資料結構，推薦訂閱作者的初階資料結構專欄！此專欄預計更新：順序表，鏈表，堆疊，佇列，二叉樹，排序演算法等等

🎉🎉初階資料結構我們通過c語言實作，所以此專欄也可以幫助大家鞏固大家的c語言知識

🎉🎉源代碼已上傳至我的碼云

🎉🎉博主的微信公眾號關注啦，關注我每天學習一道題，點我關注

前言

其中在鏈表的實作中有很多種實作方法，主要取決于以下幾個因素

單向還是雙向？
回圈還是不回圈？
帶頭還是不帶頭

這幾個特征兩兩組合，就可以看做一種鏈表的實作方式

但在實際中運用最大的，其中就只有以下兩種：

不帶頭單向不回圈和我們本文的實作方式——雙向帶頭回圈

其中前者在oj題中考的特別多，而且可以作為其它資料結構，比如哈希桶的子結構，所以應用比較廣泛

但是，前者卻不適合用來存盤資料

因為我們在尾插，尾刪等函式介面中，需要遍歷查找鏈表尾

而且，還需要考慮頭結點為空等等問題

所以，我們引入了帶頭雙向回圈鏈表，帶頭結點可以有效解決插入時鏈表為空的問題，而回圈可以解決尋找尾結點的問題，雙向讓我們方便尋找當前結點的前面一個結點

在本文中實作的結構雖然看起來復雜，但是實作卻非常簡單，在實際應用中也最適合于存盤資料

其中回圈的體現：尾結點不指向NULL，而指向頭結點

雙向的體現：結點間兩兩相互鏈接，后面結點可以找到前面的結點

邏輯結構圖如下

雙向鏈表定義

與單鏈表差不多用結構體定義，不過需要多一個prev指標存盤前面結點的地址

定義

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

同樣，為了方便存盤型別的替換，將我們的資料型別統一命名

typedef int LTDataType;

初始化

因為我們的鏈表是帶頭的，所以我們在初始化的時候需要開辟一個頭結點出來
頭結點的特征：**不存盤有效資料，**所以我們初始化的時候不需要初始化頭結點中的資料

我們為了滿足回圈的特征，將頭結點的next和prev都指向自己

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

初始化函式使用：

LTNode* plist = ListInit();

雙向鏈表的插入

在本文插入中，傳參不再用到二級指標，因為頭指標的指向永遠不會改變

并且，無需考慮邊界情況

插入函式

前文中已經介紹，這里不再詳細闡述

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

尾插

有了尾結點，我們的尾插就變的相對簡單的多

根據回圈的特征，我們頭結點的前面一個結點就是尾結點

我們開辟出一個新結點后，與單鏈表不同的是，需要注意有tail->next,newnode->prev，還有最重要的newnode->next=phead,phead->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;
}

對邊界情況的討論：

空鏈表

所以，在后續的插入中，我們并不需要特殊討論

頭插

頭插在頭結點后面插入就行了，這里不再詳細闡述

要注意它們之間的相互鏈接關系：

newnode和phead和原來的phead->next都需要做到兩兩相互鏈接

這里的phead->next如果看的不順眼，也可以用變數代替

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);

	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

任意位置插入

同樣，我們需要查找函式來查找我們需要插入的位置，引數傳遞也只需要傳入這個位置的指標

因為我們現在方便查找前面的結點，所以我們可以實作在pos位置之前的插入

為了方便，用posPrev記錄pos位置之前的結點

注意鏈接關系就行，沒什么難度

邊界情況為空鏈表，頭插，尾插，大家可以嘗試走讀代碼，可以發現邊界情況在這種結構中通通不用考慮

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

	LTNode* newnode = BuyListNode(x);
	LTNode* prevPos = pos->prev;
	prevPos->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
	newnode->prev = prevPos;
}

雙向鏈表的洗掉

尾刪

我們同樣方便找到尾部的結點

需要變數來記錄，重新建立鏈接關系時，繞開尾結點即可

最后把尾結點釋放掉

但是，這里的邊界情況需要討論

當鏈表為空時，我們再呼叫這個函式的話，連頭結點也會被釋放掉

所以為了避免這個問題，我們可以加一個斷言，判斷phead->next是不是它本身即可

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

	LTNode* tail = phead->prev;
	tail->prev->next = phead;
	phead->prev = tail->prev;
	free(tail);
	tail = NULL;

}

頭刪

同樣繞開頭結點即可，沒什么難度

void ListPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* head = phead->next;

	head->next->prev = phead;
	phead->next = head->next;

	free(head);

	head = NULL;
}

任意位置的洗掉

任意位置洗掉只需要修改兩個結點就可以繞開我們當前需要釋放的結點

void ListErase(LTNode* pos)
{
	assert(pos);

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = 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;
}

但我們可以發現，在鏈表中最優的結構中，查找的時間復雜度仍然是O(N)，所以查找復雜度高是鏈表中最大的缺點

列印函式

同樣是遍歷列印

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

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

鏈表銷毀

為了防止記憶體泄露，在我們使用完鏈表后，最好將它們全部銷毀

在這里我們最后才釋放phead，因為phead是我們的判斷條件

為了防止當前位置釋放后找不到下一個結點，我們在這里用兩個指標來遍歷

void ListDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	LTNode* next = cur->next;
	while (cur != phead)
	{
		free(cur);
		cur = next;
		if(next != phead)
			next = cur->next;
	}
	free(phead);
	phead = NULL;
}

一個使用示例

void LTest3()
{
	LTNode* plist = ListInit();//初始化鏈表

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);//尾插一些資料
	ListPrint(plist);//列印函式

	LTNode* pos = ListFind(plist, 2);//查找某個數字的位置，并回傳
	LTNode* pos2 = ListFind(plist, 4);
	ListInsert(pos, 6);//利用find找到的位置來插入
	ListPrint(plist);
	ListErase(pos2);
	ListPrint(plist);
	ListDestory(plist);//使用完要銷毀鏈表
}

運行截圖：