開發中接觸Linux越來越多，休息放松之余，免不了翻看翻看神秘的Linux的內核。看到雙向鏈表時，覺得挺有意思的，此文記下。

作為眾多基礎數據結構中的一員，雙向循環鏈表在各種“教科書”中的實現是相當的標準和一致的。

大概就是下面這個樣子：

1 typedef struct node_tag{2     //T data;3     struct node_tag *PRev;4     struct node_tag *next;5 }node;

當你需要某種類型的鏈表時，把數據成員之類的往節點里塞就是了。比如菜譜鏈表，里面就可以有宮爆雞丁，酸辣粉，地三鮮，水煮魚，麻辣雞翅。。。

嗯，當你需要另外一種鏈表時，接著如法炮制，只要功夫深，幾十上百也不是問題。有一部分人善于解決這類問題，它們叫做CP程序員(Copy-Paste)，

不要問我為什么知道。C++模板在這點上能實現通用特性，但不在本次內容之列了。

　　有著極客精神的Linux，在內核中肯定不會像上面這么做的。內核中有大量的數據結構需要使用雙向鏈表，諸如進程、模塊、文件。

難道要人去維護各種類型的雙向鏈表？而且還是不能復用的鏈表。我想沒多少人愿意把時間花在這種事情上吧。維護一種通用的不就好了。

鏈表節點，作為一個“連接件”，最本質的內容就是把一些對象鏈接起來，至于對象內部存儲的數據，是可以不用知道的。

在include/linux/list.h文件中，就有使用這樣的一個"連接件“：

struct list_head {    struct list_head *next, *prev;};

和node_tag相比，少了數據部分。

list_head作為獨立變量時，充當的是鏈表頭的角色；如果作為結構體成員時，則是“連接件”的角色。

　　在這樣的實現方式下，要獲得某種類型的鏈表，只需在宿主結構中聲明一個list_head成員，還可以任意的取名；

關鍵是，鏈表操作只需以list_head為對象進行實現；剩下唯一的問題是，在遍歷鏈表時，該如何獲取宿主結構的首地址？

畢竟鏈表是用來裝內容用的。這里利用編譯器的一個小技巧就可以算出地址偏移

#define offsetof(s,m)   (size_t)&(((s *)0)->m)

有了list_head相對宿主結構首地址的偏移，和自身地址來個加減就可以得到宿主的首地址，接下該怎么操作就怎么操作了。

個人覺得這里面有面向對象的意思。抽取出共同的“連接件” list_head，鏈表操作也以list_head為對象進行設計，

除了要具體訪問操作宿主結構之外，全部都是共性的東西。