链表的进阶：内核链表的设计思想

说实话，很多嵌入式工程师写链表，都是自己从头造轮子。每个节点里塞个next指针，再写一堆插入删除函数。我以前也这么干，直到看了Linux内核的链表实现——嗯，那感觉就像用惯了算盘突然见到了计算器。

内核链表的设计思想，说白了就一句话：把链表操作从具体数据结构中剥离出来。你想想看，我们平时写的链表，节点里既有数据又有指针，换个数据类型就得重写一套。内核的做法是——只维护指针，数据让使用者自己挂上去。

传统链表的问题在哪？

先看个典型的嵌入式链表代码：

struct student {
    int id;
    char name[32];
    struct student *next;  // 链表指针嵌在数据里
};

这种写法有什么毛病？我遇到过好几次：项目里要维护学生链表、设备链表、任务链表……每个都得写一套插入、删除、遍历函数。代码大量重复，而且容易出bug。更麻烦的是，如果需求变了，比如要在学生链表里加个字段，所有操作函数都得跟着改。

内核的做法完全不同。它定义了一个纯粹的链表节点结构体：

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

看到了吗？这个结构体里只有指针，没有数据。那数据放哪？答案是：把list_head嵌入到你的数据结构里。

内核链表的核心思想

我刚开始看这段代码时也有点懵：没有数据的链表，那还叫链表吗？其实这才是精髓所在。

传统方式：数据包含指针（数据里带next）
内核方式：指针包含数据（list_head被嵌入到数据里）

举个例子：

struct student {
    int id;
    char name[32];
    struct list_head list;  // 内核链表节点
};

这样，student结构体里就藏了一个链表节点。所有链表操作都针对list成员进行，跟id、name这些数据完全无关。

container_of宏：从成员到结构体

这个宏是内核链表的基石。它的作用：给你一个结构体成员的地址，算出整个结构体的起始地址。

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

原理很简单：成员地址减去成员在结构体中的偏移量，就是结构体起始地址。我在调试一个驱动时，就靠这个宏从链表节点反推出设备结构体，省了不少事。

内核链表的核心操作

内核链表是双向循环链表。初始化时，头节点的prev和next都指向自己：

// 静态初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }

// 动态初始化
static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

插入操作：

// 在头部插入
static inline void list_add(struct list_head *new, struct list_head *head) {
    __list_add(new, head, head->next);
}

// 在尾部插入
static inline void list_add_tail(struct list_head *new, struct list_head *head) {
    __list_add(new, head->prev, head);
}

static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next) {
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

删除操作：

static inline void list_del(struct list_head *entry) {
    entry->prev->next = entry->next;
    entry->next->prev = entry->prev;
}

遍历链表：从list_head到数据

遍历是链表最常用的操作。内核提供了两个宏：

// 遍历所有节点
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

// 遍历并获取结构体指针
#define list_for_each_entry(pos, head, member) \
    for (pos = list_entry((head)->next, typeof(*pos), member); \
         &pos->member != (head); \
         pos = list_entry(pos->member.next, typeof(*pos), member))

list_for_each_entry才是我们真正常用的。它自动帮你从list_head反推出包含它的结构体：

struct student *p;
list_for_each_entry(p, &student_list, list) {
    printf("id: %d, name: %s\n", p->id, p->name);
}

你看，遍历时完全不用关心链表指针怎么走的，直接操作数据就行。

内核链表 vs 传统链表

对比项	传统链表	内核链表
代码复用性	每种数据类型一套代码	一套代码通用所有类型
侵入性	数据必须包含指针	list_head嵌入数据中
类型安全	通常用void*，不安全	通过container_of保证类型安全
操作复杂度	需要自己维护头尾指针	双向循环，操作统一
可扩展性	改数据结构要改链表代码	数据结构与链表操作解耦

内核链表结构图

下面这张图展示了内核链表的核心结构：list_head被嵌入到数据节点中，所有节点通过list_head的prev/next指针串联成双向循环链表。

实际项目中的应用

我在做嵌入式Linux驱动时，经常用内核链表来管理设备对象。比如一个I2C总线上的多个从设备：

struct i2c_device {
    int addr;
    char name[16];
    struct list_head list;  // 链表节点
    // 其他设备相关字段
};

// 创建设备并加入链表
struct i2c_device *dev = kmalloc(sizeof(*dev), GFP_KERNEL);
dev->addr = 0x50;
strcpy(dev->name, "eeprom");
list_add_tail(&dev->list, &device_list);

// 遍历所有设备
struct i2c_device *pos;
list_for_each_entry(pos, &device_list, list) {
    printk("device: %s at 0x%02x\n", pos->name, pos->addr);
}

这种写法最大的好处是：链表操作函数是通用的，你只需要关注数据本身。如果项目里要加一种新的设备类型，直接定义结构体，嵌入list_head，现有的插入、删除、遍历函数全都能用。

避坑指南

用内核链表时，有几个坑我踩过，分享给你：

• 忘记初始化头节点：用LIST_HEAD宏或者INIT_LIST_HEAD函数，别直接用{NULL, NULL}，否则插入时会崩溃。
• 遍历时删除节点：标准list_for_each_entry不支持在遍历中删除，要用list_for_each_entry_safe，它会保存下一个节点的指针。
• container_of的类型匹配：member参数必须是结构体中list_head的字段名，写错了编译不会报错，但运行时会访问到错误的内存地址。
• 多线程并发访问：内核链表本身不是线程安全的，需要加锁保护。我曾在中断上下文和进程上下文同时操作一个链表，结果链表指针乱飞，查了两天才找到原因。

嗯，内核链表的设计思想就这些。它不是什么高深的技术，但确实是一种优雅的工程实践——把变化的部分和不变的部分分离，让代码更简洁、更可维护。下次你写链表时，不妨试试这种思路。