深入分析 linux 內核鏈表

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

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

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

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