三.链表的基本操作（插入，删除，判空）
1.判断链表是否为空
1>function:
函数判读链表是否为空链表，如果为空链表返回1，否则返回0.
2>函数接口
static inline int list_empty(const struct list_head *head)
static inline int list_empty_careful(const struct list_head *head)
3>以下两个函数都是判断一个链表是不是为空链表,
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
static inline int list_empty_careful(const struct list_head *head)
{
struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}
list_empty()函数和list_empty_careful()函数都是用来检测链表是否为空的。但是稍有区别的就是第一个链表使用的检测方法是判断表头的结点的下一个结点是否为其本身，如果是则返回为1，否则返回0。第二个函数使用的检测方法是判断表头的前一个结点和后一个结点是否为其本身，如果同时满足则返回0，否则返回值为1。
这主要是为了应付另一个cpu正在处理同一个链表而造成next、prev不一致的情况。但代码注释也承认，这一安全保障能力有限：除非其他cpu的链表操作只有list_del_init()，否则仍然不能保证安全，也就是说，还是需要加锁保护。
2.链表的插入
1>function:
将一个新结点插入到链表中（在表头插入和表尾插入）
2>Linux内核链表提供了两个函数：
static inline void list_add(struct list_head *new, struct list_head *head)
static inline void list_add_tail(struct list_head *new, struct list_head *head)
3>函数实现
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_tail(new, head->prev, head);
}
4＞list_add和list_add_tail的区别并不大，都是调用了__list_add()函数
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;
}
__list_add(new,prev,next)函数表示在prev和next之间添加一个新的节点new
5>对于list_add()函数中的__list_add(new, head, head->next)表示的在head和head->next之间加入一个新的节点。即表头插入法（即先插入的后输出，可以用来实现一个栈）
6>对于list_add_tail()中的__list_add(new, head->prev, head)表示在head->prev（双向循环链表的最后一个结点）和head之间添加一个新的结点。即表尾插入法（先插入的先输出，可以用来实现一个队列）
3.链表的删除
1>function:
将一个结点从链表中删除
2>函数接口
static inline void list_del(struct list_head *entry)
static inline void list_del_init(struct list_head *entry)
注：在3.0内核中新添加了
static inline void __list_del_entry(struct list_head *entry)
3>函数实现
static inline void __list_del(struct list_head * prev, struct list_head* next)
{
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
static inline void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
static inline void __list_del_entry(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
（1）__list_del(entry->prev, entry->next)表示将entry的前一个和后一个之间建立关联。
（2）list_del()函数将删除后的prev、next指针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值，这样设置是为了保证不在链表中的节点项不可访问。对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。
注意：
这里的entry结点所占用的内存并没有被释放。
LIST_POSTION1和LIST_POSTION1在linux/poison.h中定义
#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
POISON_POINTER_ELTA在linux/poison.h中定义
#ifdef CONFIG_ILLEGAL_POINTER_VALUE
#define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
#else
#define POISON_POINTER_DELTA 0
#endif
其中POISON_POINTER_DELTA的值在CONFIG_ILLEGAL_POINTER_VALUE中未配置时为0
（3）list_del_init这个函数首先将entry从双向链表中删除之后，并且将entry初始化为一个空链表。
说明：list_del(entry)和list_del_init(entry)唯一不同的是对entry的处理，前者是将entry设置为不可用，后者是将其设置为一个空的链表的开始。
（4）__list_del_entry()函数实现只是简单的对__list_del进行了简单的封装实现了只用传入一个entry结点即可将其从链表中删除；与list_del的不同点是只是简单的删除结点，但并没有使entry结点不可用。
注意：在3.0内核中listd_move,和list_move_tail函数内部改成调用__list_del_entry。2.6内核中调用的是__list_del函数。