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