本文共 5180 字，大约阅读时间需要 17 分钟。
1. 位置
linux原码里的list.h
2. 数据结构
| struct list_head { struct list_head *next, *prev; }; |
3. 使用方法
1. 应用时，在链表的头节点及中间节点的数据结构中包含struct list_head成员；
2. 头节点的struct list_head成员应初始化（将next、prev指针都指向自己，next指向自己时表明链表为空）；
3. 建议将中间节点的struct list_head成员next、prev初始化为NULL；
4. 在并行执行环境下使用时，需考虑对链表进行加锁保护；
5. 插入、删除、遍历等操作见下面的接口。
4. 接口
4.1. LIST_HEAD
· 原型 LIST_HEAD(name)
· 功能 定义链表头节点变量，并初始化
· 参数 name：头节点变量名
4.2. INIT_LIST_HEAD
· 原型 INIT_LIST_HEAD(ptr)
· 功能 初始化链表头节点
· 参数 ptr：头节点指针
4.3. list_add
· 原型 void list_add(struct list_head *new, struct list_head *head)
· 功能 将节点加入到链表的头部
· 参数 new：节点 head：头节点
4.4. list_add_tail
· 原型 void list_add_tail(struct list_head *new, struct list_head *head)
· 功能 将节点加入到链表的尾部
· 参数 new：节点 head：头节点
4.5. list_del
· 原型 void list_del(struct list_head *entry)
· 功能 从链表中删除节点，并将节点的next及prv置NULL。
· 参数 entry：待删除节点
4.6. list_del_init
· 原型 void list_del_init(struct list_head *entry)
· 功能 删除节点，并将节点初始化（INIT_LIST_HEAD）
· 参数 entry：待删除节点
4.7. list_empty
· 原型 int list_empty(struct list_head *head)
· 功能 判断链表是否为空
· 参数 head：头节点
· 说明 头节点的next指向自己时表明链表为空
4.8. list_is_last
· 原型 int list_is_last(const struct list_head *list, const struct list_head *head)
· 功能 判断节点是否链表的最后一个成员
· 参数 list：节点 head：头节点
· 说明 list != head时有效，或者说仅当list为链表成员时有效。
4.9. list_entry
· 原型 list_entry(ptr, type, member)
· 功能 获取包含该节点成员的数据结构的指针
· 参数 ptr：struct list_head成员的指针 type：struct list_head所在数据结构的类型 member：struct list_head的成员名
4.10. list_first_entry
· 原型 list_first_entry(ptr, type, member)
· 功能 获取链表的第一个节点
· 参数 ptr：头节点指针 type：struct list_head所在数据结构的类型 member：struct list_head的成员名
· 返回 链表第一个节点（struct list_head所在数据结构）的指针
· 说明 仅针对链表非空时可用。
4.11. list_next_entry
· 原型 list_next_entry(pos, head, member)
· 功能 获取链表的下一个节点
· 参数 pos：struct list_head所在数据结构的指针 head：链表的头节点指针 member：struct list_head的成员名
· 返回 如果是最后一个节点返回NULL，否则返回下一个节点（struct list_head所在数据结构的指针）
4.12. list_for_each
· 原型 list_for_each(pos, head)
· 功能 遍历链表所有节点
· 参数 pos：struct list_head成员的指针 head：链表的头节点指针
· 说明 需根据pos调用list_entry转换为struct list_head所在数据结构的指针后再使用； 遍历完后，pos指向的是链表的头节点。
4.13. list_for_each_prev
· 原型 list_for_each_prev(pos, head)
· 功能 遍历链表所有节点（从链表最后一个节点开始）
· 参数 pos：struct list_head成员的指针 head：链表的头节点指针
· 说明 需根据pos调用list_entry转换为struct list_head所在数据结构的指针后再使用； 遍历完后，pos指向的是链表的头节点。
4.14. list_for_each_safe
· 原型 list_for_each_safe(pos, n, head)
· 功能 遍历链表所有节点，允许有节点删除的操作
· 参数 pos：struct list_head成员的指针 n：临时变量，struct list_head的指针 head：链表的头节点指针
· 说明 需根据pos调用list_entry转换为struct list_head所在数据结构的指针后再使用； 遍历完后，pos指向的是链表的头节点。
4.15. list_for_each_entry
· 原型 list_for_each_entry(pos, head, member)
· 功能 遍历链表所有节点
· 参数 pos：struct list_head所在数据结构的指针 head：链表的头节点指针 member：struct list_head的成员名
· 说明 遍历完后，pos指向是无效的。
4.16. list_for_each_entry_safe
· 原型 list_for_each_entry_safe(pos, n, head, member)
· 功能 遍历链表所有节点，允许有节点删除的操作
· 参数 pos：struct list_head所在数据结构的指针 n：临时变量，struct list_head所在数据结构的指针 head：链表的头节点指针 member：struct list_head的成员名
· 说明 遍历完后，pos指向是无效的。
4.17. list_for_each_entry_continue
· 原型 list_for_each_entry_continue(pos, head, member)
· 功能 从指定的节点开始向后遍历链表
· 参数 pos：struct list_head所在数据结构的指针 head：链表的头节点指针 member：struct list_head的成员名
· 说明 遍历完后，pos指向是无效的。
4.18. list_replace
· 原型 void list_replace(struct list_head *old, struct list_head *new)
· 功能 替换节点
· 参数 old：原节点 new：新节点
4.19. list_replace_init
· 原型 void list_replace_init(struct list_head *old, struct list_head *new)
· 功能 替换节点，并将原节点初始化（INIT_LIST_HEAD）
· 参数 old：原节点 new：新节点
4.20. list_move
· 原型 void list_move(struct list_head *list, struct list_head *head)
· 功能 删除节点，并将其加入到另一链表的头部
· 参数 list：待删除节点 head：头节点
4.21. list_move_tail
· 原型 void list_move_tail(struct list_head *list, struct list_head *head)
· 功能 删除节点，并将其加入到另一链表的尾部
· 参数 list：待删除节点 head：头节点
4.22. list_break
· 原型 void list_break(struct list_head *list, struct list_head *entry)
· 功能 将链表截断为两个链表
· 参数 list：原链表头结点 entry：截断点，该节点成为新链表的头节点
4.23. list_splice
· 原型 void list_splice(struct list_head *list, struct list_head *head)
· 功能 合并两个链表
· 参数 list：待合并的链表的头节点 head：头节点
· 说明 list非空时，将其成员加入到head的头部。随后，list为非初始化状态。
4.24. list_splice_init
· 原型 void list_splice_init(struct list_head *list, struct list_head *head)
· 功能 合并两个链表，并初始化空链表的头节点
· 参数 list：待合并的链表的头节点 head：头节点
· 说明 list非空时，将其成员加入到head的头部。随后对list进行初始化。
5. 示例
Example
#include/* 定义头节点 */struct list_head exa_head;/* 定义链表节点 */struct exa_node{ u32 num; struct list_head node;}; void list_example(){ struct exa_node *e; struct exa_node *temp; int found = 0; /* 初始化头节点 */ INIT_LIST_HEAD(&exa_head); /* 创建链表节点并初始化 */ e = (struct exa_node *)malloc(sizeof(struct exa_node)); memset(e, 0, sizeof(struct exa_node)); e->num = 100; /* 加入到链表头 */ list_add(&e->node, &exa_head); /* 遍历、查找链表 */ list_for_each_entry(temp, &exa_head, node) { if (temp->num == e->num) { found = 1; break; } } if (found) { printf("found entry %d\r\n", temp->num); /* 获取下一个节点 */ temp = list_next_entry(temp, &exa_head, node); if (temp != NULL) printf("next entry %d\r\n", temp->num); } /* 获取链表的第一个节点 */ if (!list_empty(&exa_head)) { /* 必须先判断链表非空 */ temp = list_first_entry(&exa_head, struct exa_node, node); } /* 从链表中删除 */ list_del(&e->node); /* 释放链表节点 */ free(e);}
转载地址：http://nfqci.baihongyu.com/