文章目錄

• • LIST 示意圖
  • 接口和實現
  • 舉例
  • 代碼分析
  • • LIST_ENTRY 和 LIST_HEAD
    • LIST_INIT 和 LIST_INSERT_HEAD
    • LIST_INSERT_AFTER
    • LIST_INSERT_BEFORE
    • LIST_FOREACH
    • LIST_REMOVE
    • LIST_FIRST 和 LIST_NEXT
  • 參考資料

上一篇博文 鏈表之SLIST_車子（chezi）-CSDN博客 說過，queue.h 里面有 5 種鏈表，分別是：

SLIST

LIST

STAILQ

TAILQ

CIRCLEQ

這篇文章說 LIST

LIST 示意圖

LIST 是雙向無尾非循環鏈表。雙向鏈表有前向的指針，因此可以執行一些前向操作。

仔細看圖你會發現，le_next 這個指針指向后面的大結構體，這個不稀奇；稀奇的是，le_prev 這個指針，它指的不是前面的大結構體，而是前面的 le_next。為什么這樣設計呢？賣個關子，答案在我以后的文章中。

接口和實現

注意：不同的版本，代碼可能有差異。

/** List declarations.*/ #define LIST_HEAD(name, type) \ struct name { \struct type *lh_first; /* first element */ \ }#define LIST_HEAD_INITIALIZER(head) \{ NULL }#define LIST_ENTRY(type) \ struct { \struct type *le_next; /* next element */ \struct type **le_prev; /* address of previous next element */ \ }/** List functions.*/#define LIST_EMPTY(head) ((head)->lh_first == NULL)#define LIST_FIRST(head) ((head)->lh_first)#define LIST_FOREACH(var, head, field) \for ((var) = LIST_FIRST((head)); \(var); \(var) = LIST_NEXT((var), field))#define LIST_INIT(head) do { \LIST_FIRST((head)) = NULL; \ } while (0)#define LIST_INSERT_AFTER(listelm, elm, field) do { \if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\LIST_NEXT((listelm), field)->field.le_prev = \&LIST_NEXT((elm), field); \LIST_NEXT((listelm), field) = (elm); \(elm)->field.le_prev = &LIST_NEXT((listelm), field); \ } while (0)#define LIST_INSERT_BEFORE(listelm, elm, field) do { \(elm)->field.le_prev = (listelm)->field.le_prev; \LIST_NEXT((elm), field) = (listelm); \*(listelm)->field.le_prev = (elm); \(listelm)->field.le_prev = &LIST_NEXT((elm), field); \ } while (0)#define LIST_INSERT_HEAD(head, elm, field) do { \if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\LIST_FIRST((head)) = (elm); \(elm)->field.le_prev = &LIST_FIRST((head)); \ } while (0)#define LIST_NEXT(elm, field) ((elm)->field.le_next)#define LIST_REMOVE(elm, field) do { \if (LIST_NEXT((elm), field) != NULL) \LIST_NEXT((elm), field)->field.le_prev = \(elm)->field.le_prev; \*(elm)->field.le_prev = LIST_NEXT((elm), field); \ } while (0)

舉例

我們舉例說明，代碼來自 https://manpages.courier-mta.org/htmlman3/list.3.html，我稍微改了一下。

#include <stddef.h> #include <stdio.h> #include <stdlib.h> #include <sys/queue.h>struct entry {int data;LIST_ENTRY(entry) entries; /* List */ };LIST_HEAD(listhead, entry);int main(void) {struct entry *n1, *n2, *n3, *np;struct listhead head; /* List head */int i;LIST_INIT(&head); /* Initialize the list */n1 = malloc(sizeof(struct entry)); /* Insert at the head */n1->data = 1; //我加的LIST_INSERT_HEAD(&head, n1, entries);n2 = malloc(sizeof(struct entry)); /* Insert after */n2->data = 2; //我加的LIST_INSERT_AFTER(n1, n2, entries);n3 = malloc(sizeof(struct entry)); /* Insert before */n3->data = 3; //我加的LIST_INSERT_BEFORE(n2, n3, entries);/* Forward traversal */LIST_FOREACH(np, &head, entries)printf("%i\n", np->data);LIST_REMOVE(n2, entries); /* Deletion */free(n2);/* Forward traversal */LIST_FOREACH(np, &head, entries)printf("%i\n", np->data);/* List deletion */n1 = LIST_FIRST(&head);while (n1 != NULL) {n2 = LIST_NEXT(n1, entries);free(n1);n1 = n2;}LIST_INIT(&head);exit(EXIT_SUCCESS); }

代碼分析

代碼呢，就是這么個代碼。咱們一點一點看。

LIST_ENTRY 和 LIST_HEAD

struct entry {int data;LIST_ENTRY(entry) entries; /* List */ };LIST_HEAD(listhead, entry);

宏展開就是：

struct entry {int data;struct { // 沒有標簽的結構體struct entry *le_next; struct entry **le_prev; } entries; }; struct listhead { struct entry *lh_first; };

和 slist 很相似，唯一的區別是 entries 里面有 2 個指針，因為是雙向，當然有 2 個指針了。注意，le_prev 的類型是指向指針的指針，即二級指針，這是為什么呢？

LIST_INIT 和 LIST_INSERT_HEAD

struct entry *n1, *n2, *n3, *np;struct listhead head; /* List head */int i;LIST_INIT(&head); /* Initialize the list */n1 = malloc(sizeof(struct entry)); /* Insert at the head */n1->data = 1; //我加的LIST_INSERT_HEAD(&head, n1, entries);

第 5 行就是 (&head)->lh_first = NULL; 初始化一個空的鏈表

第 9 行宏替換是：

if (((n1)->entries.le_next = (&head)->lh_first) != ((void *)0)) (&head)->lh_first->entries.le_prev = &(n1)->entries.le_next; (&head)->lh_first = (n1); (n1)->entries.le_prev = &(&head)->lh_first;

第 1 行的前半部分 ((n1)->entries.le_next = (&head)->lh_first) 和第 3 行完成頭插

第一行的后半部分判斷原先是不是空鏈表，如果是，if 條件不成立，否則會執行第 2 行。

第 4 行：讓 n1 的 entries.le_prev 指向 (&head)->lh_first；lh_first 的類型是 struct entry *，而 le_prev 的類型是 struct entry **

第 2 行不好理解，讓插入前的第一個節點的 entries.le_prev 指向 n1 的 entries.le_next。

所以，le_prev 被定義成 struct entry ** 就可以理解了，作者的意圖是讓它指向 struct entry * 類型，比如 lh_first 和 le_next

這時候再看本文開頭的圖，就理解了。

node 相當于是代碼中的 struct entry

SLIST_INSERT_HEAD(&head, n1, entries) 的意思是：把 n1 節點插入到鏈表 head 的頭部；第一個參數是表頭的地址，第二參數是待插入的節點的地址，第三個參數是無標簽結構體的成員名。

LIST_INSERT_AFTER

n2 = malloc(sizeof(struct entry)); /* Insert after */n2->data = 2; //我加的LIST_INSERT_AFTER(n1, n2, entries);

LIST_INSERT_AFTER(n1, n2, entries) 表示把節點 n2 插入到 n1 的后面。

第 3 行，宏替換后是

if (((n2)->entries.le_next = (n1)->entries.le_next) != ((void *)0)) (n1)->entries.le_next->entries.le_prev = &(n2)->entries.le_next; (n1)->entries.le_next = (n2); (n2)->entries.le_prev = &(n1)->entries.le_next;

把節點 n2 插入到 n1 的后面，我們看看哪些指針要改變

n1 的 entries.le_next

n2 的 entries.le_next

n2 的 entries.le_prev

插入之前 n1 后面的那個節點（就叫它 n0 吧）的 entries.le_prev；如果 n0 等于 NULL，就不需要考慮了

第 1 行的 (n2)->entries.le_next = (n1)->entries.le_next 解決的是 2

第 2 行代碼解決的是 4

第 3 行代碼解決了 1

第 4 行代碼解決了 3

LIST_INSERT_BEFORE

n3 = malloc(sizeof(struct entry)); /* Insert before */n3->data = 3; //我加的LIST_INSERT_BEFORE(n2, n3, entries);

LIST_INSERT_BEFORE(n2, n3, entries) 意思是把 n3 插入到 n2 的前面

第 3 行宏替換后是：

(n3)->entries.le_prev = (n2)->entries.le_prev; (n3)->entries.le_next = (n2); *(n2)->entries.le_prev = (n3); (n2)->entries.le_prev = &(n3)->entries.le_next;

把 n3 插入到 n2 的前面，我們看看哪些指針要改變

n2 的 entries.le_prev

n3 的 entries.le_next

n3 的 entries.le_prev

在插入 n3 之前， n2 前面的那個節點（就叫它 n1 吧）的 entries.le_next；

第 1 行解決了 3

第 2 行解決了 2

第 3 行解決了 4，這個有點復雜。(n2)->entries.le_prev 指向 n1 的 entries.le_next，對 (n2)->entries.le_prev 解引用，得到的就是 n1 的 entries.le_next，插入后，因為 n1 的后面是 n3，所以 n1 的 entries.le_next = n3;

第 4 行解決了 1

LIST_FOREACH

/* Forward traversal */LIST_FOREACH(np, &head, entries)printf("%i\n", np->data);

宏展開后是：

for ((np) = ((&head)->lh_first); (np); (np) = ((np)->entries.le_next))printf("%i\n", np->data);

遍歷每個節點，這個比較好懂。

注意，這種遍歷是不能刪除的，因為如果把 np 指向的節點刪除了，

(np) = ((np)->entries.le_next) 這句就不對了。

LIST_FOREACH(np, &head, entries) 用來遍歷鏈表的每個節點。第一個參數是臨時變量，指向當前的節點，第二個參數是表頭的地址，第三個 entries 是無標簽結構體的成員名。

LIST_REMOVE

LIST_REMOVE(n2, entries); /* Deletion */

宏替換后是

if ((n2)->entries.le_next != ((void *)0)) (n2)->entries.le_next->entries.le_prev = (n2)->entries.le_prev; *(n2)->entries.le_prev = (n2)->entries.le_next;

要刪除 n2，我們看看哪些指針要改變

n2 前面的那個節點（假設是 n1）的 entries.le_next

n2 后面的那個節點（假設是 n3）的 entries.le_prev；如果 n3 是 NULL，那就不用了

第 3 行解決了 1

1-2 行解決了 2

LIST_FIRST 和 LIST_NEXT

n1 = LIST_FIRST(&head);while (n1 != NULL) {n2 = LIST_NEXT(n1, entries);free(n1);n1 = n2;}

1：展開后是 n1 = ((&head)->lh_first);

LIST_FIRST(&head) 表示取鏈表的第一個節點

3：展開后是 n2 = ((n1)->entries.le_next);

LIST_NEXT(n1, entries) 表示取節點 n1 的下一個節點

---

參考資料

https://manpages.courier-mta.org/htmlman3/list.3.html

總結

以上是生活随笔為你收集整理的链表之LIST的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。