一、侵入式链表

侵入式链表让结构体包含一个成员变量，该成员变量是一个通用的链表结点。普通的单链表的结点链接域存的是下一个结点的内存首地址，而侵入式单链表的结点链接域存的是下一个结点的链接域成员变量的内存首地址。

typedef struct list_s {

        struct list_s *next;

} list_t;

typedef struct foo_s {

        int     data;

        list_t  link;

} foo_t;

下面给出一个最简单的侵入式单链表实现。

1. list.h

 1 #ifndef _LIST_H

 2 #define _LIST_H

 3

 4 #ifdef  __cplusplus

 5 extern “C” {

 6 #endif

 7

 8 /**

 9  * offsetof – offset of a structure member

10  * @TYPE:       the type of the struct.

11  * @MEMBER:     the name of the member within the struct.

12  */

13 #define offsetof(TYPE, MEMBER) ((size_t)(&(((TYPE *)0)->MEMBER)))

14

15 /**

16  * container_of – cast a member of a structure out to the containing structure

17  * @ptr:        the pointer to the member.

18  * @type:       the type of the container struct this is embedded in.

19  * @member:     the name of the member within the struct.

20  *

21  */

22 #define container_of(ptr, type, member) ({                      \

23         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \

24         (type *)( (char *)__mptr – offsetof(type, member) );})

25

26 typedef struct list_s {

27         struct list_s *next;

28 } list_t;

29

30 typedef void (*list_handler_t)(void *arg);

31

32 extern void list_init(list_t **head, list_t *node);

33 extern void list_fini(list_t *head, list_handler_t fini);

34 extern void list_show(list_t *head, list_handler_t show);

35

36 #ifdef  __cplusplus

37 }

38 #endif

39

40 #endif /* _LIST_H */

2. list.c

 1 /*

 2  * Generic single linked list implementation

 3  */

 4 #include

 5 #include “list.h”

 6

 7 void

 8 list_init(list_t **head, list_t *node)

 9 {

10         static list_t *tail = NULL;

11

12         if (*head == NULL) {

13                 *head = tail = node;

14                 return;

15         }

16

17         tail->next = node;

18         tail = node;

19         node->next = NULL;

20 }

21

22 void

23 list_show(list_t *head, list_handler_t show)

24 {

25         for (list_t *p = head; p != NULL; p = p->next)

26                 show(p);

27 }

28

29 void

30 list_fini(list_t *head, list_handler_t fini)

31 {

32         list_t *p = head;

33         while (p != NULL) {

34                 list_t *q = p;

35                 p = p->next;

36                 fini(q);

37         }

38 }

延伸阅读：

二、侵入式的好处

一般来说，大家都会优先选择使用非侵入式的实现。因为侵入式实现需要将一些逻辑耦合到业务代码中，因此为人所不喜。但是在背景介绍中提到的场景下，侵入式实现有显著的好处，从而使得侵入式实现被广泛的使用。我们在此不再强调侵入式与非侵入式的区别，主要考虑一下侵入式链表的优势有哪些。

更好的 Data Locality

std::list 在遍历的过程中还需要对 T* 进行解引用才能访问 T 内部的数据。但是侵入式链表的 next 和 T 内部的数据是放在一起的，因此无需额外的解引用。而且由于内存 layout 就是在一起的，所以也会获得更好的 Data Locality。

更友好的 API

对于侵入式链表，我们拿到数据就可以将这个节点从链表中摘除，而无需再去定位其 iterator，然后再去找到对应的容器 erase 这个 iterator。

脱离容器进行生命周期管理

最主要的应用场景是同一份对象需要在多个容器中共享，例如在背景介绍中提到的实现 LRU 的场景，又例如需要将同一份数据加入多个链表中。因此侵入式链表需要用户自己管理数据节点生命周期的特性在这里就成为了一个优点。

上一篇

常用的数据结构有哪些?

下一篇

堆为什么又会被称为“优先队列”?