在理论的工作中，咱们可能会常常应用链表构造来存储数据，特地是嵌入式开发，常常会应用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_LISTstatic 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;}#elseextern 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_LISTstatic inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}#elseextern 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_LISTstatic inline void list_del(struct list_head *entry){ __list_del(entry->prev, entry->next); entry->next = LIST_POISON1; entry->prev = LIST_POISON2;}#elseextern 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_LISTstatic 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;}#elseextern 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_LISTstatic inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}#elseextern 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学习材料。