03 Linux 内核数据结构

Linux kernel 有四种重要的数据结构：链表、队列、映射、二叉树。普通驱动开发者只需要掌握链表和队列即可。

链表和队列 Linux 内核都有完整的实现，我们不需要深究其实现原理，只需要会使用 API 接口即可。

1、链表

链表是 Linux 内核中最简单、最普通的数据结构。链表是一种存放和操作可变数量元素(常称为节点)的数据结构。链表和静态数组的不同之处在于，它所包含的元素都是动态创建并插入链表的，在编译时不必知道具体需要创建多少个元素。另外也因为链表中每个元素的创建时间名不相同，所以它们在内存中无须占用连续内存区。正是因为元素不连续地存放，所以各元素需要通过某种方式被连接在一起。于是每个元素都包含一个指向下一个元素的指针，当有元素加入链表或从链表中删除元素时，简单调整指向下一个节点的指针就可以了。

使用示例，请查看注释：

#include      // 包含内核初始化和清理函数
#include