目錄
一、循環(huán)單鏈表
二、循環(huán)雙鏈表
一、循環(huán)單鏈表
循環(huán)單鏈表的表尾結(jié)點的next指針總是指向頭結(jié)點。?
所以在初始化循環(huán)單鏈表的時候，需要記得將頭結(jié)點的next指針指向頭結(jié)點自己：
?
判斷循環(huán)單鏈表是否為空，只要判斷頭結(jié)點的next指針是否指向自己就可以了，因為循環(huán)鏈表的最后一個結(jié)點的next指針總是指向頭結(jié)點的，如果為空，那就只能是頭結(jié)點的next指針指向自己了：
判斷結(jié)點是否是循環(huán)單鏈表的表尾結(jié)點，只需判斷該結(jié)點的next指針是否指向頭結(jié)點即可，因為循環(huán)鏈表的最后一個結(jié)點的next指針總是指向頭結(jié)點的：
?
循環(huán)單鏈表有一些重要的性質(zhì)：1、從一個結(jié)點出發(fā)，無論這個結(jié)點位于鏈表的哪里，都可以找到其他任何一個結(jié)點，而單鏈表不行。
2、在一些情況下，我們需要頻繁對鏈表的頭部和尾部進行操作，此時使用循環(huán)單鏈表就很有用，原因是對于單鏈表，已知頭結(jié)點，想找到最后一個結(jié)點的話，時間復雜度是O(n)；但是對于循環(huán)單鏈表，我們可以一開始就把頭指針指向尾結(jié)點，這樣找到尾結(jié)點所需時間復雜度是O(1)，因為尾結(jié)點的next指針總是指向頭結(jié)點，所以找到頭結(jié)點的時間復雜度也是O(1)。因此，循環(huán)單鏈表在這種情況下的表現(xiàn)明顯優(yōu)于普通的單鏈表。
二、循環(huán)雙鏈表
先拿雙鏈表和循環(huán)雙鏈表做個對比：
雙鏈表：
?循環(huán)雙鏈表：
?
在初始化循環(huán)雙鏈表的時候，需要記得將頭結(jié)點的前指針和后指針都指向頭結(jié)點自己：
?像這樣↓
?
根據(jù)以上性質(zhì)，所以在判斷循環(huán)雙鏈表是否為空時，只需判斷頭指針的next指針是否指向頭結(jié)點自身即可：
?
判斷當前結(jié)點時都是循環(huán)雙鏈表的表尾結(jié)點，只要判斷當前節(jié)點的next指針是否指向頭結(jié)點即可：
?
下面來看一下雙鏈表和循環(huán)雙鏈表在插入與刪除上的區(qū)別：
在p結(jié)點之后插入s結(jié)點，雙鏈表的代碼是這樣的：
有一個明顯的缺陷，即當p結(jié)點正好是尾結(jié)點的話，代碼的第二句"p->next->piror=s"會出錯，因為p->next指向NULL；?但是如果是循環(huán)雙鏈表的話，上述代碼就是正確的，因為循環(huán)雙鏈表中，即使p是尾結(jié)點，它的next指針的指向也是非空的，因此就不會出錯了。
同理當刪除p的后繼節(jié)點q，雙鏈表的代碼↓
文章來源：http://www.zghlxwxcb.cn/news/detail-483928.html
?q結(jié)點位于尾結(jié)點位置，雙鏈表代碼就會出錯，而循環(huán)鏈表不會。文章來源地址http://www.zghlxwxcb.cn/news/detail-483928.html
到了這里，關于循環(huán)鏈表詳解(循環(huán)單鏈表/循環(huán)雙鏈表)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C語言實現(xiàn)]帶你手撕帶頭循環(huán)雙鏈表](https://imgs.yssmx.com/Uploads/2024/02/464006-1.png)
