链表简介
链表是一种常见的数据结构，它通过指针将一系列数据节点连接成一条数据链。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。
传统链表与Linux内核链表的区别
Linux内核链表是双向循环链表，提供一套统一的链表和操作函数。内核链表的节点由数据和指针两部分组成，不同的是指针不指向下一个节点的数据部分，而是指向下一个节点的指针部分。
内核链表的结构
struct list_head{
struct list_head *next, *prev;
};
list_head结构包含两个指向list_head结构的指针prev和next，由此可见，内核的链表具备双向链表功能，实际上通常它都组织成双向循环链表。
内核链表的函数
头文件<linux/list.h>
INIT_LIST_HEAD:创建链表
list_add:在链表头插入节点
list_ad_tail:在链表尾插入节点
list_del:删除节点
list_entry:取出节点
list_for_each:遍历链表
list_entry(ptr, type, member)
ptr:链表结点指针
type:链表结点
member:链表结点的指针名
实现方法是通过链表结点(type)减去链表结点的指针名(member)算出结点头部距离结点指针的偏移，然后让链表结点指针(ptr)指针指向链表结点头部。
list.c
#include <linux/init.h> #include <linux/module.h> #include <linux/list.h> //类型定义 typedef struct student{ int numb; //学生学号 int engl; //英语成绩 int math; //数学成绩 struct list_head node; //链表结点 }STUDENT; //加载函数 static int list_init(){ //创建链表 struct list_head student_head; INIT_LIST_HEAD(&student_head); //添加结点 STUDENT stu1, stu2, stu3; stu1.numb = 1; stu1.engl = 90; stu1.math = 90; list_add_tail(&(stu1.node), &student_head); stu2.numb = 2; stu2.engl = 80; stu2.math = 80; list_add_tail(&(stu2.node), &student_head); stu3.numb = 3; stu3.engl = 70; stu3.math = 70; list_add_tail(&(stu3.node), &student_head); //遍历结点 struct list_head *pos; STUDENT *temp; list_for_each(pos, &student_head){ temp = list_entry(pos, STUDENT, node); printk("No.%d, English is %d, Math is %d ", temp->numb, temp->engl, temp->math); } //删除结点 list_del(&(stu1.node)); list_del(&(stu2.node)); list_del(&(stu3.node)); return 0; } //卸载函数 static void list_exit(){ } //模块信息声明 MODULE_LICENSE("GPL"); MODULE_AUTHOR("D"); MODULE_DESCRIPTION("list"); MODULE_VERSION("v1.0"); //模块函数声明 module_init(list_init); module_exit(list_exit);
Makefile
obj-m := list.o KDIR := /space/work/guoqian/liunxkernel/000/kernel/linux-mini2440 all : make -C $(KDIR) M=$(PWD) modules ARCH=arm CROSS_COMPILE=arm-linux- clean : @rm -f *.o *.ko *.mod.* *.order *.symvers
内核链表代码不涉及到任何内核调用，可以直接移植到应用程序中使用。