Linux 数据结构之链表

Linux 内核代码中实现的链表是双向循环链表涉及代码 include/linux/types.h （定义了 list_head 这个数据结构） include/linux/list.h（所有链表的操作）

Linux 中链表的使用

插入操作

看一个基本的插入流程伪代码

typedef struct node{
  int val;
  int key;
  struct list_head* list;
}node;

//初始化头指针
LIST_HEAD(head);

//创建节点
node* a = malloc(sizeof(node));
node* b = malloc(sizeof(node));

//插入链表 方式一 注意传的参数
list_add(&a->list,&head);
list_add(&b->list,&head);

//插入链表 方式二
list_add_tail(&a->list,&head);
list_add_tail(&b->list,&head);

//遍历链表
node *c;
list_for_each_entry(c, &head, list)；

//删除节点
list_del(&a->list);

list_head 结构体定义，注意结构体变量，应该是指针，不能是 struct next结构体变量,不然就无限嵌套了哦。这里想个问题，Struct list_head 的大小是多大？

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

LIST_HEAD 宏定义，前后指针都指向自己。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

这边只分析一下 list_add 的原理，关于 list_add_tail 只是前后指针插入的顺序不同而已。这里传入的参数分别是&a->list，&head，即分别把结构体 a 的 list 指针地址赋值给指针变量 new,头结点 head 的地址赋值给指针变量 head

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
/*此时 new 为要插入的新节点的 list_head 变量，head 为头结点的首地址，head->next 即 head 的成员变量 next*/
	__list_add(new, head, head->next);
}

实际调用 __list_add，这里的 WRITE_ONCE 只是为了不让编译器优化的，可以直接理解成 prev->next = new。

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;
    /*head->next->prev = new,第一次插入的话，由于指向的是自己，所以即头结点的prev指针，赋值操作代表 prev 指针指向 new*/
	next->prev = new;
    /*list->next = head->next,即将 list 结构体的结构体变量 next 指针指向头节点的 next 指针指向的地址*/
	new->next = next;
    /*list->prev = head,即将要插入的新节点的 prev 指针指向 head 头节点*/
	new->prev = prev;
    /*理解成 prev->next = new*/
    /*head->next = list*/
	WRITE_ONCE(prev->next, new);
}

list_add 接口，先入后出原则，有点类似于栈，注意，中间的指针next 指向的并不是下一节点的 next 的指针地址，而是 list_head 的首地址，每次添加时，最外的两指针位置不会发生变化

list_add

list_add_tail 接口，先入先出原则，有点类似于fifo

list_add_tail

小结

内核中所以链表相关的操作都封装在了 include/linux/list.h 中，在使用时也非常简单，在需要的结构体中插入 struct list_head* list;在通过 LIST_HEAD(head);就完成了双向循环链表的初始化了，之后就可以调用 list.h 中定义的函数对链表进行不同的操作。

ctwillson

Linux 数据结构之链表