当前位置：首页 > web >正文

内核链表常用接口的一些理解

web 2025/8/22 7:06:51

1，引入

内核链表是一个双向循环链表，说明他是一个环状的链表，同时只有指针域，数据域根据自我需求来分配。下面会解释为什么是双向循环链表。内核链表的指针域：

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

2，内核链表接口的使用

① 链表的初始化INIT接口：

typedef struct my_stu{struct list_head slist;int id;int age;char name[32];
}MY_STU;// 从初始化的函数可以看出，其初始化时，将prev和next指针都指向的head,
// 所以他是双向循环链表，如果prev = next = NULL，就是双向链表LIST_HEAD(mystu); //内部会定义了 一个lish_head类型的变量--mystu，相当于头节点不带数据域INIT_LIST_HEAD(&MyStu.slist); //这里定义了一个结构体，内部成员有一个slist链表头，头尾指向自己注：INIT_LIST_HEAD 也可以不使用MyStu.slist中的slist，可以重新定义一个list_head 的变量初始化，因为头结点不一定需要带数据域。

② 链表的头插/尾插：

头插法：

_list_add：函数就是一个插入算法，值得注意的是第三个参数，当链表第一次插入时，next结点为头结点，因为初始化时，prev=next=head;

同时 list_add头插法传递的其中一个参数是 head->next

尾插法：

尾插法传递的参数是head->prev，head->prev是指向尾部，所以这个函数不管是首次插入还是后续插入，都插到了末尾。

③ 链表的遍历：

1，list_for_each(p, head):

p --- 为定义的list_head临时指针变量 head ---- 链表头结点

所以其功能就是一个for循环遍历所以链表结点，存储在p变量中，注意：这是个宏定义

2，list_for_each_safe(p, n, head):

p，n --- 都为定义的list_head临时指针变量 head ---- 链表头结点

从中可以看出该宏使用了n变量存储遍历到的当前结点的下一个结点。为什么是安全的？什么时候使用，待下面分析。

上面两个函数都是直接移动链表头结点中的list_head指针域，同时将变量的值赋值到p (pos)，我们可以从这个p（pos）值中解析出数据域：
printf("id = %d, age = %d, name = %s.\n", ((MY_STU*)pos)->id, \((MY_STU*)pos)->age, ((MY_STU*)pos)->name);
注：这样强转，适用于MY_STU结构体中的list_head成员在第一的位置，当list_head不在首位置时，需要使用list_for_each_entry(p , h, field)

       p --- p指针为大结构体指针变量

       h --- 可为头结点指针的lish_head的地址

       field --- 为成员变量名（一般是：list）

最后我们每遍历一次head,都能得到数据域的首地址，即p指针指向的地址。注：要看懂这个需要理解container_of 和 offsetof 的原理。

list_for_each_entry 这个宏通过传入的h(head)和大结构体的类型，找到list成员在大结构体中的偏移量，然后通过container_of 即：list_entry计算出每一个结点的首地址。

④ 链表的删除操作

list_del 或 list_del_init 功能类似，从上面_list_del看，删除操作就是断开当前结点的前一个节点的next指向后一个，后一个的prev指向前一个。list_del_init 的好处是将old节点的前驱和后继断开了。

删除操作我们一般都会在循环中去使用，使用会用到 list_for_each / list_for_each_safe ,如下代码：
// list_for_each 子运行你在循环中删除一个
list_for_each(pos , head) {if(pos->id == 30) {list_del(&pos->list);break;}
}
// list_for_each_safe 由于tmp保存了要删除的节点的下一个,所以删除了这一个，可以继续遍历节点
// 当链表有多个重复数据要删除时，使用这个可一次性删除
list_for_each_safe(pos , tmp, head) {if(pos->id == 30) {list_del(&pos->list);}
}

3，一个完整代码的实现

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>#include "list.h"typedef struct my_stu{int id;int age;char name[32];struct list_head slist;
}MY_STU;LIST_HEAD(mylist); //申请了一个list_head头节点int main()
{int i = 0;MY_STU *node =NULL;struct list_head *pos =NULL;char *str[5]={"111","222","333","444","555"};for(i = 0; i < 5; i++){node = (MY_STU *)malloc(sizeof(MY_STU));if(node) {node->id = i;node->age = i+10;strcpy( node->name, str[i]);list_add( &node->slist, &mylist);}}printf("-----------------list_for_each-------------------------\n");list_for_each(pos, &mylist) {//MY_STU *ps = container_of(pos, MY_STU, slist);MY_STU *ps = list_entry(pos, MY_STU, slist);if(ps){printf("id = %d, age = %d, name = %s.\n", ((MY_STU*)ps)->id, \((MY_STU*)ps)->age, ((MY_STU*)ps)->name); ps = NULL;}else {printf("id = %d, age = %d, name = %s.\n", ((MY_STU*)pos)->id, \((MY_STU*)pos)->age, ((MY_STU*)pos)->name);}}printf("-----------------list_for_each_entry-------------------------\n");list_for_each_entry(node, &mylist, slist) {printf("id = %d, age = %d, name = %s.\n", ((MY_STU*)node)->id, \((MY_STU*)node)->age, ((MY_STU*)node)->name);}printf("-----------------list_for_each_entry_safe-------------------------\n");MY_STU *n =NULL;list_for_each_entry_safe(node, n, &mylist, slist) {if(node->id == 2){list_del(&node->slist);}}list_for_each_entry_safe(node, n, &mylist, slist) {printf("id = %d, age = %d, name = %s.\n", ((MY_STU*)node)->id, \((MY_STU*)node)->age, ((MY_STU*)node)->name);}
}

测试结果：