 |
|||||||||||||||||||||||||||||||||||
嵌入式linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表 |
|||||||||||||||||||||||||||||||||||
|
鏈表作為嵌入式Linux內(nèi)核中常見的數(shù)據(jù)結(jié)構(gòu)，在之前的文章里我們分別介紹過了單向鏈表和雙向鏈表，今天主要介紹的則是循環(huán)列表。 單向鏈表的后一個節(jié)點的指針域為空（NULL）。如果將這個指針利用起來，以指向單向鏈表的第一個節(jié)點，就能組成一個單向循環(huán)鏈表，如圖1.1所示。
可以看到，循環(huán)鏈表的組織結(jié)構(gòu)與單鏈表非常相似，因此其操作與單鏈表也是一致的，惟一的差別僅在于在單鏈表中，算法判端到達鏈表尾的條件是p→next是否為空，而在雙鏈表中，則是判斷p→next是否等于頭指針。 總而言之，循環(huán)鏈表的運算與單鏈表的運算基本一致，所不同的有以下幾點： 1、在建立一個循環(huán)鏈表時，必須使其后一個結(jié)點的指針指向表頭結(jié)點，而不是像單鏈表那樣置為NULL。此種情況還使用于在后一個結(jié)點后插入一個新的結(jié)點。 2、在判斷是否到表尾時，是判斷該結(jié)點鏈域的值是否是表頭結(jié)點，當(dāng)鏈域值等于表頭指針時，說明已到表尾。而非像單鏈表那樣判斷鏈域值是否為NULL。 表1.1總結(jié)了各種鏈表的異同點。 表1.1 各種鏈表的異同點
熱點鏈接：
1、嵌入式linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)之雙向鏈表 |
