C語言如何實現帶頭雙向循環鏈表

這篇文章主要介紹了C語言如何實現帶頭雙向循環鏈表，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

前言

在實際生活中最常用的就是這兩種鏈表。無頭單向非循環鏈表。和帶頭雙向循環鏈表。
無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現很多。
帶頭雙向循環鏈表：結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶來很多優勢，實現反而簡單了，后面我們代碼實現了就知道了。

1. 創建結構體

注意：typedef起作用是在第7行哦。所以第5,6還需要寫struct ListNode類型。

typedef int LNDataType;

typedef struct ListNode
{
	  struct ListNode* prev;
 	  struct ListNode* next;
      LNDataType val;
}LN;

2.malloc新節點

注意：需判斷新開辟的節點是否為空。

//申請一個新節點
LN* BuynewNode(LNDataType x)
{
	LN* newNode = (LN*)malloc(sizeof(LN));
	if (newNode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->prev = NULL;
	newNode->val = x;
	return newNode;
}

3.創建哨兵位節點

注意：這里因為需要改變plist指針的內容，也就是改變plist指針的指向，所以需要傳遞plist的地址。

一句話就是：需要改變誰的內容，就傳誰的地址。

這里有一點非常巧非常妙，就是phead的后繼和前驅都是指向自己（phead），這里是模仿C++STL庫里的哨兵位節點。

只能佩服想出來這些東西的大神。這樣設計哨兵位節點的話，后續尾插，尾刪，都特別的巧妙。

test.c

	LN* plist = NULL;
	ListNodeInit(&plist);

List.h

//初始化節點
void ListNodeInit(LN** pphead)
{
	LN* newNode = BuynewNode(0);
	*pphead = newNode;
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}

4.尾插

注意：需要斷言的原因是因為，即使鏈表沒有一個節點，那鏈表至少還有個頭，所以phead肯定不為空。

這里沒有傳地址的原因是因為，你不需要改變plist的指向，你改變的是plist指向的結構體里面的值。

多個節點尾插的情況如圖。

一個節點的尾插。

//尾插
void ListNodePushBack(LN* phead, LNDataType x)
{
	assert(phead);
	LN* newNode = BuynewNode(x);
	LN* tail = phead->prev;
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = phead;
	phead->prev = newNode;
}

5.打印

注意：因為帶個頭，所以cur從第二個位置開始。

//打印
void ListNodePrint(LN* phead)
{
	LN* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

6.尾刪

注意不能刪掉頭結點，free掉頭結點的話會造成野指針，再次訪問時會造成非法訪問。
所以要用assert斷言不為首節點。

//尾刪
void ListNodePopBack(LN* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LN* tail = phead->prev;
	LN* tailPrev = tail->prev;
	free(tail);
	tail = NULL;
	phead->prev = tailPrev;
	tailPrev->next = phead;
}

7.頭插

最好用next記錄下一個節點。這樣方便，思路清晰

//頭插
void ListNodePushFront(LN* phead, LNDataType x)
{
	assert(phead);
	LN* newNode = BuynewNode(x);
	LN* next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next = next;
	next->prev = newNode;
}

8.在指定位置pos的前面進行插入

一般情況

只有一個節點時。

兩種情況都適用以下代碼。

//指定位置前插入，極限是頭插
void ListNodeInsert(LN* pos, LNDataType x)
{
	if (pos == NULL)
	{
		printf("沒有找到這個數\n");
		return;
	}
	LN* newNode = BuynewNode(x);
	LN* tailPrev = pos->prev;
	tailPrev->next = newNode;
	newNode->prev = tailPrev;
	newNode->next = pos;
	pos->prev = newNode;
}

9. 刪除指定位置pos節點

正常情況

極限尾刪

兩種情況都適用以下代碼。

//指定位置刪除
void ListNodeErease(LN* phead, LN* pos)
{
	if (pos == phead || pos == NULL)
	{
		printf("pos指向頭，或為空\n");
		return;
	}
	LN* posPrev = pos->prev;
	LN* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}

10.銷毀鏈表

注意：這里相當于malloc用完之后的free。否則會造成內存泄漏。
cur可以置空，但用處不大，因為cur是形參，形參是實參的一份臨時拷貝，形參置空并不能改變實參。外部的實參還是依舊能非法訪問到cur所指向的空間。

//鏈表銷毀
void ListNodeDestroy(LN* phead)
{
	assert(phead);
	LN* cur = phead->next;
	LN* next = cur->next;
	while (cur != phead)
	{
		next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;
	}
	free(phead);
	phead = NULL;
}

感謝你能夠認真閱讀完這篇文章，希望小編分享的“C語言如何實現帶頭雙向循環鏈表”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!