一、 鏈表數據結構簡介 鏈表是一種常用的組織有序數據的數據結構，它通過指針將一系列數據節點連接成一條數據鏈，是線性表的一種重要實現方式。相對於數組，鏈表具有更好的動態性，建立鏈表時無需預先知道數據總量，可以隨機分配空間，可以高效地在鏈表中的任意位置實時插入或刪除數據。鏈表的開銷主要是訪問的順序性和組織鏈的空間損失。 通常鏈表數據結構至少應包含兩個域：數據域和指針域，數據域用於存儲數據，指針域用於建立與下一個節點的聯系。按照指針域的組織以及各個節點之間的聯系形式，鏈表又可以分為單鏈表、雙鏈表、循環鏈表等多種類型，下面分別給出這幾類常見鏈表類型的示意圖： 1. 單鏈表 單鏈表是最簡單的一類鏈表，它的特點是僅有一個指針域指向後繼節點（next），因此，對單鏈表的遍歷只能從頭至尾（通常是 NULL 空指針）順序進行。 2. 雙鏈表 通過設計前驅和後繼兩個指針域，雙鏈表可以從兩個方向遍歷，這是它區別於單鏈表的地方。如果打亂前驅、後繼的依賴關系，就可以構成"二叉樹"；如果再讓首節點的前驅指向鏈表尾節點、尾節點的後繼指向首節點（如圖2中虛線部分），就構成了循環鏈表；如果設計更多的指針域，就可以構成各種復雜的樹狀數據結構。 3. 循環鏈表 循環鏈表的特點是尾節點的後繼指向首節點。前面已經給出了雙循環鏈表的示意圖，它的特點是從任意一個節點出發，沿兩個方向的任何一個，都能找到鏈表中的任意一個數據。如果去掉前驅指針，就是單循環鏈表。 在Linux內核中使用了大量的鏈表結構來組織數據，包括設備列表以及各種功能模塊中的數據組織。這些鏈表大多采用在[include/linux/list.h]實現的一個相當精彩的鏈表數據結構。本文的後繼部分就將通過示例詳細介紹這一數據結構的組織和使用。
二、 Linux 2.6 內核鏈表數據結構的實現 盡管這裡使用2.6內核作為講解的基礎，但實際上 2.4 內核中的鏈表結構和 2.6 並沒有什麼區別。不同之處在於 2.6 擴充了兩種鏈表數據結構：鏈表的讀拷貝更新（rcu）和 HASH 鏈表（hlist）。這兩種擴展都是基於最基本的 list 結構，因此，本文主要介紹基本鏈表結構，然後再簡要介紹一下 rcu 和 hlist。 鏈表數據結構的定義很簡單（節選自 [include/linux/list.h]，以下所有代碼，除非加以說明，其余均取自該文件）： strUCt list_head { struct list_head *next, *prev; }; list_head 結構包含兩個指向 list_head 結構的指針 prev 和 next，由此可見，內核的鏈表具備雙鏈表功能，實際上，通常它都組織成雙循環鏈表。 和第一節介紹的雙鏈表結構模型不同，這裡的 list_head 沒有數據域。在 Linux 內核鏈表中，不是在鏈表結構中包含數據，而是在數據結構中包含鏈表節點。 在數據結構課本中，鏈表的經典定義方式通常是這樣的（以單鏈表為例）： struct list_node { struct list_node *next; ElemType data; }; 因為 ElemType 的緣故，對每一種數據項類型都需要定義各自的鏈表結構。有經驗的 C++ 程序員應該知道，標准模板庫中的 采用的是 C++ Template，利用模板抽象出和數據項類型無關的鏈表操作接口。 在 Linux 內核鏈表中，需要用鏈表組織起來的數據通常會包含一個 struct list_head 成員，例如在 [include/linux/netfilter.h] 中定義了一個 nf_sockopt_ops 結構來描述 Netfilter 為某一協議族准備的 getsockopt/setsockopt 接口，其中就有一個（struct list_head list）成員，各個協議族的 nf_sockopt_ops 結構都通過這個 list 成員組織在一個鏈表中，表頭是定義在 [net/core/netfilter.c] 中的 nf_sockopts（struct list_head）。從下圖中我們可以看到，這種通用的鏈表結構避免了為每個數據項類型定義自己的鏈表的麻煩。 Linux 的簡捷實用、不求完美和標准的風格，在這裡體現得相當充分。
三、 鏈表操作接口 1. 聲明和初始化 實際上 Linux 只定義了鏈表節點，並沒有專門定義鏈表頭，那麼一個鏈表結構是如何建立起來的呢？讓我們來看看 LIST_HEAD() 這個宏： #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) 當我們用 LIST_HEAD(nf_sockopts) 聲明一個名為 nf_sockopts 的鏈表頭時，它的 next、prev 指針都初始化為指向自己，這樣，我們就有了一個空鏈表，因為 Linux 用頭指針的 next 是否指向自己來判斷鏈表是否為空： static inline int list_empty(const struct list_head *head) { return head->next == head; } 除了用 LIST_HEAD() 宏在聲明的時候初始化一個鏈表以外，Linux 還提供了一個 INIT_LIST_HEAD 宏用於運行時初始化鏈表： #define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr); } while (0) 我們用 INIT_LIST_HEAD(&nf_sockopts) 來使用它。 2. 插入/刪除/合並 a) 插入 對鏈表的插入操作有兩種：在表頭插入和在表尾插入。Linux為此提供了兩個接口： static inline void list_add(struct list_head *new, struct list_head *head); static inline void list_add_tail(struct list_head *new, struct list_head *head); 因為 Linux 鏈表是循環表，且表頭的 next、prev 分別指向鏈表中的第一個和最末一個節點，所以，list_add 和 list_add_tail 的區別並不大，實際上，Linux 分別用 __list_add(new, head, head->next); 和 __list_add(new, head->prev, head); 來實現兩個接口，可見，在表頭插入是插入在 head 之後，而在表尾插入是插入在 head->prev 之後。 假設有一個新 nf_sockopt_ops 結構變量 new_sockopt 需要添加到 nf_sockopts 鏈表頭，我們應當這樣操作： list_add(&new_sockopt.list, &nf_sockopts); 從這裡我們看出，nf_sockopts 鏈表中記錄的並不是 new_sockopt 的地址，而是其中的 list 元素的地址。如何通過鏈表訪問到 new_sockopt 呢？下面會有詳細介紹。 b) 刪除 static inline void list_del(struct list_head *entry); 當我們需要刪除 nf_sockopts 鏈表中添加的 new_sockopt 項時，我們這麼操作： list_del(&new_sockopt.list); 被剔除下來的 new_sockopt.list，prev、next 指針分別被設為 LIST_POSITION2 和 LIST_POSITION1 兩個特殊值，這樣設置是為了保證不在鏈表中的節點項不可訪問--對 LIST_POSITION1 和 LIST_POSITION2 的訪問都將引起頁故障。與之相對應， list_del_init() 函數將節點從鏈表中解下來之後，調用 LIST_INIT_HEAD() 將節點置為空鏈狀態。 c) 搬移 Linux 提供了將原本屬於一個鏈表的節點移動到另一個鏈表的操作，並根據插入到新鏈表的位置分為兩類： static inline void list_move(struct list_head *list, struct list_head *head); static inline void list_move_tail(struct list_head *list, struct list_head *head); 例如 list_move(&new_sockopt.list,&nf_sockopts) 會把 new_sockopt 從它所在的鏈表上刪除，並將其再鏈入 nf_sockopts 的表頭。 d) 合並 除了針對節點的插入、刪除操作，Linux 鏈表還提供了整個鏈表的插入功能： static inline void list_splice(struct list_head *list, struct list_head *head); 假設當前有兩個鏈表，表頭分別是 list1 和 list2（都是 struct list_head 變量），當調用 list_splice(&list1,&list2) 時，只要 list1 非空，list1 鏈表的內容將被掛接在 list2 鏈表上，位於 list2 和 list2.next（原 list2 表的第一個節點）之間。新 list2 鏈表將以原 list1 表的第一個節點為首節點，而尾節點不變。如圖（虛箭頭為next指針）： 當 list1 被掛接到 list2 之後，作為原表頭指針的 list1 的 next、prev 仍然指向原來的節點，為了避免引起混亂，Linux 提供了一個 list_splice_init() 函數： static inline void list_splice_init(struct list_head *list, struct list_head *head); 該函數在將 list 合並到 head 鏈表的基礎上，調用 INIT_LIST_HEAD(list) 將 list 設置為空鏈。 3. 遍歷 遍歷是鏈表最經常的操作之一，為了方便核心應用遍歷鏈表，Linux 鏈表將遍歷操作抽象成幾個宏。在介紹遍歷宏之前，我們先看看如何從鏈表中訪問到我們真正需要的數據項。 a) 由鏈表節點到數據項變量 我們知道，Linux 鏈表中僅保存了數據項結構中 list_head 成員變量的地址，那麼我們如何通過這個 list_head 成員訪問到作為它的所有者的節點數據呢？Linux 為此提供了一個 list_entry(ptr,type,member) 宏，其中ptr是指向該數據中 list_head 成員的指針，也就是存儲在鏈表中的地址值，type 是數據項的類型，member 則是數據項類型定義中 list_head 成員的變量名，例如，我們要訪問 nf_sockopts 鏈表中首個 nf_sockopt_ops 變量，則如此調用： list_entry(nf_sockopts->next, struct nf_sockopt_ops, list); 這裡 "list" 正是 nf_sockopt_ops 結構中定義的用於鏈表操作的節點成員變量名。
