【C】Linked List筆記

資料整理 Corn

議題

• 偵測環狀結構
• 排序問題確保空間複雜度為
  $O(1)$
• Traverse

Linked List 在 Linux 核心程式碼

在linux/list.h為Linked List中以circular doubly-linked list(雙向環狀鏈結串列) 進行實作，只要在自定義的資料結構中加入struct list_head便可以透過Linux List list的api進行操作。如下圖所示，也就是將其嵌入自定義的資料結構。

Linux核心原始程式碼巨集 container_of & offsetof

【Linux】Linux核心原始程式碼巨集 container_of & offsetof

Circular Doubly-Linked List

環狀鏈結串列 (circular Doubly-linked list)為linux kernel中實現list方式，包含了以下特性

• head到tail的時間複雜度從
  $O(n)$ 到
  $O(1)$
• node具有上個節點與下個節點的特性
• 任何節點都可以為開始位置

圖解如下:

• list_head 結構體

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

• 自定義結構體嵌入list_head
  自定義的結構體(container struct)被稱作entry，
  我們可以使用list_entry來求得自定義結構體的起始位址。

• LIST_HEAD - Declare list head and initialize it

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

• list_entry - Calculate address of entry that contains list node
  list_entry就是container_of的封裝而已喔!
  list_first_entry為取得在head->next的自定義結構體的起始位置，也就是第一個node
list_first_last為取得在head->prev的自定義結構體的起始位置，也就是最後一個node

#define list_entry(node, type, member) container_of(node, type, member)

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)

• list_for_each iterate over list nodes
  尋訪整個list，但不能對node與head進行修改，否則會造成未定義！

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

• list_for_each iterate over list nodes and allow deletions
  尋訪整個list，但可以針對node進行操作，因為有了safe確保下一個節點的位置

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
    node = safe, safe = node->next)