Linux内核单链表：原理、实现与应用

1. Linux内核开发中的单链表基础

单链表是Linux内核中最基础也最重要的数据结构之一。作为物理存储单元上非连续、非顺序的线性数据结构，它在内核中的使用频率极高。我第一次接触内核链表时，就被它简洁而高效的设计所震撼。

1.1 链表的基本概念

链表由一系列节点组成，每个节点包含两个部分：

• 数据域：存储实际数据
• 指针域：存储指向下一个节点的地址

与数组不同，链表的元素在内存中不是连续存储的，而是通过指针相互连接。这种特性带来了几个显著优势：

1. 动态大小：可以随时增加或删除节点，不需要预先分配固定大小的内存
2. 高效插入/删除：在已知位置插入或删除节点的时间复杂度是O(1)
3. 内存利用率高：不需要连续内存空间，可以充分利用零散内存

在内核中，链表最常见的应用场景包括：

• 进程管理（任务队列）
• 文件系统（inode缓存）
• 设备驱动（设备列表）
• 网络协议栈（数据包队列）

1.2 单链表的结构特点

单链表是最简单的链表形式，每个节点只有一个指向下一个节点的指针。从内核开发的角度看，单链表有几个关键特性需要特别注意：

1. 头指针：指向链表的第一个节点，是访问整个链表的入口
2. 尾节点：最后一个节点的指针域为NULL
3. 空链表：头指针为NULL

在内核中，我们通常这样定义单链表节点：

c复制struct list_node {
    int data;           // 数据域
    struct list_node *next; // 指针域
};

2. 单链表的创建与初始化

2.1 单个节点的创建

创建单个链表节点是链表操作的基础。在内核开发中，我们需要特别注意内存分配和错误处理：

c复制struct node* create_node(int value) {
    // 1. 分配内存
    struct node *new_node = (struct node*)malloc(sizeof(struct node));
    
    // 2. 检查内存是否分配成功
    if (new_node == NULL) {
        printk(KERN_ERR "内存分配失败！\n");
        return NULL;
    }
    
    // 3. 设置节点数据
    new_node->data = value;
    new_node->next = NULL;  // 重要：新节点默认不连接任何节点
    
    return new_node;
}

这里有几个关键点需要注意：

1. 使用malloc动态分配内存，在内核中通常使用kmalloc
2. 必须检查内存分配是否成功
3. 新节点的next指针必须初始化为NULL，避免野指针
4. 在内核开发中，应该使用printk而不是printf

2.2 链表的批量创建

实际开发中，我们经常需要批量创建链表节点。下面是一个创建包含多个节点的链表的实现：

c复制struct node* create_list_node(int *value, int size) {
    struct node *head = NULL;  // 头指针
    struct node *tail = NULL;  // 尾指针

    for(int i = 0; i < size; i++) {
        struct node *new_node = create_node(value[i]);
        if(new_node == NULL) {
            // 创建失败，需要释放已分配的内存
            delete_list_node(head);