概述

一般情况下的链表的节点会如下定义：

struct student {
    char *name;
    struct student*next;
    struct student*prev;
};

这种定义方式的缺点很明显：不同的链表需要构造不同的节点。例如：构造一个“老师的链表”，就需要如下构造节点：

struct teacher {
    char* name;
    struct teacher *next;
    struct teacher *prev;
}

这样的方式显得很笨。有没有更好的方式呢？方法是有的，将链表单独成一个结构体：

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

然后struct student和struct teacher继承struct list_head(在C代码中，“继承”就是定义一个结构体变量)，然后变化出下面两个结构体：

struct student {
    struct list_head list; //定义一个链表，list成员的地址，就是struct student结构体的地址
    char* name;
};

struct teacher {
    struct list_head list; //定义一个链表，list成员的地址，就是struct teacher 结构体的地址
    char* name;
};

以struct student为例分析，如果struct student的list成员的地址知道，则struct student的地址就可以知道。通过list->next可以知道下一个struct student的list成员的地址，知道下一个struct student的list成员的地址，自然就知道下一个struct student的地址。对于prev也是同样的理解。
我们知道，结构体的第一个成员的地址和整个结构体的首地址是一样的。当然，我们也可以通过任意一个结构体成员，获得结构地的首地址，这就需要我们用到container_of和offsetof，因此对于struct student也可以按照下面的定义来继承struct list_head：

struct student {
    char* name;
    struct list_head list; //注意：此时list成员是struct student的第二份个成员
};

API

链表初始化

• INIT_LIST_HEAD：对已定义的链表头节点进行初始化

• LIST_HEAD：定义链表头结点，并进行初始化

  遍历链表

• list_for_each ： 遍历所有的节点

• list_for_each_entry ： 等于list_for_each + list_entry

• list_for_each_entry_safe ： 等于list_for_each + list_entry + 一个额外指针

  插入节点

• list_add ：将新节点插入到链表的最前面

• list_add_head ：和list_add 一样

• list_add_tail：将新节点插入到链表的最后面

  删除节点

• list_del ：将节点从链表中摘除。注意：这个接口不释放malloc申请的空间。

  替换节点

• list_replace ： 替换节点

  其他

• list_empty ：判断链表是否为空的链表

• list_entry : 求得链表节点所在的结构体的首地址
• list_first_entry ：求得下一个链表节点所在的结构体首地址
• list_at_tail ： 判断当前节点是否为链表结尾的节点
• list_at_head ： 判断当前节点是否为链表开头的节点

  示例

  示例1：INIT_LIST_HEAD，list_add，list_for_each

  ```c

  include

  include

include “list.h”

struct person { struct list_head list; int age; };

int main(int argc,char *argv) { int i; struct person p; struct person person1; //定义一个头结点 struct list_head *item;

INIT_LIST_HEAD(&person1.list); //对list成员赋值
for (i = 0;i<5;i++) { //循环
    p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
    p->age=i*10; //给struct person结构体的age成员赋值
    list_add(&p->list,&person1.list); //将新节点的list成员链接到person1.list的链表中。
}
list_for_each(item, &person1.list) {  //遍历person1.list链表，
    printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
}
return 0;

}

$ ./a.out age = 40 age = 30 age = 20 age = 10 age = 0

<a name="p6lO7"></a>
### 示例2：简化示例1
在示例1中，链表的头结点是`struct person person1`的list成员。我们完全可以直接定义一个头结点`struct list_head list;`，不需要将先定义`struct person person1;`再通过`person1`定义头结点。简化后的代码为：
```c
#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    struct list_head list;
    int age;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head list; //定义一个头结点
    struct list_head *item;

    INIT_LIST_HEAD(&list); //对list成员赋值

    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add(&p->list,&list); //将新节点的list成员链接到list的链表中。
    }

    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }

    return 0;
}

$ ./a.out 
age = 40
age = 30
age = 20
age = 10
age = 0

示例3：LIST_HEAD

在示例2中，通过struct list_head list; INIT_LIST_HEAD(&list);两条语句才完成list链表头结点的初始化。我们可以直接通过LIST_HEAD(list)来代替这两个步骤，LIST_HEAD是一个宏，其定义如下：

#define LIST_HEAD(name) \
    struct list_head name = { &(name), &(name) }

因此，将示例2修改，可以得到示例3:

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    struct list_head list;
    int age;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list

    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add(&p->list,&list); //将新节点的list成员链接到list的链表中。
    }

    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }

    return 0;
}

$ ./a.out 
age = 40
age = 30
age = 20
age = 10
age = 0

示例4：list_add_head

list_add_head的作用和list_add一样，在链表的最前面插入一个节点。

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    struct list_head list;
    int age;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list

    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_head(&p->list,&list); //将新节点的list成员链接到list的链表中。
    }

    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }

    return 0;
}

$ ./a.out 
age = 40
age = 30
age = 20
age = 10
age = 0

示例5：list_add_tail

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    struct list_head list;
    int age;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list

    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list,&list); //将新节点的list成员链接到list的链表中。
    }

    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }

    return 0;
}

$ ./a.out 
age = 0
age = 10
age = 20
age = 30
age = 40

示例6：list_empty

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    struct list_head list;
    int age;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list
    printf("this list %s empty\n",list_empty(&list) ? "is":"isn't");
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list,&list); //将新节点的list成员链接到list的链表中。
    }
    printf("this list %s empty\n",list_empty(&list) ? "is":"isn't");
    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }

    return 0;
}


$ ./a.out 
this list is empty
this list isn't empty
age = 0
age = 10
age = 20
age = 30
age = 40

示例7：list_del

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    struct list_head list;
    int age;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list,&list); //将新节点的list成员链接到list的链表中。
    }
    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }
    printf("********\n");
    list_for_each(item, &list) {
        if(((struct person *)item)->age == 20) {
            list_del(item);
            free((struct person *)item);
            break; //一定要break，跳出list_for_each，否则list_for_each会一直遍历list链表
        } 
    }

    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }

    return 0;
}


$ ./a.out 
age = 0
age = 10
age = 20
age = 30
age = 40
********
age = 0
age = 10
age = 30
age = 40

示例8：list_replace

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    struct list_head list;
    int age;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list,&list); //将新节点的list成员链接到list的链表中。
    }
    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }
    printf("********\n");
    struct person *jahol = (struct person *)malloc(sizeof(struct person ));
    jahol->age = 1000;
    list_for_each(item, &list) {
        if(((struct person *)item)->age == 20) {
            list_replace(item,&jahol->list);
            break;
        }
    }

    list_for_each(item, &list) {  //遍历list链表，
        printf("age = %d\n",((struct person *)item)->age);  //地址强制转换,获得struct person中的age成员的值
    }

    return 0;
}


$ ./a.out 
age = 0
age = 10
age = 20
age = 30
age = 40
********
age = 0
age = 10
age = 1000
age = 30
age = 40

示例9：list_entry

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    int age;
    struct list_head list_node;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list_node,&list); //将新节点的list成员链接到list的链表中。
    }

    list_for_each(item, &list) {  //遍历list链表
        struct person *pt = list_entry(item,struct person,list_node); //通过list_entry，获得struct person首地址
        printf("age = %d\n",pt->age);
    }

    return 0;
}

$ ./a.out 
age = 0
age = 10
age = 20
age = 30
age = 40

示例10：list_first_entry

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    int age;
    struct list_head list_node;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list_node,&list); //将新节点的list成员链接到list的链表中。
    }

    list_for_each(item, &list) {  //遍历list链表
        struct person *current = list_entry(item,struct person,list_node); //通过list_entry，获得struct person首地址
        struct person *next = list_first_entry(item,struct person,list_node); 
        printf("currnt age = %d, next age = %d\n",current->age,next->age);
    }

    return 0;
}

$ ./a.out 
currnt age = 0, next age = 10
currnt age = 10, next age = 20
currnt age = 20, next age = 30
currnt age = 30, next age = 40
currnt age = 40, next age = 556266208  //说明：链表头结点没有age成员，所以“next age”是随机

示例11：list_at_tail

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    int age;
    struct list_head list_node;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list_node,&list); //将新节点的list成员链接到list的链表中。
    }

    list_for_each(item, &list) {  //遍历list链表
        struct person *pt = list_entry(item,struct person,list_node); //通过list_entry，获得struct person首地址
        printf("age = %d,now %s at tail\n",pt->age, list_at_tail(pt,&list,list_node) ?"is":"isn't");
    }

    return 0;
}

$ ./a.out 
age = 0,now isn't at tail
age = 10,now isn't at tail
age = 20,now isn't at tail
age = 30,now isn't at tail
age = 40,now is at tail

示例12：list_at_head

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    int age;
    struct list_head list_node;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct list_head *item;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list_node,&list); //将新节点的list成员链接到list的链表中。
    }

    list_for_each(item, &list) {  //遍历list链表
        struct person *pt = list_entry(item,struct person,list_node); //通过list_entry，获得struct person首地址
        printf("age = %d,now %s at head\n",pt->age, list_at_head(pt,&list,list_node) ?"is":"isn't");
    }

    return 0;
}

$ ./a.out 
age = 0,now is at head
age = 10,now isn't at head
age = 20,now isn't at head
age = 30,now isn't at head
age = 40,now isn't at head

示例13：list_for_each_entry

list_for_each_entry = list_for_each + list_entry

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    int age;
    struct list_head list_node;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list_node,&list); //将新节点的list成员链接到list的链表中。
    }
    p = NULL;
    list_for_each_entry(p,&list,list_node) {  //遍历list链表
        printf("*** %d\n",p->age);
    }

    return 0;
}

示例14：list_for_each_entry_safe

list_for_each_entry_safe = list_for_each + list_entry + 一个额外指针

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    int age;
    struct list_head list_node;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct person *_n;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list_node,&list); //将新节点的list成员链接到list的链表中。
    }
    p = NULL;
    list_for_each_entry_safe(p,_n,&list,list_node) {  //遍历list链表
        printf("*** %d\n",p->age);
    }

    return 0;
}

示例15：list_for_each_entry_safe与list_del

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct person
{
    int age;
    struct list_head list_node;
};

int main(int argc,char **argv)
{
    int i;
    struct person *p;
    struct person *_n;

    LIST_HEAD(list); //定义并初始化链表头结点list
    for (i = 0;i<5;i++) { //循环
        p = (struct person *)malloc(sizeof(struct person )); //每次构造一个struct person结构体
        p->age=i*10; //给struct person结构体的age成员赋值
        list_add_tail(&p->list_node,&list); //将新节点的list成员链接到list的链表中。
    }
    p = NULL;
    list_for_each_entry_safe(p,_n,&list,list_node) {  //遍历list链表
        printf("*** %d\n",p->age);
    }
    printf("********\n");
    list_for_each_entry_safe(p,_n,&list,list_node) {
        if(p->age == 20) {
            list_del(&p->list_node);
            free(p);
            //break; //用了list_for_each_entry_safe，就可以屏蔽掉break
        } 
    }

    list_for_each_entry_safe(p,_n,&list,list_node) {  //遍历list链表，
        printf("age = %d\n",p->age);  //地址强制转换,获得struct person中的age成员的值
    }

    return 0;
}

简便list.h

/*
 * list.h List Utilities
 *
 *    This library is free software; you can redistribute it and/or
 *    modify it under the terms of the GNU Lesser General Public
 *    License as published by the Free Software Foundation version 2.1
 *    of the License.
 *
 * Copyright (c) 2003-2006 Thomas Graf <tgraf@suug.ch>
 */

#ifndef __LIST_H
#define __LIST_H
#define offsetof(TYPE, MEMBER)    ((unsigned long)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({            \
    const typeof(((type *)0)->member) * __mptr = (ptr);    \
    (type *)(((unsigned long)__mptr - offsetof(type, member))); })

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

static inline void __list_add(struct list_head *obj,
                struct list_head *prev,
                struct list_head *next)
{
    prev->next = obj;
    obj->prev = prev;
    next->prev = obj;
    obj->next = next;
}


/**
 * 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)
{
    __list_add(new, head, head->next);
}


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

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

static inline void list_del(struct list_head *obj)
{
    obj->prev->next = obj->next;
    obj->next->prev = obj->prev;
    obj->next = obj->prev = obj;
}

static inline void list_replace(struct list_head *old,
                struct list_head *obj)
{
    obj->next = old->next;
    obj->next->prev = obj;
    obj->prev = old->prev;
    obj->prev->next = obj;
}

static inline int list_empty(struct list_head *head)
{
    return head->next == head;
}

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

#define list_first_entry(ptr, type, member) \
    container_of((ptr)->next, type, member)

#define list_at_tail(pos, head, member) \
    ((pos)->member.next == (head))

#define list_at_head(pos, head, member) \
    ((pos)->member.prev == (head))

#define LIST_HEAD(name) \
    struct list_head name = { &(name), &(name) }

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

/**
 * 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; pos != (head); pos = pos->next)

#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))

#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))
#endif /* __LIST_H */