深入分析 linux 內(nèi)核鏈表

1、深入分析Linux內(nèi)核鏈表級(jí)別：初級(jí)楊沙洲(pubb@)國防科技大學(xué)計(jì)算機(jī)學(xué)院2004年8月01日本文詳細(xì)分析了2.6.x內(nèi)核中鏈表結(jié)構(gòu)的實(shí)現(xiàn)，并通過實(shí)例對(duì)每個(gè)鏈表操作接口進(jìn)行了詳盡的講解。一、一、鏈表數(shù)據(jù)結(jié)構(gòu)簡介鏈表數(shù)據(jù)結(jié)構(gòu)簡介鏈表是一種常用的組織有序數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，它通過指針將一系列數(shù)據(jù)節(jié)點(diǎn)連接成一條數(shù)據(jù)鏈，是線性表的一種重要實(shí)現(xiàn)方式。相對(duì)于數(shù)組，鏈表具有更好的動(dòng)態(tài)性，建立鏈表時(shí)無需預(yù)先知道數(shù)據(jù)總量，可以隨機(jī)分配空間，可以高效地在鏈

2、表中的任意位置實(shí)時(shí)插入或刪除數(shù)據(jù)。鏈表的開銷主要是訪問的順序性和組織鏈的空間損失。通常鏈表數(shù)據(jù)結(jié)構(gòu)至少應(yīng)包含兩個(gè)域：數(shù)據(jù)域和指針域，數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù)，指針域用于建立與下一個(gè)節(jié)點(diǎn)的聯(lián)系。按照指針域的組織以及各個(gè)節(jié)點(diǎn)之間的聯(lián)系形式，鏈表又可以分為單鏈表、雙鏈表、循環(huán)鏈表等多種類型，下面分別給出這幾類常見鏈表類型的示意圖：1單鏈表單鏈表圖1單鏈表單鏈表單鏈表是最簡單的一類鏈表，它的特點(diǎn)是僅有一個(gè)指針域指向后繼節(jié)點(diǎn)（next），因此，對(duì)單鏈表

3、的遍歷只能從頭至尾（通常是NULL空指針）順序進(jìn)行。2雙鏈表雙鏈表圖2雙鏈表雙鏈表通過設(shè)計(jì)前驅(qū)和后繼兩個(gè)指針域，雙鏈表可以從兩個(gè)方向遍歷，這是它區(qū)別于單鏈表的地方。如果打亂前驅(qū)、后繼的依賴關(guān)系，就可以構(gòu)成“二叉樹“；如果再讓首節(jié)點(diǎn)的前驅(qū)指向鏈表尾節(jié)點(diǎn)、尾節(jié)點(diǎn)的后繼指向首節(jié)點(diǎn)（如圖2中虛線部分），就構(gòu)成了循環(huán)鏈表；如果設(shè)計(jì)更多的指針域，就可以構(gòu)成各種復(fù)雜的樹狀數(shù)據(jù)結(jié)構(gòu)。3循環(huán)鏈表循環(huán)鏈表2010919深入分析Linux內(nèi)核鏈表develo

4、perwks…lchain19三、三、鏈表操作接口鏈表操作接口1.聲明和初始化聲明和初始化實(shí)際上Linux只定義了鏈表節(jié)點(diǎn)，并沒有專門定義鏈表頭，那么一個(gè)鏈表結(jié)構(gòu)是如何建立起來的呢？讓我們來看看LIST_HEAD()這個(gè)宏：#defineLIST_HEAD_INIT(name)除了用LIST_HEAD()宏在聲明的時(shí)候初始化一個(gè)鏈表以外，Linux還提供了一個(gè)INIT_LIST_HEAD宏用于運(yùn)行時(shí)初始化鏈表：#defineINIT_L