【Linux内核数据结构】最为经典的链表list的学习

数据结构】最为经典的链表list的学习"/>

【Linux内核数据结构】最为经典的链表list的学习

一.前言：

最近因为工作原因，在拜读内核数据结构，学习内核经典的数据结构；不过因为数据结构不好的原因被鄙视(链表，二年级的学生都会的东西)；所以从现在重新补习曾经没有掌握好的知识。这个链表经典的地方是，没有数据域，不是把数据内嵌到链表中，而是把链表链表内嵌到数据对象中，数据结构大概如下所示：

二.总体数据结构

                                                                  (图1总体数据结构)

list_head的数据结构如下所示：

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

三. 创建链表

提供了三种方法来初始化链表，请注意，这里是有链表头的大概是下图这样的结构，

有一个头部，后边都是list。

#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \struct list_head name = LIST_HEAD_INIT(name)static inline void INIT_LIST_HEAD(struct list_head *list)
{list->next = listlist->prev = list;
}

链表的head 的next 跟prev 都是指向自己，这个比较好理解；再此强调一点，这里的链表没有指定具体的数据域，只有指针域；一般的使用方式都是创建一个宿主结构，在此结构中嵌套此list，而且，此宿主结构又有其他的字段；代码使用的例子是：

typedef struct list_st
{int type;char name[MAX];struct list_head head;} list_t;list_t list;
INIT_LIST_HEAD(&list.head)

 四.添加节点 

在prev和next 直接插入一个new 节点

/** Insert a new entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/
static inline void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next)
{if (!__list_add_valid(new, prev, next))return;next->prev = new;new->next = next;new->prev = prev;prev->next = new;
}

如下图所示在Prev 跟Next 之间插入New这个节点

 五.头插法添加节点

static inline void list_add(struct list_head *new, struct list_head *head)
{__list_add(new, head, head->next);
}

很明显，Head 就上面__list_add中的prev节点，Head->next 就是上面__list_add的next节点，

这个比较好理解；

 六.尾插法添加节点

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{__list_add(new, head->prev, head);
}

很明显，Head 就是上面__list_add中的next节点，Head->prev 就是上面__list_add的prev节点，

这个比较好理解；

 七.删除节点

static inline void __list_del(struct list_head * prev, struct list_head * next)
{next->prev = prev;WRITE_ONCE(prev->next, next);
}static inline void __list_del_entry(struct list_head *entry)
{if (!__list_del_entry_valid(entry))return;__list_del(entry->prev, entry->next);
}

 从上面的图像中可以看到，删除时的Prev就是Entry->prev,Next就是Entry->next