? 在本次的博客當(dāng)中我們來向大家介紹一下雙向循環(huán)鏈表，在介紹雙向循環(huán)鏈表之前我們需要先來了解一下所有的鏈表的種類。

? 我們的鏈表大致分為八種：單向鏈表，雙向鏈表，帶頭結(jié)點的鏈表，不帶頭結(jié)點的鏈表，循環(huán)鏈表，不循環(huán)的鏈表。經(jīng)過組合一共分為八種。（單向不帶頭節(jié)點不循環(huán)的鏈表，雙向帶頭結(jié)點循環(huán)的鏈表......）

? 我們之前實現(xiàn)過一個單項鏈表。單項鏈表是我們在題目中最常見的題目類型，但是他不是最實用的，因為我們想要在特定的節(jié)點前方插入一個數(shù)據(jù)的時候就需要從頭開始遍歷，找到我們目標(biāo)節(jié)點的前一個位置，之后才可以進(jìn)行插入等操作。但是對于雙向鏈表來說，我們就不需要從頭開始進(jìn)行遍歷了，我們結(jié)構(gòu)體當(dāng)中會自動存儲一個指向前一個節(jié)點的指針，便于我們進(jìn)行操作。

? 雙向帶頭循環(huán)鏈表邏輯結(jié)構(gòu)如下：

? ?我們主要需要實現(xiàn)的鏈表當(dāng)中的函數(shù)如下:

? 在準(zhǔn)備函數(shù)的書寫的之前我們要像我們編寫單項鏈表的一樣，構(gòu)建一個結(jié)構(gòu)體，作為我們每一個節(jié)點的模板，便于后面使用。所示代碼如下：

?

? ? ? ??ListCreate函數(shù)

? 在我們第一次構(gòu)建循環(huán)鏈表的時候，最重要的就是創(chuàng)建頭節(jié)點，我們需要梳理好我們的邏輯，當(dāng)我們的鏈表當(dāng)中只存在我們的頭節(jié)點的時候，（也就代表我們我們鏈表當(dāng)中的數(shù)據(jù)項為0）我們同樣需要構(gòu)建一個循環(huán)鏈表，只不過我們的循環(huán)當(dāng)中只存在一個頭節(jié)點。就像是下面的結(jié)構(gòu)所示：
?

? 我們要完成的是我們對于頭節(jié)點的初始化的函數(shù)。所示代碼如下：

? 首先我們向堆區(qū)請求分配一個結(jié)構(gòu)體大小的空間，之后將我們的頭節(jié)點的指針更改為我們開辟出來的空間的地址，之后將我們節(jié)點當(dāng)中的數(shù)據(jù)初始化為 -1 并將我們的前一個指針和后一個指針均指向我們該節(jié)點。需要注意的是，我們有兩種改變頭節(jié)點的方式，第一種是在我們的參數(shù)當(dāng)中傳入一個二級指針，直接更改我們頭節(jié)點的地址的值。第二種是讓我們的函數(shù)返回處理好的地址，并在主函數(shù)當(dāng)中使用phead進(jìn)行接收。

? ? ? ??ListPushBack函數(shù)

? 在完成初始化節(jié)點之后我們就可以開始向我們的鏈表當(dāng)中嘗試著存儲數(shù)據(jù)了，我們先來構(gòu)建一個尾插函數(shù)，代碼如下：
? 首先我們開辟一個新的節(jié)點進(jìn)行接收我們創(chuàng)建的新的節(jié)點。

? ?之后我們想要將我們的新節(jié)點連接進(jìn)入我們的鏈表當(dāng)中，我們會發(fā)現(xiàn)想要在鏈表的尾部插入其實和在我們的phead之前插入是一樣的道理，因為我們每一次遍歷鏈表都是從phead開始的，所以最后遍歷到的節(jié)點只需要在我們頭節(jié)點的前方即可。我們將節(jié)點鏈接進(jìn)入我們的鏈表當(dāng)中：

? 就像是我們上圖中所示的那樣，我們需要更改四個指針的鏈接即可。但是我們需要注意的是我們需要提前創(chuàng)建一個結(jié)構(gòu)體指針將我們原鏈表當(dāng)中的尾節(jié)點保存起來，不然當(dāng)我們更改了phead頭指針之后就會丟失我們尾節(jié)點的地址。?

??? ? ??ListPrint函數(shù)

? 在完成了數(shù)據(jù)的插入之后我們僅僅在理論上完成了循環(huán)鏈表的構(gòu)建但是我們要想查看就還需要構(gòu)建一個打印函數(shù)。

? 對于打印函數(shù)我們依舊是遍歷整個鏈表，需要我們注意的也就是循環(huán)的結(jié)束條件了，循環(huán)鏈表在我們查找到最后一個節(jié)點的時候下一個節(jié)點就會回到我們的頭節(jié)點，所以我們只需要判斷我們節(jié)點的下一項是否為頭節(jié)點即可。結(jié)合我們尾插函數(shù)進(jìn)行代碼的檢測：

? ? ? ??ListPushFront函數(shù)

? 當(dāng)我們完成尾插函數(shù)之后和我們尾插函數(shù)邏輯相類似的就是我們的頭插函數(shù)，甚至我們還可以將我們的尾插函數(shù)直接復(fù)制粘貼到我們的頭插函數(shù)當(dāng)中，只需要修改部分邏輯即可：

? 唯一不同的就是我們對于鏈表的頭插函數(shù)需要將我們新開辟的節(jié)點插入到我們我們頭節(jié)點的后面

? 在這里我們需要創(chuàng)建一個結(jié)構(gòu)體指針變量保存我們原來鏈表當(dāng)中phead節(jié)點的下一個節(jié)點的地址，原理和我們的尾插函數(shù)相同。運行效果如下：

? ? ? ??ListPopFront函數(shù)

? 在構(gòu)建完我們的節(jié)點增加的函數(shù)之后就可以構(gòu)建我們的節(jié)點刪除的函數(shù)了：

? 首先我們需要判斷我們鏈表當(dāng)中是否存在存儲數(shù)據(jù)的節(jié)點，只有存儲數(shù)據(jù)的節(jié)點的時候我們才需要進(jìn)行刪除否則就直接返回即可。否則再刪除的話就有可能破壞循環(huán)鏈表的結(jié)構(gòu)。我們使用一個結(jié)構(gòu)體指針存儲我們第二個數(shù)據(jù)節(jié)點之后就可以刪除第一個節(jié)點了，之后再進(jìn)行略微的代碼的修改即可。? ?我們在這里需要更改兩個指針鏈接即可，就像是上圖中所示的那樣，我們不需要管拆下來的節(jié)點的指針指向，因為我們將其釋放之后就會將其置為空，不在對其進(jìn)行使用。?代碼測試如下：

? ? ? ??ListPopBack函數(shù)

? 和我們頭刪函數(shù)類似的是我們的尾刪函數(shù)，我們同樣可以將我們的代碼復(fù)制粘貼一份進(jìn)行復(fù)用：

? ?同樣的我們需要先對鏈表進(jìn)行判空操作，之后將我們鏈表當(dāng)中phead的前一個節(jié)點按照同樣的邏輯進(jìn)行刪除即可。運行結(jié)果如下：

? ? ? ???ListFind函數(shù)

? 之后再來構(gòu)建我們的查找函數(shù)。

? 我們第一步需要做的同樣是對鏈表進(jìn)行判空，如果鏈表當(dāng)中為空就可以直接返回NULL，并提示無法進(jìn)行查找。否則就進(jìn)行鏈表的遍歷，邏輯和我們打印函數(shù)類似，直到我們我們查找的節(jié)點下一個指向頭節(jié)點即可結(jié)束，如果在遍歷途中就可以返回節(jié)點的地址，如果沒有返回并且循環(huán)結(jié)束就代表沒有找到，就返回空指針。測試效果如下：

?

? ? ? ??ListInsert函數(shù)

? 有了查找函數(shù)之后我們的在指定位置插入刪除的函數(shù)構(gòu)建起來就方便多了。還記得我們在單鏈表的構(gòu)建過程當(dāng)中，在我們指定節(jié)點的位置前面插入新節(jié)點的時候，需要進(jìn)行遍歷，會造成效率上面的問題。代碼如下：

? 對于鏈表節(jié)點的插入邏輯和我們的頭插尾插相似。? ?測試效果如下：

? ? ? ??ListErase函數(shù)

? 之后刪除我們指定位置的節(jié)點，代碼編寫邏輯和我們的頭刪類似：

? 因為我們向函數(shù)的形參部分傳入的是一個指針，我們在查找時候接收到的指針代表著這個元素已經(jīng)存在，那么我們只需要直接使用即可，無需考慮鏈表當(dāng)中是否為空的情況。運行效果如下：

? ? ? ??ListDestory函數(shù)

? 最后我們在使用完我們的鏈表之后需要將我們的每一個節(jié)點都返回給我們的操作系統(tǒng)，否則就會存在內(nèi)存泄露的危險，因此我們最后還需要創(chuàng)建一個銷毀函數(shù)。代碼如下：

? 我們需要提前創(chuàng)建一個結(jié)構(gòu)體變量接收我們下一步驟當(dāng)中想要釋放的節(jié)點，循環(huán)釋放節(jié)點的邏輯和我們遍歷結(jié)構(gòu)體相似，我們依舊將我們的循環(huán)結(jié)束條件定義為判斷下一個地址是否為phead。

? 在編寫完上述代碼之后我們的循環(huán)鏈表也就正式編寫結(jié)束了，感謝您的觀看，下次博客再見。?文章來源地址http://www.zghlxwxcb.cn/news/detail-428560.html

到了這里，關(guān)于雙向鏈表的實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！