C語言詳解如何實現(xiàn)帶頭雙向循環(huán)鏈表

更新時間：2022年04月23日 11:52:31 作者：風(fēng)＆646

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單

創(chuàng)建鏈表存儲結(jié)構(gòu)
創(chuàng)建結(jié)點(diǎn)
鏈表的初始化
雙向鏈表的打印
雙向鏈表尾插
雙向鏈表尾刪
雙向鏈表頭插
雙向鏈表頭刪
雙向鏈表查找
雙向鏈表pos前插入結(jié)點(diǎn)
雙向鏈表刪除pos位置的結(jié)點(diǎn)
雙向鏈表的銷毀
順序表和鏈表的區(qū)別

創(chuàng)建鏈表存儲結(jié)構(gòu)

我們需要創(chuàng)建一個結(jié)構(gòu)體來存儲一個鏈表結(jié)點(diǎn)的相關(guān)信息。

typedef int ListDataType;//將ListDataType先定義為int類型，根據(jù)需要可以改為不同的類型
//創(chuàng)建一個鏈表的結(jié)構(gòu)體
typedef struct ListNode
{
	ListDataType data;//存儲數(shù)據(jù)
	struct ListNode* next;//存儲下一個結(jié)點(diǎn)的地址的指針
	struct ListNode* prev;//存儲上一個結(jié)點(diǎn)的地址的指針
}ListNode;

創(chuàng)建結(jié)點(diǎn)

我們每次增加數(shù)據(jù)都要創(chuàng)建一個新的結(jié)點(diǎn)，但每次都創(chuàng)建就會非常的麻煩。所以我們考慮把創(chuàng)建一個結(jié)點(diǎn)這個功能封裝成一個函數(shù)，每次要使用只要調(diào)用一下就可以了。

ListNode* BuyListNode(ListDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//向內(nèi)存申請一個新的結(jié)點(diǎn)
	if (newnode == NULL)
	{
		printf("BuyListNode::%s\n", strerror(errno));//打印結(jié)點(diǎn)空間申請失敗的原因
		exit(-1);//終止程序
	}
	newnode->data = x;//將x放入申請的結(jié)點(diǎn)數(shù)據(jù)區(qū)
	newnode->next = NULL;//讓新結(jié)點(diǎn)的next指向空
	newnode->prev = NULL;//讓新結(jié)點(diǎn)的prev指向空
	return newnode;//返回新結(jié)點(diǎn)的地址
}

鏈表的初始化

帶頭雙向循環(huán)鏈表我們對其初始化就是申請一個帶哨兵位的頭結(jié)點(diǎn)。接下來我們看初始化的兩種方法。

void ListInit(ListNode** pphead)//這里我們需要對頭結(jié)點(diǎn)進(jìn)行改變，所以傳二級指針
{
	assert(pphead);//檢測傳過來的pphead的地址是否為空
	*pphead = BuyListNode(0);//創(chuàng)建一個新的哨兵位頭結(jié)點(diǎn)
	(*pphead)->next = *pphead;//讓這個結(jié)點(diǎn)指向自己
	(*pphead)->prev = *pphead;
}

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);//創(chuàng)建一個新的哨兵位頭結(jié)點(diǎn)
	phead->next = phead;//讓這個結(jié)點(diǎn)的next指向自己
	phead->prev = phead;//讓prev指向自己
	return phead;//返回哨兵位頭結(jié)點(diǎn)的地址
}

雙向鏈表的打印

我們才用遍歷鏈表的方式來打印鏈表中的數(shù)據(jù)。

void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;//讓cur指向哨兵位的下一個結(jié)點(diǎn)
	while (cur != phead)//鏈表打印是否結(jié)束的條件判斷
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

雙向鏈表尾插

雙向循環(huán)鏈表結(jié)構(gòu)比較優(yōu)，所以很方便找到尾結(jié)點(diǎn)。尾結(jié)點(diǎn)就是哨兵位結(jié)點(diǎn)prev指向的結(jié)點(diǎn)。

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);//檢查傳過來的頭結(jié)點(diǎn)是否為空
	ListNode* tail = phead->prev;//找到鏈表的尾結(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個新的結(jié)點(diǎn)

	tail->next = newnode;//讓尾結(jié)點(diǎn)的next指向新的結(jié)點(diǎn)
	newnode->prev = tail;//讓新結(jié)點(diǎn)的prev指向之前的尾結(jié)點(diǎn)
	newnode->next = phead;//讓新的結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)
	phead->prev = newnode;//讓頭結(jié)點(diǎn)指向新的尾結(jié)點(diǎn)
}

雙向鏈表尾刪

void ListPopBack(ListNode* phead)
{
	assert(phead);
	if (phead->next == phead)//如果鏈表只有哨兵位結(jié)點(diǎn)的情況，就不能繼續(xù)刪除了
		return;

	ListNode* tail = phead->prev;//找到尾結(jié)點(diǎn)
	ListNode* tailPrev = tail->prev;//定義尾結(jié)點(diǎn)的前一個結(jié)點(diǎn)
	free(tail);//釋放要刪除的結(jié)點(diǎn)
	tailPrev->next = phead;//讓前一個結(jié)點(diǎn)指向哨兵位結(jié)點(diǎn)
	phead->prev = tailPrev;//讓哨兵位結(jié)點(diǎn)指向新的尾結(jié)點(diǎn)
}

雙向鏈表頭插

雙向鏈表的頭插就是在哨兵位結(jié)點(diǎn)的下一個位置插入一個新的數(shù)據(jù)。

注意：這一種方法種的指向關(guān)系不能隨意顛倒，否則就會出錯。

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個新結(jié)點(diǎn)
	newnode->next = phead->next;//新結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)
	phead->next->prev = newnode;//頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)指向新結(jié)點(diǎn)
	phead->next = newnode;//頭結(jié)點(diǎn)指向新結(jié)點(diǎn)
	newnode->prev = phead;//新結(jié)點(diǎn)prev指向頭結(jié)點(diǎn)
}

我們可以對上一種情況進(jìn)行優(yōu)化，定義一個next記錄頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)的地址。這樣我們就可以不用在意指向順序的問題，可以減少出錯的概率。

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個新結(jié)點(diǎn)
	ListNode* next = phead->next;//定義next記錄頭節(jié)點(diǎn)的下一個結(jié)點(diǎn)的位置
	phead->next = newnode;//頭結(jié)點(diǎn)next指向新結(jié)點(diǎn)
	newnode->prev = phead;//新結(jié)點(diǎn)的prev指向頭結(jié)點(diǎn)
	next->prev = newnode;//頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)的prev指向新階段
	newnode->next = next;//新結(jié)點(diǎn)的next指向原頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)
}

雙向鏈表頭刪

我們先找到頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)，然后在把它釋放掉。這里需要注意的是如果鏈表為空，只有哨兵位頭結(jié)點(diǎn)的情況，我們需要對其進(jìn)行特殊的處理。

void ListPopFront(ListNode* phead)
{
	assert(phead);
	if (phead->next == NULL)//只有哨兵位頭結(jié)點(diǎn)的情況
		return;
	ListNode* next = phead->next->next;//定義next指向要刪除結(jié)點(diǎn)的下一個結(jié)點(diǎn)
	free(phead->next);//釋放要刪除的結(jié)點(diǎn)
	phead->next = next;//讓哨兵位頭結(jié)點(diǎn)指向要刪除的下一個結(jié)點(diǎn)
	next->prev = phead;//讓要刪除的下一個結(jié)點(diǎn)的prev指向toujied
}

雙向鏈表查找

若我們想要對指定的位置的結(jié)點(diǎn)進(jìn)行相應(yīng)的改變就得先找到對應(yīng)的結(jié)點(diǎn)，所以我們將查找指定數(shù)據(jù)封裝成一個函數(shù)。方便后續(xù)調(diào)用。

ListNode* ListFind(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;//讓cur指向哨兵位頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)
	while (cur != phead)//鏈表循環(huán)是否結(jié)束的判斷條件
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;//找不到對于的結(jié)點(diǎn)
}

雙向鏈表pos前插入結(jié)點(diǎn)

推薦使用第二種方法，不容易出錯。

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個新的結(jié)點(diǎn)
	pos->prev->next = newnode;//pos的前一個結(jié)點(diǎn)的next指向新結(jié)點(diǎn)
	newnode->prev = pos->prev;//新結(jié)點(diǎn)的prev指向pos的前一個結(jié)點(diǎn)
	newnode->next = pos;//新結(jié)點(diǎn)的next指向pos結(jié)點(diǎn)
	pos->prev = newnode;//pos的prev指向新結(jié)點(diǎn)
}

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個新的結(jié)點(diǎn)
	ListNode* posPrev = pos->prev;//定義pos的前一個結(jié)點(diǎn)
	posPrev->next = newnode;//讓pos的pos前一個結(jié)點(diǎn)的next指向新結(jié)點(diǎn)
	newnode->prev = posPrev;//新結(jié)點(diǎn)的prev指向pos的前一個結(jié)點(diǎn)
	newnode->next = pos;//新結(jié)點(diǎn)的next指向pos
	pos->prev = newnode;//pos的prev指向新結(jié)點(diǎn)
}

雙向鏈表刪除pos位置的結(jié)點(diǎn)

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;//prev為pos的前一個結(jié)點(diǎn)
	ListNode* next = pos->next;//next為pos的后一個結(jié)點(diǎn)
	free(pos);//釋放posjied
	prev->next = next;
	next->prev = prev;
}

雙向鏈表的銷毀

void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;//指向哨兵位結(jié)點(diǎn)的下一個結(jié)點(diǎn)
	while (cur != phead)//依次循環(huán)找鏈表的每一個結(jié)點(diǎn)
	{
		ListNode* next = cur->next;//記錄cur的下一個結(jié)點(diǎn)位置
		free(cur);//釋放cur位置的結(jié)點(diǎn)
		cur = next;//指向下一個結(jié)點(diǎn)
	}
	free(phead);//釋放哨兵位頭結(jié)點(diǎn)
}

注意：在寫雙向鏈表的頭插，頭刪，尾插，尾刪時我們可以復(fù)用雙向鏈表的任意位置插入和任意位置刪除那兩個函數(shù)。那兩個函數(shù)就可以完成頭插，頭刪，尾插，尾刪這幾個功能。