?鏈表的介紹
鏈表的結(jié)構(gòu)一共有八種：帶頭單向循環(huán)鏈表、帶頭單向非循環(huán)鏈表、帶頭雙向循環(huán)鏈表、帶頭雙向非循環(huán)鏈表、無頭單向循環(huán)鏈表、無頭單向非循環(huán)鏈表、無頭雙向循環(huán)鏈表、無頭雙向非循環(huán)鏈表。
今天我們來詳解帶頭雙向循環(huán)鏈表
帶頭雙向循環(huán)鏈表是一種數(shù)據(jù)結(jié)構(gòu)，它通過在雙向鏈表的基礎(chǔ)上增加循環(huán)的特性，并通過一個頭結(jié)點(diǎn)（帶頭）來簡化操作。這種結(jié)構(gòu)在實(shí)際應(yīng)用中有其獨(dú)特的優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)
- 雙向遍歷：鏈表可以從兩個方向遍歷，即可以向前或向后移動。這使得許多操作，如反轉(zhuǎn)遍歷、雙端操作等，更為方便和高效。
- 循環(huán)特性：由于是循環(huán)鏈表，表尾與表頭直接相連。這一特性使得從鏈表的一端到另一端的訪問時間縮短，特別是在需要頻繁執(zhí)行環(huán)形遍歷的場合（如輪轉(zhuǎn)調(diào)度算法）。
- 統(tǒng)一操作：帶頭結(jié)點(diǎn)的鏈表簡化了插入和刪除節(jié)點(diǎn)的操作，因?yàn)椴恍枰獑为?dú)處理空鏈表的情況。頭結(jié)點(diǎn)的存在使得鏈表始終非空，減少了邊界條件的檢查。
- 易于管理：頭結(jié)點(diǎn)提供了一個固定的起點(diǎn)，無論鏈表是否為空，這使得鏈表的管理更為統(tǒng)一和方便。
缺點(diǎn)
- 額外的空間消耗：頭結(jié)點(diǎn)本身不存儲有效數(shù)據(jù)，占用一定的空間。對于內(nèi)存使用極為嚴(yán)格的應(yīng)用場景，這種額外消耗可能是一個缺點(diǎn)。
- 實(shí)現(xiàn)復(fù)雜度：相比單向鏈表，雙向循環(huán)鏈表的實(shí)現(xiàn)更復(fù)雜。正確管理前驅(qū)和后繼指針需要更多的注意和精確控制，增加了編程的難度。
- 性能開銷：每次插入或刪除操作都需要更新兩個指針（前驅(qū)和后繼），這比單向鏈表的操作稍顯復(fù)雜，可能會略微增加時間開銷。
- 循環(huán)錯誤：如果不正確管理節(jié)點(diǎn)的連接和斷開，循環(huán)鏈表容易產(chǎn)生邏輯錯誤，如死循環(huán)或訪問已刪除的節(jié)點(diǎn)，這可能導(dǎo)致程序出錯或崩潰。
鏈表詳解
1. 鏈表的定義?
實(shí)現(xiàn)步驟：
首先，我們還是需要先定義一個結(jié)點(diǎn)類型，與單向鏈表相比，雙向鏈表的結(jié)點(diǎn)類型中需要多出一個前驅(qū)指針，用于指向前面一個結(jié)點(diǎn)，實(shí)現(xiàn)雙向。?
typedef int LTDataType;//存儲的數(shù)據(jù)類型
typedef struct ListNode
{
LTDataType data;//數(shù)據(jù)域
struct ListNode* front;//前驅(qū)指針
struct ListNode* next;//后繼指針
}ListNode;
2. 鏈表節(jié)點(diǎn)的創(chuàng)建?
實(shí)現(xiàn)步驟：
-
內(nèi)存分配：
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));這行代碼通過malloc函數(shù)為一個新的ListNode結(jié)構(gòu)體分配內(nèi)存。sizeof(ListNode)確保分配足夠的內(nèi)存以存放一個ListNode結(jié)構(gòu)體。 -
內(nèi)存分配校驗(yàn)：
if (newNode == NULL) { ... }這個條件判斷用來檢查malloc是否成功分配了內(nèi)存。如果malloc返回NULL，表示內(nèi)存分配失敗，可能是因?yàn)橄到y(tǒng)內(nèi)存不足。這時，函數(shù)打印錯誤消息并返回NULL，避免后續(xù)的空指針操作。 -
初始化節(jié)點(diǎn)數(shù)據(jù)：
newNode->data = value;這行代碼將傳入的value賦值給節(jié)點(diǎn)的data屬性。這樣新節(jié)點(diǎn)就存儲了它應(yīng)該持有的數(shù)據(jù)。 -
自引用初始化：
newNode->front = newNode;和newNode->next = newNode;這兩行代碼初始化節(jié)點(diǎn)的front和next指針，使它們指向節(jié)點(diǎn)自身。這種初始化方式是為了創(chuàng)建一個獨(dú)立的循環(huán)節(jié)點(diǎn)，即該節(jié)點(diǎn)在一個循環(huán)鏈表中既是頭節(jié)點(diǎn)也是尾節(jié)點(diǎn)。
// 創(chuàng)建一個新的節(jié)點(diǎn)
ListNode* CreateNode(LTDataType value) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = value;
newNode->front = newNode;
newNode->next = newNode;
return newNode;
}3. 鏈表的初始化
實(shí)現(xiàn)步驟：
對雙向鏈表進(jìn)行初始化，在初始化的過程中，需要申請一個頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的前驅(qū)和后繼指針都指向自己，使得鏈表一開始便滿足循環(huán)。
// 初始化帶頭的雙向循環(huán)鏈表
ListNode* InitList() {
ListNode* phead = CreateNode(-1); // 創(chuàng)建頭結(jié)點(diǎn)，數(shù)據(jù)通常設(shè)置為-1或其他標(biāo)記值
if (phead != NULL) {
phead->front = phead; // 將頭結(jié)點(diǎn)的前驅(qū)指針指向自身，確保循環(huán)鏈表的閉環(huán)性
phead->next = phead; // 將頭結(jié)點(diǎn)的后繼指針指向自身，同樣確保循環(huán)鏈表的閉環(huán)性
}
return phead; // 返回頭結(jié)點(diǎn)的指針
}4. 鏈表的頭插?
實(shí)現(xiàn)步驟：
- 參數(shù)驗(yàn)證：
assert(phead);這行代碼使用assert函數(shù)確保傳入的頭節(jié)點(diǎn)指針phead不是NULL。這是一種防御性編程實(shí)踐，用于避免空指針引用。 - 創(chuàng)建新節(jié)點(diǎn)：
ListNode* newNode = CreateNode(value);這行代碼調(diào)用CreateNode函數(shù)創(chuàng)建一個新的ListNode對象，其數(shù)據(jù)域設(shè)置為傳入的value。這個函數(shù)返回一個初始化好的新節(jié)點(diǎn)，其front和next指針指向自己，形成一個獨(dú)立的小循環(huán)。 - 定位第一個節(jié)點(diǎn)：
ListNode* Front = phead->next;這行代碼獲取頭節(jié)點(diǎn)后面的第一個節(jié)點(diǎn)（我們稱之為Front）。這是為了之后將新節(jié)點(diǎn)插入頭節(jié)點(diǎn)和Front之間。 - 連接新節(jié)點(diǎn)與頭節(jié)點(diǎn)：
phead->next = newNode;將頭節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)，從而把新節(jié)點(diǎn)作為鏈表的第一個節(jié)點(diǎn)。newNode->front = phead;將新節(jié)點(diǎn)的front指針指向頭節(jié)點(diǎn)，確保從新節(jié)點(diǎn)向前遍歷可以回到頭節(jié)點(diǎn)。 - 連接新節(jié)點(diǎn)與原第一個節(jié)點(diǎn)：
newNode->next = Front;將新節(jié)點(diǎn)的next指針指向原第一個節(jié)點(diǎn)Front，這樣新節(jié)點(diǎn)就正確地插入在頭節(jié)點(diǎn)和Front之間。Front->front = newNode;更新Front的front指針指向新節(jié)點(diǎn)，確保從Front向前遍歷也可以到達(dá)新節(jié)點(diǎn)。
void ListPushFront(ListNode* phead, LTDataType value)
{
assert(phead);
ListNode* newNode = CreateNode(value);//申請一個結(jié)點(diǎn)，數(shù)據(jù)域賦值為value
ListNode* Front = phead->next;//記錄頭結(jié)點(diǎn)的后一個結(jié)點(diǎn)位置
//建立新結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的雙向關(guān)系
phead->next = newNode;
newNode->front = phead;
//建立新結(jié)點(diǎn)與front結(jié)點(diǎn)之間的雙向關(guān)系
newNode->next = Front; //這時候不能用phead了，因?yàn)閜head
Front->front = newNode;
}
?5. 鏈表的頭刪
實(shí)現(xiàn)步驟：
-
參數(shù)驗(yàn)證：
assert(phead);使用assert函數(shù)確保傳入的頭節(jié)點(diǎn)指針phead不是NULL。這一步防止后續(xù)代碼在空指針上進(jìn)行操作，可能導(dǎo)致程序崩潰。assert(phead->next != phead);確保鏈表中除頭節(jié)點(diǎn)外還有其他節(jié)點(diǎn)。如果頭節(jié)點(diǎn)的next指針指向自己，說明鏈表為空，此時不能進(jìn)行刪除操作。 -
定位節(jié)點(diǎn)：
ListNode* Front = phead->next;這行代碼定位到鏈表的當(dāng)前前端節(jié)點(diǎn)，即頭節(jié)點(diǎn)后的第一個節(jié)點(diǎn)。ListNode* newFront = Front->next;獲取當(dāng)前前端節(jié)點(diǎn)的下一個節(jié)點(diǎn)，這將成為新的前端節(jié)點(diǎn)。 -
重建鏈接：
phead->next = newFront;更新頭節(jié)點(diǎn)的next指針，直接指向newFront，從而繞過Front節(jié)點(diǎn)。newFront->front = phead;更新newFront的front指針，指向頭節(jié)點(diǎn)，確保從新的前端節(jié)點(diǎn)向前遍歷可以回到頭節(jié)點(diǎn)。 -
釋放內(nèi)存：
free(Front);釋放原前端節(jié)點(diǎn)Front所占的內(nèi)存。這一步是必須的，以避免內(nèi)存泄漏。
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* Front = phead->next;//記錄頭結(jié)點(diǎn)的后一個結(jié)點(diǎn)
ListNode* newFront = front->next;//記錄front結(jié)點(diǎn)的后一個結(jié)點(diǎn)
//建立頭結(jié)點(diǎn)與newFront結(jié)點(diǎn)之間的雙向關(guān)系
phead->next = newFront;
newFront->front = phead;
free(Front);//釋放Front結(jié)點(diǎn)
}
6. 鏈表的尾插
實(shí)現(xiàn)步驟：
-
參數(shù)驗(yàn)證：
assert(phead);使用assert函數(shù)確保傳入的頭節(jié)點(diǎn)指針phead不是NULL。這個檢查是為了防止在空指針上執(zhí)行操作，這可能會導(dǎo)致程序崩潰。 -
創(chuàng)建新節(jié)點(diǎn)：
ListNode* newNode = CreateNode(value);這行代碼調(diào)用CreateNode函數(shù)，創(chuàng)建一個新的ListNode對象，并將value設(shè)置為節(jié)點(diǎn)的數(shù)據(jù)。CreateNode函數(shù)返回一個已經(jīng)初始化的新節(jié)點(diǎn)，它的front和next指針指向自己，形成一個獨(dú)立的小循環(huán)。 -
定位尾節(jié)點(diǎn)：
ListNode* tail = phead->front;獲取當(dāng)前的尾節(jié)點(diǎn)，即頭節(jié)點(diǎn)的前一個節(jié)點(diǎn)。 -
連接新節(jié)點(diǎn)與頭節(jié)點(diǎn)：
newNode->next = phead;將新節(jié)點(diǎn)的next指針指向頭節(jié)點(diǎn)，確保新節(jié)點(diǎn)成為鏈表的最后一個節(jié)點(diǎn)，其后繼指向頭節(jié)點(diǎn)。phead->front = newNode;更新頭節(jié)點(diǎn)的front指針指向新節(jié)點(diǎn)，從而將新節(jié)點(diǎn)正式連接到鏈表的尾部。 -
連接新節(jié)點(diǎn)與原尾節(jié)點(diǎn)：
tail->next = newNode;將原尾節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)，這樣原尾節(jié)點(diǎn)之后就是新節(jié)點(diǎn)了。newNode->front = tail;將新節(jié)點(diǎn)的front指針指向原尾節(jié)點(diǎn)，確保從新節(jié)點(diǎn)向前遍歷可以到達(dá)原尾節(jié)點(diǎn)。
void ListPushBack(ListNode* phead, LTDataType value)
{
assert(phead);
ListNode* newNode = CreateNode(value);//申請一個結(jié)點(diǎn)，數(shù)據(jù)域賦值為x
ListNode* tail = phead->front;//記錄頭結(jié)點(diǎn)的前一個結(jié)點(diǎn)的位置
//建立新結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的雙向關(guān)系
newNode->next = phead;
phead->front = newNode;
//建立新結(jié)點(diǎn)與tail結(jié)點(diǎn)之間的雙向關(guān)系
tail->next = newNode;
newNode->front = tail;
}
?7. 鏈表的尾刪
實(shí)現(xiàn)步驟：
-
校驗(yàn)傳入的頭節(jié)點(diǎn)：使用
assert(phead)確保傳入的頭節(jié)點(diǎn)指針phead是有效的。這是為了防止空指針引用，確保鏈表至少被初始化。使用assert(phead->next != phead)確保鏈表不是空的（即鏈表中除了頭節(jié)點(diǎn)之外還有其他節(jié)點(diǎn)）。這個檢查是必要的，因?yàn)榭真湵恚ㄖ挥蓄^節(jié)點(diǎn)指向自己）無法進(jìn)行尾部刪除操作。 -
定位尾部節(jié)點(diǎn)和新尾部節(jié)點(diǎn)：使用
ListNode* Tail = phead->front;定位到當(dāng)前的尾部節(jié)點(diǎn)（即頭節(jié)點(diǎn)的前一個節(jié)點(diǎn)Tail），這是要被移除的節(jié)點(diǎn)。使用ListNode* newTail = Tail->front;定位到新的尾部節(jié)點(diǎn)，即當(dāng)前尾部節(jié)點(diǎn)的前一個節(jié)點(diǎn)newTail。 -
重建頭節(jié)點(diǎn)與新尾部節(jié)點(diǎn)之間的鏈接：設(shè)置新尾部節(jié)點(diǎn)的
next指針指向頭節(jié)點(diǎn)，即newTail->next = phead;，這樣從新尾部節(jié)點(diǎn)向后遍歷即可直接到達(dá)頭節(jié)點(diǎn)。設(shè)置頭節(jié)點(diǎn)的front指針指向新尾部節(jié)點(diǎn)，即phead->front = newTail;，這樣從頭節(jié)點(diǎn)向前遍歷即可直接到達(dá)新尾部節(jié)點(diǎn)。 -
釋放原尾部節(jié)點(diǎn)的內(nèi)存：使用
free(Tail);釋放原尾部節(jié)點(diǎn)Tail占用的內(nèi)存。這一步是必須的，以避免內(nèi)存泄漏。
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* Tail = phead->front;//記錄頭結(jié)點(diǎn)的前一個結(jié)點(diǎn)
ListNode* newTail = Tail->front;//記錄tail結(jié)點(diǎn)的前一個結(jié)點(diǎn)
//建立頭結(jié)點(diǎn)與newtail結(jié)點(diǎn)之間的雙向關(guān)系
newTail->next = phead;
phead->front = newTail;
free(Tail);//釋放Tail結(jié)點(diǎn)
}
8. 在pos位置插入節(jié)點(diǎn)
實(shí)現(xiàn)步驟：
-
校驗(yàn)傳入的節(jié)點(diǎn)指針：使用
assert(pos)確保傳入的節(jié)點(diǎn)指針pos是有效的。這一步驟防止空指針引用，保證程序的健壯性。 -
定位前驅(qū)節(jié)點(diǎn)：使用
ListNode* before = pos->front;獲取pos節(jié)點(diǎn)的前一個節(jié)點(diǎn)before。這樣做是為了接下來將新節(jié)點(diǎn)插入到before和pos之間。 -
創(chuàng)建新節(jié)點(diǎn)：調(diào)用
CreateNode(value)函數(shù)創(chuàng)建一個新的節(jié)點(diǎn)newNode，其中value是新節(jié)點(diǎn)的數(shù)據(jù)值。這個函數(shù)應(yīng)該分配內(nèi)存并初始化新節(jié)點(diǎn)的data字段和指針字段。 -
建立新節(jié)點(diǎn)與前驅(qū)節(jié)點(diǎn)的關(guān)系：設(shè)置
before節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)，即before->next = newNode;，這樣before和新節(jié)點(diǎn)之間的鏈接就建立了。設(shè)置新節(jié)點(diǎn)的front指針指向before，即newNode->front = before;，確保新節(jié)點(diǎn)能正確鏈接到鏈表中。 -
建立新節(jié)點(diǎn)與指定位置節(jié)點(diǎn)的關(guān)系：設(shè)置新節(jié)點(diǎn)的
next指針指向pos，即newNode->next = pos;，將新節(jié)點(diǎn)直接鏈接到pos節(jié)點(diǎn)前面。設(shè)置pos節(jié)點(diǎn)的front指針指向新節(jié)點(diǎn)，即pos->front = newNode;，完成從pos節(jié)點(diǎn)到新節(jié)點(diǎn)的雙向鏈接。
//在指定位置插入結(jié)點(diǎn)
void ListInsert(ListNode* pos, LTDataType value)
{
assert(pos);
ListNode* before = pos->front;//記錄pos指向結(jié)點(diǎn)的前一個結(jié)點(diǎn)
ListNode* newNode = CreateNode(value);//申請一個結(jié)點(diǎn)，數(shù)據(jù)域賦值為x
//建立新結(jié)點(diǎn)與before結(jié)點(diǎn)之間的雙向關(guān)系
before->next = newNode;
newNode->front = before;
//建立新結(jié)點(diǎn)與pos指向結(jié)點(diǎn)之間的雙向關(guān)系
newNode->next = pos;
pos->front = newNode;
}
9. 在pos位置刪除節(jié)點(diǎn)
實(shí)現(xiàn)步驟：
-
檢查有效性：使用
assert(pos)來確保傳入的節(jié)點(diǎn)指針pos是有效的，即不為NULL。這是一個基本的安全檢查，防止對空指針進(jìn)行操作，這樣的操作可能導(dǎo)致程序崩潰 -
定位前驅(qū)和后繼節(jié)點(diǎn)：使用
ListNode* before = pos->front;獲取pos節(jié)點(diǎn)的前一個節(jié)點(diǎn)，并將其存儲在變量before中。使用ListNode* after = pos->next;獲取pos節(jié)點(diǎn)的后一個節(jié)點(diǎn)，并將其存儲在變量after中。 -
重建鏈接：將
before節(jié)點(diǎn)的next指針指向after節(jié)點(diǎn)，即before->next = after;。這步操作是斷開before節(jié)點(diǎn)與pos節(jié)點(diǎn)之間的鏈接，并直接鏈接到after節(jié)點(diǎn)。 - 將
after節(jié)點(diǎn)的front指針指向before節(jié)點(diǎn)，即after->front = before;。這步操作是斷開after節(jié)點(diǎn)與pos節(jié)點(diǎn)之間的鏈接，并直接鏈接到before節(jié)點(diǎn)。 -
釋放內(nèi)存：使用
free(pos);釋放pos指針指向的節(jié)點(diǎn)所占用的內(nèi)存。這是清理資源的重要步驟，避免內(nèi)存泄漏。
//刪除指定位置結(jié)點(diǎn)
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* before = pos->front;//記錄pos指向結(jié)點(diǎn)的前一個結(jié)點(diǎn)
ListNode* after = pos->next;//記錄pos指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)
//建立before結(jié)點(diǎn)與after結(jié)點(diǎn)之間的雙向關(guān)系
before->next = after;
after->front = before;
free(pos);//釋放pos指向的結(jié)點(diǎn)
}
10. 鏈表判空
實(shí)現(xiàn)步驟：文章來源：http://www.zghlxwxcb.cn/news/detail-858488.html
-
檢查頭節(jié)點(diǎn)的后繼指針：在帶頭的雙向循環(huán)鏈表中，頭節(jié)點(diǎn)（哨兵節(jié)點(diǎn)）不存儲數(shù)據(jù)。鏈表為空的標(biāo)準(zhǔn)是頭節(jié)點(diǎn)的
next指針指向自身。 -
檢查頭節(jié)點(diǎn)的前驅(qū)指針：為了確保鏈表完整性，也應(yīng)驗(yàn)證頭節(jié)點(diǎn)的
prev指針是否也指向自身。
bool isEmpty(ListNode* *phead) {
return (phead->next == phead && head->front == phead);
}11.?獲取鏈表中的元素個數(shù)
實(shí)現(xiàn)步驟：文章來源地址http://www.zghlxwxcb.cn/news/detail-858488.html
- 初始化計(jì)數(shù)器: 創(chuàng)建一個變量來保存節(jié)點(diǎn)的數(shù)量。
- 遍歷鏈表: 從鏈表的頭節(jié)點(diǎn)開始，遍歷每一個節(jié)點(diǎn)，直到鏈表末尾。
- 遞增計(jì)數(shù)器: 每訪問一個節(jié)點(diǎn)，計(jì)數(shù)器增加1。
- 返回結(jié)果: 遍歷完整個鏈表后，計(jì)數(shù)器的值即為鏈表中的元素個數(shù)。
//獲取鏈表中的元素個數(shù)
int ListSize(ListNode* phead)
{
assert(phead);
int count = 0;//初始化計(jì)數(shù)器
ListNode* cur = phead->next;//從頭節(jié)點(diǎn)的后一個結(jié)點(diǎn)開始遍歷
while (cur != phead)//當(dāng)cur指向頭節(jié)點(diǎn)時，遍歷完畢，頭節(jié)點(diǎn)不計(jì)入總元素個數(shù)
{
count++;
cur = cur->next;
}
return count;//返回元素個數(shù)
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) - 鏈表詳解（二）—— 帶頭雙向循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
