共计 24874 个字符，预计需要花费 63 分钟才能阅读完成。
在理论的工作中，咱们可能会常常应用链表构造来存储数据，特地是嵌入式开发，常常会应用 linux 内核最经典的双向链表 list_head。本篇文章具体介绍了 Linux 内核的通用链表是如何实现的，对于常常应用的函数都给出了具体的阐明和测试用例，并且移植了 Linux 内核的链表构造，在任意平台都能够不便的调用内核曾经写好的函数。倡议珍藏，以备不时之需！
@[TOC]
链表简介
链表是一种罕用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现形式。绝对于数组，链表具备更好的动态性，建设链表时无需事后晓得数据总量，能够随机调配空间，能够高效地在链表中的任意地位实时插入或删除数据。
通常链表数据结构至多应蕴含两个域：数据域和指针域，数据域用于存储数据，指针域用于建设与下一个节点的分割。依照指针域的组织以及各个节点之间的分割模式，链表又能够分为单链表、双链表、循环链表等多种类型，上面别离给出这几类常见链表类型的示意图：
单链表
单链表是最简略的一类链表，它的特点是仅有一个指针域指向后继节点（next），因而，对单链表的遍历只能从头至尾（通常是 NULL 空指针）程序进行。
双链表
通过设计前驱和后继两个指针域，双链表能够从两个方向遍历，这是它区别于单链表的中央。如果打乱前驱、后继的依赖关系，就能够形成 ” 二叉树 ”；如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点，就形成了循环链表；如果设计更多的指针域，就能够形成各种简单的树状数据结构。
循环链表
循环链表的特点是尾节点的后继指向首节点。后面曾经给出了双链表的示意图，它的特点是从任意一个节点登程，沿两个方向的任何一个，都能找到链表中的任意一个数据。如果去掉前驱指针，就是单循环链表。
对于链表的更具体的内容能够看这两篇博客
史上最全单链表的增删改查反转等操作汇总以及 5 种排序算法
详解双向链表的基本操作.
Linux 内核中的链表
下面介绍了一般链表的实现形式，能够看到数据域都是包裹在节点指针中的，通过节点指针拜访下一组数据。然而 Linux 内核的链表实现能够说比拟非凡，只有前驱和后继指针，而没有数据域。链表的头文件是在 include/list.h（Linux2.6 内核）下。在理论工作中，也能够将内核中的链表拷贝进去供咱们应用，就需不要造轮子了。
链表的定义
内核链表只有前驱和后继指针，并不蕴含数据域，这个链表具备通用性，应用十分不便。因而能够很容易的将内核链表构造体蕴含在任意数据的构造体中，非常容易扩大。咱们只须要将链表构造体包含在数据结构体中就能够。上面看具体的代码。
内核链表的构造
// 链表构造
struct list_head
{
struct list_head *prev;
struct list_head *next;
}; 当须要用内核的链表构造时，只须要在数据结构体中定义一个 struct list_head{} 类型的构造体成员对象就能够。这样，咱们就能够很不便地应用内核提供给咱们的一组标准接口来对链表进行各种操作。咱们定义一个学生构造体，外面蕴含学号和数学问题。构造体如下：
struct student
{
struct list_head list;// 暂且将链表放在构造体的第一位
int ID;
int math;
};链表的初始化
内核实现
#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 = list;
list->prev = list;
}
阐明
INIT_LIST_HEAD 和 LIST_HEAD 都能够初始化链表，二者的区别如下：
LIST_HEAD（stu_list） 初始化链表时会顺便创立链表对象。
//LIST_HEAD（stu_list）开展如下
struct list_head stu_list= {&(stu_list), &(stu_list) }; INIT_LIST_HEAD(&stu1.stu_list) 初始化链表时须要咱们曾经有了一个链表对象stu1_list。
` 咱们能够看到链表的初始化其实非常简单，就是让链表的前驱和后继都指向了本人。
举例
INIT_LIST_HEAD(&stu1.stu_list);链表减少节点
内核实现
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next);
#endif
/**
* 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.
*/
#ifndef CONFIG_DEBUG_LIST
static inline void list_add(struct list_head *new, struct list_head *head)
{__list_add(new, head, head->next);
}
#else
extern void list_add(struct list_head *new, struct list_head *head);
#endif
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{__list_add(new, head->prev, head);
}阐明
list_add为头插法，即在链表头部（head 节点）前插入节点。最初打印的时候，先插入的先打印，后插入的后打印。例如原链表为 1 ->2->3, 应用 list_add 插入 4 后变为，4->1->2->3。因为链表时循环的，而且通常没有首尾节点的概念，所以能够把任何一个节点当成 head。
同理，list_add_tail为尾插法，即在链表尾部（head 节点）插入节点。最初打印的时候，先插入的后打印，后插入的先打印。例如原链表为 1 ->2->3, 应用 list_add_tail 插入 4 后变为，1->2->3->4。
举例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos;
// 链表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
// 头插法创立 stu stu1 链表
for (int i = 0;i < 6;i++) {p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
// 头插法
list_add(&p->stu_list,&stu1.stu_list);
// 尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("list_add: \r\n");
list_for_each(pos, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);
}
// 尾插法创立 stu stu1 链表
for (int i = 0;i < 6;i++) {p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
// 头插法
//list_add(&p->stu_list,&stu1.stu_list);
// 尾插法
list_add_tail(&p->stu_list,&stu2.stu_list);
}
printf("list_add_tail: \r\n");
list_for_each(pos, &stu2.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);
}
return 0;
}
链表删除节点
内核实现
// 原来内核设置的删除链表后的指向地位
// # define POISON_POINTER_DELTA 0
// #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
// #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
// 这里咱们设置为 NULL 内核中定义 NULL 为 0
#define NULL ((void *)0)
#define LIST_POISON1 NULL
#define LIST_POISON2 NULL
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head *entry);
#endif
阐明
链表删除之后，entry 的前驱和后继会别离指向 LIST_POISON1 和LIST_POISON2，这个是内核设置的一个区域，然而在本例中将其置为了NULL。
举例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
// 留神这里的 pos2，前面会解释为什么定义为
struct student *pos2;
//stu = (struct student*)malloc(sizeof(struct student));
// 链表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
// 头插法创立 stu stu1 链表
for (int i = 0;i < 6;i++) {p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
// 头插法
list_add(&p->stu_list,&stu1.stu_list);
// 尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("list_add: \r\n");
list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
// 删除
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {if (pos2->ID == 4) {list_del(&pos2->stu_list);
break;
}
}
printf("list_del\r\n");
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {printf("ID = %d,math = %d\n",pos2->ID,pos2->math);
}
return 0;
}
链表替换节点
内核实现
/**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
static inline void list_replace_init(struct list_head *old,
struct list_head *new)
{list_replace(old, new);
INIT_LIST_HEAD(old);// 从新初始化
}阐明
list_replace应用新的节点替换旧的节点。
list_replace_init与 list_replace 不同之处在于，list_replace_init会将旧的节点从新初始化，让前驱和后继指向本人。
举例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
struct student *pos2;
struct student new_obj={.ID=100,.math=100};
//stu = (struct student*)malloc(sizeof(struct student));
// 链表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
// 头插法创立 stu stu1 链表
for (int i = 0;i < 6;i++) {p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
// 头插法
list_add(&p->stu_list,&stu1.stu_list);
// 尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("list_add: \r\n");
list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
// 替换
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {if (pos2->ID == 4) {list_replace(&pos2->stu_list,&new_obj.stu_list);
break;
}
}
printf("list_replace\r\n");
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {printf("ID = %d,math = %d\n",pos2->ID,pos2->math);
}
return 0;
}
链表删除并插入节点
内核实现
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{__list_del(list->prev, list->next);
list_add(list, head);
}
/**
* list_move_tail - delete from one list and add as another's tail
* @list: the entry to move
* @head: the head that will follow our entry
*/
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{__list_del(list->prev, list->next);
list_add_tail(list, head);
}阐明
list_move函数实现的性能是删除 list 指向的节点，同时将其以头插法插入到 head 中。list_move_tail和 list_move 性能相似，只不过是将 list 节点插入到了 head 的尾部。
举例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
struct student *pos2;
struct student new_obj={.ID=100,.math=100};
//stu = (struct student*)malloc(sizeof(struct student));
// 链表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
// 头插法创立 stu stu1 链表
for (int i = 0;i < 6;i++) {p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
// 头插法
list_add(&p->stu_list,&stu1.stu_list);
// 尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("list_add: \r\n");
list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
// 移位替换
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {if (pos2->ID == 0) {list_move(&pos2->stu_list,&stu1.stu_list);
break;
}
}
printf("list_move\r\n");
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {printf("ID = %d,math = %d\n",pos2->ID,pos2->math);
}
return 0;
}
链表的合并
内核实现
static inline void __list_splice(struct list_head *list,
struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{if (!list_empty(list))
__list_splice(list, head);
}
/**
* list_splice_init - join two lists and reinitialise the emptied list.
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* The list at @list is reinitialised
*/
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{if (!list_empty(list)) {__list_splice(list, head);
INIT_LIST_HEAD(list);// 置空
}
}阐明
list_splice实现的性能是合并两个链表。假如以后有两个链表，表头别离是 stu_list1 和stu_list2（都是 struct list_head 变量），当调用 list_splice(&stu_list1,&stu_list2) 时，只有 stu_list1 非空，stu_list1链表的内容将被挂接在 stu_list2 链表上，位于 stu_list2 和stu_list2.next（原 stu_list2 表的第一个节点）之间。新 stu_list2 链表将以原 stu_list1 表的第一个节点为首节点，而尾节点不变。
list_splice_init和 list_splice 相似，只不过在合并完之后，调用 INIT_LIST_HEAD(list) 将 list 设置为空链。
用例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
struct student *pos2;
struct student new_obj={.ID=100,.math=100};
//stu = (struct student*)malloc(sizeof(struct student));
// 链表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
// 头插法创立 stu1 list 链表
for (int i = 0;i < 6;i++) {p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
// 头插法
list_add(&p->stu_list,&stu1.stu_list);
// 尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("stu1: \r\n");
list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
// 头插法创立 stu2 list 链表
for (int i = 0;i < 3;i++) {q = (struct student *)malloc(sizeof(struct student));
q->ID=i;
q->math = i+80;
// 头插法
list_add(&q->stu_list,&stu2.stu_list);
// 尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("stu2: \r\n");
list_for_each(pos1, &stu2.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
// 合并
list_splice(&stu1.stu_list,&stu2.stu_list);
printf("list_splice\r\n");
list_for_each(pos1, &stu2.stu_list) {printf("stu2 ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
return 0;
}
链表的遍历
内核实现
// 计算 member 在 type 中的地位
#define offsetof(type, member) (size_t)(&((type*)0)->member)
// 依据 member 的地址获取 type 的起始地址
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
/**
* list_first_entry - get the first element from a list
* @ptr: the list head to take the element from.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*
* Note, that list is expected to be not empty.
*/
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
/**
* __list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*
* This variant differs from list_for_each() in that it's the
* simplest possible list iteration code, no prefetching is done.
* Use this for code that knows the list to be very short (empty
* or 1 entry) most of the time.
*/
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
pos = pos->prev)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_entry_reverse - iterate backwards over list of given type.
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
prefetch(pos->member.prev), &pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
/**
* list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
* @pos: the type * to use as a start point
* @head: the head of the list
* @member: the name of the list_struct within the struct.
*
* Prepares a pos entry for use as a start point in list_for_each_entry_continue().
*/
#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))
/**
* list_for_each_entry_continue - continue iteration over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Continue to iterate over list of given type, continuing after
* the current position.
*/
#define list_for_each_entry_continue(pos, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_entry_from - iterate over list of given type from the current point
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Iterate over list of given type, continuing from current position.
*/
#define list_for_each_entry_from(pos, head, member) \
for (; prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
/**
* list_for_each_entry_safe_continue
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Iterate over list of given type, continuing after current point,
* safe against removal of list entry.
*/
#define list_for_each_entry_safe_continue(pos, n, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
/**
* list_for_each_entry_safe_from
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Iterate over list of given type from current point, safe against
* removal of list entry.
*/
#define list_for_each_entry_safe_from(pos, n, head, member) \
for (n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
/**
* list_for_each_entry_safe_reverse
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Iterate backwards over list of given type, safe against removal
* of list entry.
*/
#define list_for_each_entry_safe_reverse(pos, n, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member), \
n = list_entry(pos->member.prev, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.prev, typeof(*n), member))
阐明
list_entry(ptr, type, member)能够失去节点构造体的地址，失去地址后就能够对构造体中的元素进行操作了。依附 list_entry(ptr, type, member) 函数，内核链表的增删查改都不须要晓得 list_head 构造体所嵌入式的对象，就能够实现各种操作。（为什么这里应用 container_of 来定义 list_entry(ptr, type, member) 构造体呢，上面会具体解释）
list_first_entry(ptr, type, member)失去的是构造体中第一个元素的地址
list_for_each(pos, head) 是用来正向遍历链表的，pos 相当于一个长期的节点，用来一直指向下一个节点。
list_for_each_prev(pos, head)和 list_for_each_entry_reverse(pos, head, member) 是用来倒着遍历链表的
list_for_each_safe(pos, n, head) 和list_for_each_entry_safe(pos, n, head, member)，这两个函数是为了防止在遍历链表的过程中因 pos 节点被开释而造成的断链这个时候就要求咱们另外提供一个与 pos 同类型的指针 n，在 for 循环中暂存 pos 下一个节点的地址。（内核的设计者思考的真是全面！）
list_prepare_entry(pos, head, member)用于筹备一个构造体的首地址，用在 list_for_each_entry_contine() 中
list_for_each_entry_continue(pos, head, member)从以后 pos 的下一个节点开始持续遍历残余的链表，不包含 pos. 如果咱们将 pos、head、member 传入 list_for_each_entry，此宏将会从链表的头节点开始遍历。
list_for_each_entry_continue_reverse(pos, head, member) 从以后的 pos 的前一个节点开始持续反向遍历残余的链表，不包含 pos。
list_for_each_entry_from(pos, head, member)从 pos 开始遍历残余的链表。
list_for_each_entry_safe_continue(pos, n, head, member)从 pos 节点的下一个节点开始遍历残余的链表，并避免因删除链表节点而导致的遍历出错。
list_for_each_entry_safe_from(pos, n, head, member) 从 pos 节点开始持续遍历残余的链表，并避免因删除链表节点而导致的遍历出错。其与 list_for_each_entry_safe_continue(pos, n, head, member) 的不同在于在第一次遍历时，pos 没有指向它的下一个节点，而是从 pos 开始遍历。
list_for_each_entry_safe_reverse(pos, n, head, member)从 pos 的前一个节点开始反向遍历一个链表，并避免因删除链表节点而导致的遍历出错。
list_safe_reset_next(pos, n, member) 返回以后 pos 节点的下一个节点的 type 构造体首地址。
举例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
struct student *pos2;
struct student new_obj={.ID=100,.math=100};
//stu = (struct student*)malloc(sizeof(struct student));
// 链表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
// 头插法创立 stu stu1 链表
for (int i = 0;i < 6;i++) {p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
// 头插法
list_add(&p->stu_list,&stu1.stu_list);
// 尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("stu1: \r\n");
list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
printf("list_for_each_prev\r\n");
list_for_each_prev(pos1, &stu1.stu_list){printf("stu2 ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
return 0;
}
例子就不都写进去了，感兴趣的能够本人试试。
纳闷解答
之前咱们定义构造体的时候是把 struct list_head放在首位的，当应用 list_for_each 遍历的时候，pos 获取的地位就是构造体的地位，也就是链表的地位。如下所示
struct student
{
struct list_head list;// 暂且将链表放在构造体的第一位
int ID;
int math;
}; list_for_each(pos, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);
} 然而当咱们把 struct list_head list; 放在最初时，pos 获取的显然就曾经不是链表的地位了，那么当咱们再次调用 list_for_each 时就会出错。
struct student
{
int ID;
int math;
struct list_head list;// 暂且将链表放在构造体的第一位
}; list_for_each_entry这个函数示意在遍历的时候获取 entry，该宏中的 pos 类型为容器构造类型的指针，这与后面 list_for_each 中的应用的类型不再雷同（这也就是为什么咱们下面会别离定义 pos1 和 pos2 的起因了），不过这也是情理之中的事，毕竟当初的 pos，我要应用该指针去拜访数据域的成员 age 了；head 是你应用 INIT_LIST_HEAD 初始化的那个对象，即头指针，留神，不是头结点；member 就是容器构造中的链表元素对象。应用该宏代替后面的办法。这个时候就要用到 container_of 这个宏了。（再一次感叹内核设计者的平凡）。
对于 container_of 宏将在下一篇文章具体介绍，这里先晓得如何应用就能够。
list.h 移植源码
这里须要留神一点，如果是在 GNU 中应用 GCC 进行程序开发，能够不做更改，间接应用下面的函数即可；但如果你想把其移植到 Windows 环境中进行应用，能够间接将 prefetch 语句删除即可，因为 prefetch 函数它通过对数据手工预取的办法，缩小了读取提早，从而进步了性能，也就是 prefetch 是 GCC 用来提高效率的函数，如果要移植到非 GNU 环境，能够换成相应环境的预取函数或者间接删除也可，它并不影响链表的性能。
/*
* @Description: 移植 Linux2.6 内核 list.h
* @Version: V1.0
* @Autor: https://blog.csdn.net/qq_16933601
* @Date: 2020-09-12 22:54:51
* @LastEditors: Carlos
* @LastEditTime: 2020-09-16 00:35:17
*/
#ifndef _MYLIST_H
#define _MYLIST_H
// 原来链表删除后指向的地位，这里咱们批改成 0
// # define POISON_POINTER_DELTA 0
// #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
// #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
#define NULL ((void *)0)
#define LIST_POISON1 NULL
#define LIST_POISON2 NULL
// 计算 member 在 type 中的地位
#define offsetof(type, member) (size_t)(&((type*)0)->member)
// 依据 member 的地址获取 type 的起始地址
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
// 链表构造
struct list_head
{
struct list_head *prev;
struct list_head *next;
};
#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 = list;
list->prev = list;
}
static inline void init_list_head(struct list_head *list)
{
list->prev = list;
list->next = list;
}
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next);
#endif
// 从头部增加
/**
* 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.
*/
#ifndef CONFIG_DEBUG_LIST
static inline void list_add(struct list_head *new, struct list_head *head)
{__list_add(new, head, head->next);
}
#else
extern void list_add(struct list_head *new, struct list_head *head);
#endif
// 从尾部增加
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{__list_add(new, head->prev, head);
}
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
prev->next = next;
next->prev = prev;
}
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_splice(struct list_head *list,
struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
static inline int list_empty(const struct list_head *head)
{return head->next == head;}
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{if (!list_empty(list))
__list_splice(list, head);
}
/**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
static inline void list_replace_init(struct list_head *old,
struct list_head *new)
{list_replace(old, new);
INIT_LIST_HEAD(old);
}
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{__list_del(list->prev, list->next);
list_add(list, head);
}
/**
* list_move_tail - delete from one list and add as another's tail
* @list: the entry to move
* @head: the head that will follow our entry
*/
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{__list_del(list->prev, list->next);
list_add_tail(list, head);
}
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); \
pos = pos->prev) 养成习惯，先赞后看！如果感觉写的不错，欢送关注，点赞，珍藏，转发，谢谢！
以上代码均为测试后的代码。如有谬误和不妥的中央，欢送指出。
如遇到排版错乱的问题，能够通过以下链接拜访我的 CSDN。
CSDN:CSDN 搜寻“嵌入式与 Linux 那些事”
欢送欢送关注我的公众号：嵌入式与 Linux 那些事，支付秋招口试面试大礼包（华为小米等大厂面经，嵌入式知识点总结，口试题目，简历模版等）和 2000G 学习材料。
正文完
