主要內容連結串列佇列對映二叉樹1. 連結串列單向連結串列、雙向連結串列環形連結串列

linux核心中的連結串列使用方法和一般資料結構中定義的連結串列是有所不同的。傳統連結串列：

傳統雙向連結串列.png

傳統的連結串列有個最大的缺點就是不好共通化，因為每個node中的data1，data2等等都是不確定的(無論是個數還是型別)。linux中的連結串列巧妙的解決了這個問題，linux的連結串列不是將使用者資料儲存在連結串列節點中，而是將連結串列節點儲存在使用者資料中。linux的連結串列節點只有2個指標(pre和next)，這樣的話，連結串列的節點將獨立於使用者資料之外，便於實現連結串列的共同操作。

Linux核心連結串列：

linux核心雙向連結串列.png

最大的問題在於，怎樣透過連結串列的節點來取得使用者資料？答案是透過container_of()宏

#define container_of(ptr, type, member) ({          \    const typeof(((type *)0)->member)*__mptr = (ptr);    \             (type *)((char *)__mptr - offsetof(type, member)); })

type一般是個結構體，也就是包含使用者資料和連結串列節點的結構體。ptr是指向type中連結串列節點的指標member則是type中定義連結串列節點是用的名字

比如：

struct student{    int id;    char* name;    struct list_head list;};

type是struct studentptr是指向stuct list的指標，也就是指向member型別的指標member就是 list

下面分析一下container_of宏:

// 步驟1：將數字0強制轉型為type*，然後取得其中的member元素((type *)0)->member  // 相當於((struct student *)0)->list// 步驟2：定義一個臨時變數__mptr，並將其也指向ptr所指向的連結串列節點const typeof(((type *)0)->member)*__mptr = (ptr);// 步驟3：計算member欄位距離type中第一個欄位的距離，也就是type地址和member地址之間的差// offset(type, member)也是一個宏，定義如下：#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)// 步驟4：將__mptr的地址 - type地址和member地址之間的差// 其實也就是獲取type的地址

步驟1，2，4比較容易理解，下面的圖以sturct student為例進行說明步驟3：

首先需要知道 ((TYPE *)0) 表示將地址0轉換為 TYPE 型別的地址由於TYPE的地址是0，所以((TYPE *)0)->MEMBER 也就是 MEMBER的地址和TYPE地址的差，如下圖所示：

理解步驟3.png

2. 佇列

FIFO，沒啥好說的

佇列的size在初始化時，始終設定為2的n次方使用佇列之前將佇列結構體中的鎖(spinlock)釋放3. 對映

類似於python裡的字典散列表是一種對映，但自平衡二叉樹搜尋樹也能實現儲存資料，比如C++中map就是紅黑樹嘛，在最壞情況下能有更好的表現Linux核心中的對映叫idr，目標是對映一個位於id標識數UID到一個指標

4. 紅黑樹5. 演算法複雜度

大o符號代表上限（更差情況）大θ符號代表最小上限

附上一份Linux核心學習大綱：