鏈表是我們學(xué)習(xí)C語(yǔ)言避不開(kāi)的問(wèn)題柑晒，就讓我們一起飛過(guò)去看看吧：
1 定義鏈表
鏈表是C語(yǔ)言編程中常用的數(shù)據(jù)結(jié)構(gòu)浇揩，比如我們要建一個(gè)整數(shù)鏈表，一般可能這么定義：
struct int_node {
int val;
struct int_node *next;
};
2 定義功能函數(shù)
為了實(shí)現(xiàn)鏈表的插入航徙、刪除钳降、遍歷等功能，另外要再實(shí)現(xiàn)一系列函數(shù)泰涂，比如：
void insert_node(struct int_node **head, int val);
void delete_node(struct int_node *head, struct int_node *current);
void access_node(struct int_node *head)
{
struct int_node *node;
for (node = head; node != NULL; node = node->next) {
// do something here
}
}
如果我們的代碼里只有這么一個(gè)數(shù)據(jù)結(jié)構(gòu)的話(huà)鲫竞，這樣做當(dāng)然沒(méi)有問(wèn)題，但是當(dāng)代碼的規(guī)模足夠大逼蒙，需要管理很多種鏈表从绘，難道需要為每一種鏈表都要實(shí)現(xiàn)一套插入、刪除是牢、遍歷等功能函數(shù)嗎僵井？
熟悉C++的同學(xué)可能會(huì)說(shuō)，我們可以用標(biāo)準(zhǔn)模板庫(kù)啊驳棱，但是批什，我們這里談的是C，在C語(yǔ)言里有沒(méi)有比較好的方法呢社搅？
Linux內(nèi)核中一般使用雙向鏈表驻债，聲明為struct list_head，這個(gè)結(jié)構(gòu)體是在include/linux/types.h中定義的形葬，鏈表的訪(fǎng)問(wèn)是以宏或者內(nèi)聯(lián)函數(shù)的形式在include/linux/list.h中定義合呐。
struct list_head {
struct list_head *next, *prev;
};
Linux內(nèi)核為鏈表提供了一致的訪(fǎng)問(wèn)接口。
void INIT_LIST_HEAD(struct list_head *list)笙以；
void list_add(struct list_head *new, struct list_head *head)淌实；
void list_add_tail(struct list_head *new, struct list_head *head)；
void list_del(struct list_head *entry);
int list_empty(const struct list_head *head)
；
以上只是從Linux內(nèi)核里摘選的幾個(gè)常用接口拆祈，更多的定義請(qǐng)參考Linux內(nèi)核源代碼恨闪。
3 處理鏈表
我們先通過(guò)一個(gè)簡(jiǎn)單的實(shí)作來(lái)對(duì)Linux內(nèi)核如何處理鏈表建立一個(gè)感性的認(rèn)識(shí)。
#include <stdio.h>
#include "list.h"
struct int_node {
int val;
struct list_head list;
};
int main()
{
struct list_head head, *plist;
struct int_node a, b;
a.val = 2;
b.val = 3;
INIT_LIST_HEAD(&head);
list_add(&a.list, &head);
list_add(&b.list, &head);
list_for_each(plist, &head) {
struct int_node *node = list_entry(plist, struct int_node, list);
printf("val = %d\n", node->val);
}
return 0;
}
看完這個(gè)實(shí)作缘屹，是不是覺(jué)得在C代碼里管理一個(gè)鏈表也很簡(jiǎn)單呢凛剥？
代碼中包含的頭文件list.h是我從Linux內(nèi)核里抽取出來(lái)并做了一點(diǎn)修改的鏈表處理代碼，現(xiàn)附在這里給大家參考轻姿，使用的時(shí)候只要把這個(gè)頭文件包含到自己的工程里即可。
4 代碼
list_head通常是嵌在數(shù)據(jù)結(jié)構(gòu)內(nèi)使用逻炊，在上文的實(shí)作中我們還是以整數(shù)鏈表為例互亮，int_node的定義如下：
struct int_node {
int val;
struct list_head list;
};
使用list_head組織的鏈表的結(jié)構(gòu)如下圖所示：
遍歷鏈表是用宏list_for_each來(lái)完成。
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
在這里余素，pos和head均是struct list_head豹休。在遍歷的過(guò)程中如果需要訪(fǎng)問(wèn)節(jié)點(diǎn)，可以用list_entry來(lái)取得這個(gè)節(jié)點(diǎn)的基址桨吊。
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
我們來(lái)看看container_of是如何實(shí)現(xiàn)的威根。如下圖所示，我們已經(jīng)知道TYPE結(jié)構(gòu)中MEMBER的地址视乐，如果要得到這個(gè)結(jié)構(gòu)體的地址洛搀，只需要知道MEMBER在結(jié)構(gòu)體中的偏移量就可以了。如何得到這個(gè)偏移量地址呢佑淀？這里用到C語(yǔ)言的一個(gè)小技巧留美，我們不妨把結(jié)構(gòu)體投影到地址為0的地方，那么成員的絕對(duì)地址就是偏移量伸刃。得到偏移量之后谎砾，再根據(jù)ptr指針指向的地址，就可以很容易的計(jì)算出結(jié)構(gòu)體的地址捧颅。
list_entry就是通過(guò)上面的方法從ptr指針得到我們需要的type結(jié)構(gòu)體景图。
現(xiàn)在我們就從菜鳥(niǎo)變成不那么菜的鳥(niǎo)了，當(dāng)然碉哑，如果還有疑問(wèn)的小伙伴可以直接聯(lián)系我挚币，也可以加群710520381，邀請(qǐng)碼：柳貓谭梗，跟你們不見(jiàn)不散……
