2021 年「資訊科技產業專案設計」課程範例: linked list

貢獻者: 梅仁耀

測驗 `1`

考慮一個單向 linked list，其結構定義為:

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:

add_entry: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
remove_entry: 移去指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
swap_pair: 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
reverse: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

"delete" 和 "remove" 看似都是「刪去某物」，在 Linux 核心的 include/list.h 中，這二個動作並存，但實際行為卻不同。依據 Difference between "delete" and "remove" 的解釋，可知:

"remove" 這動作對於 linked list 來說，是斷開節點和節點的關聯，也就是說原本若是 A
$\to$ B
$\to$ C，在 remove(B) 操作完成後，就會變成 A
$\to$ C 的節點關係。特別注意到 B 這個節點其實還存在於記憶體中，只是我們無法從節點間的關係看出來。於是 "remove" 可解讀為 "take away" (將某物帶走)
"delete" 則有 "erase" 的涵義，若用於 linked list，則指某個節點將被「抹除」，對應的記憶體空間可能會被釋放 (release) 或回收 (reclaim)，並非只是指標的變化

對應的程式碼如下:
































































































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

typedef struct __node {
    int value;
    struct __node *next;
} node_t;

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    /* 請填補 */
}

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; BB1) {
        /* 請填補 */
    }
    return head;
}

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        /* 請填補 */
    }
    return cursor;
}

void print_list(node_t *head)
{
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}

int main(int argc, char const *argv[])
{
    node_t *head = NULL;

    print_list(head);

    add_entry(&head, 72);
    add_entry(&head, 101);
    add_entry(&head, 108);
    add_entry(&head, 109);
    add_entry(&head, 110);
    add_entry(&head, 111);

    print_list(head);

    node_t *entry = find_entry(head, 101);
    remove_entry(&head, entry);

    entry = find_entry(head, 111);
    remove_entry(&head, entry);

    print_list(head);

    /* swap pair.
     * See https://leetcode.com/problems/swap-nodes-in-pairs/
     */
    head = swap_pair(head);
    print_list(head);

    head = reverse(head);
    print_list(head);

    return 0;
}

參考執行輸出: (第 1 行是換行符號)






72 101 108 109 110 111 
72 108 109 110 
108 72 110 109
109 110 72 108

請補完程式碼。

背景知識:

你所不知道的 C 語言: linked list 和非連續記憶體操作

貢獻者: RinHizakura

程式運作原理

注意圖中的所有 head 是以 main(caller) 裡的 head pointer 的角度，而不是做為參數的 pointer to pointer 的 head

`add_entry`

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;
    
    *indirect = new_node;
}

把一個 node 加到 linked list 的尾端:

這裡使用到了 pointer to pointer 的技巧，indirect 是指向 head pointer 的 pointer
首先，透過 malloc 建立一個新的 node 空間，填入 value 欄位後將其指向 NULL(因為 new_node 會放在尾端)

透過 assert 去檢查 new_node 是否為 NULL(malloc 是否失敗)，因此 AA1 = assert(new_node)
- 我認為這個 assert 的位置需要調整！詳細請閱讀往下的 Issue 1: where to use assert
indirect 如果指向的位置上不是 NULL，就往指向位置存放的 node 的下一個 node 指去，直到指到的位置上是放 NULL

這個位置就是 new_node 要放的地方，所以 AA2 = *indirect = new_node

Issue 1: where to use assert

為了模擬 malloc 出 NULL 的情境，設計了一個總是回傳 NULL 的 MALLOC，假裝配置記憶體失敗。


















static inline node_t *MALLOC(size_t size){
    return NULL;
}

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = MALLOC(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;
    
    *indirect = new_node;
}

意料之中，上面 add_entry 的寫法在 assert 前就有透過 new_node->value = new_value 去存取 new_node，因此會產生 Segmentation fault。

Segmentation fault (core dumped)

從 valgrind 偵測的結果來看，問題也確實是如此 (linked_list.c:16 等同上面程式的第 11 行)。

==108297== Invalid write of size 4
==108297==    at 0x1092C4: add_entry (linked_list.c:16)
==108297==    by 0x1090F7: main (main.c:10)
==108297==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

至於如果改成把 assert 接續在 malloc 之後，測試後會得到以下結果。

exec: linked_list.c:16: add_entry: Assertion `new_node' failed.
Aborted (core dumped)

從兩個結果的差異來思考。首先，如果我們的目的只是希望整個 linked list 的操作符合預期，並且在發生錯誤時 shut down，那麼是不是放不放 assert 都沒關係呢？(反正 dereference pointer 會發生 exception?)

為此我們需要了解 NULL pointer 的一些細節，在 C 語言規格書中對 NULL pointer 的定義是：

6.3.2.3 Pointers:
An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

因此，int* ptr = (int *)0; 或者 int* ptr = (int *)(void *)0 都同等於是 NULL pointer。而規格書裡也有提到：

Conversion of a null pointer to another pointer type yields a null pointer of that type.
Any two null pointers shall compare equal.

所以下面的程式會印出 equal!!。

int main()
{
        int* ptr = (int *)0;
        int* ptr2 = (int *)(void *)0;
        if(ptr == ptr2)
                printf("equal!!\n");

        return 0;
}

而 dereference 的操作，在規格書裡如是說：

6.5.3.2 Address and indirection operators
If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined

Deference NULL pointer 是 undefined behavior。在 Null pointer 中也提到，在某些系統上 dereference NULL pointer 是可能會繼續執行然而導致非預期的結果的。所以如果想要即時的掌握錯誤，assert 應該接續在 malloc 之後，才能保證即時的檢查到錯誤。

Issue 2: when to use assert?

我們在 lab0 的時候，以類似的插入節點的 function q_insert_head 為例，對 malloc 的檢查是用 if 分支，雖然也對 malloc 的失敗做了處理，但與 assert 程式會保持 linked list 的原始模樣但程式不會直接 crash。

newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
    return false;

那麼在真實的應用上，在甚麼情境下使用哪個方法可能會比較好呢？

assert 的中文是斷言，因此，程式碼的 assert 就像是在對閱讀程式碼的人說「這一行 statement 必定是這種情況」，當出現程式撰寫者預期外的情況，則必須要回頭來檢查錯誤。因此，assert 基本就是一個比較粗糙、但方便的 debug 工具，我們可以在編譯中加上 -DNDEBUG 將其變成 no operation。

使用 if 檢查的情況，則比較像是我們預期使用程式的人可能誤用(錯誤的參數等)，程式可以容忍使用者犯傻，告訴他「這個操作不合法喔」，然後維持正確的狀態讓程式往下執行。

My conclusion

因此，結論來說，以上面的程式而言，如果我們的目的只是希望在發生錯誤時 shut down，考慮到 dereference 也有可能不會發生 exception，所以 assert 的存在仍然是必要的，至於 assert 該放在原本的位置或者接續在 malloc 之後，以此為目的的話都可以。但是如果我們想要在出錯時可以直接抓到錯誤之處，因為 Segmentation fault 並不會直接反映出錯的地方，或者考慮到使用 assert 的邏輯的話，我會認為接續在 malloc 之後才是正確的。

`find_entry`

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}

從 head 開始，逐步尋找符合儲存的值為 value 的 node。

`remove_entry`

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

移除目標的 entry。pointer to pointer 的使用手法類似前面，假設初始為下圖，而 head 是 A，entry 是 C。

一直前進，直到找到 entry

把 B->next 下的節點換成 D，於是就變成了

最後再把 entry 指向的節點 C 釋放掉，大功告成

`swap_pair`

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; node = &((*node)->next->next)) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

將節點兩兩交換(第 0 個跟第 1 個交換、第 2 個跟第 3 個…)。下面以前兩個 node 的操作來解釋 swap。

首先 node_t *tmp = *node

然後，把 node 指到的地址換成下一個節點的地址。因此 BB2 會是 *node = (*node)->next; 。注意到因為交換的是節點的位址，因此第一個 iteration 的這一步會把 head 的位址變成 B 的位址，也就是讓 head 指向變成開頭的 B。

再來是 tmp->next = (*node)->next

最後是 (*node)->next = tmp。

把 A、B 處理完後，要把 node 指向的位址換到 C 去。 node = &((*node)->next->next)

根據 C 語言規格書
& (address of) 是屬於 6.5.3 Unary operators
-> 則是屬於 6.5.2 Postfix operators

又在規格書第 76 頁中有提到：
The syntax specifies the precedence of operators in the evaluation of an expression, which is the same as the order of the major subclauses of this subclause, highest precedence first.

The exceptions are cast expressions (6.5.4) as operands of unary operators
(6.5.3), and an operand contained between any of the following pairs of operators: grouping parentheses () (6.5.1), subscripting brackets [] (6.5.2.1), function-call parentheses () (6.5.2.2), and the conditional operator ? : (6.5.15).

因此在章節比較前面的 -> 優先權會大於 &，所以 &((*node)->next->next) 和 node = &(*node)->next->next 等價

也可以透過下面的程式來驗證這點。
























void test(node_t *head)
{
    node_t **node = &head;  
    node = &(*node)->next->next;
    printf("test: %ld, value: %d\n", (unsigned long)node, (*node)->value);
}

void test_2(node_t *head)
{
    node_t **node = &head;  
    node = &((*node)->next->next);
    printf("test_2: %ld, value: %d\n", (unsigned long)node, (*node)->value);
}

int main ()
{
    node_t *head = NULL;
    add_entry(&head, 1); 
    add_entry(&head, 2); 
    add_entry(&head, 3); 
    
    test(head);
    test_2(head);
}

得到結果：

test: 94834115597000, value: 3
test_2: 94834115597000, value: 3

`reverse`










node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        head->next = cursor; cursor = head;
        head = next;
    }
    return cursor;
}

將 linked list 倒置。一開始 linked list 大概如下圖：

首先 node_t *next = head->next;

cursor 就是回頭的節點，head->next = cursor; cursor = head

最後是 head = next;。後面就重覆前面的步驟，把 linked list 所指的方向逆轉。最後 cursor 會指向原本 linked list 的最尾端，也就是新的 head，return 之。

改寫為 pointer to pointer

Bonus: `delete_list`

為了方便做實驗時更新 linked list 且避免 memory leak，實作一個釋放 linked list 上所有節點的 function。

void delete_list(node_t **head) {

  while (*head) {
    node_t *next = (*head)->next;
    free(*head);
    *head = next;
  }
}

`swap_pair`

由於原本的 node 已經是在對 pointer to pointer 做操作，所以可以簡單的改寫 swap_pair 成：

void swap_pair(node_t **head)
{
    for (; *head && (*head)->next;
         head = &((*head)->next->next)) {
        node_t *tmp = *head;
        *head = (*head)->next;
        tmp->next = (*head)->next;
        (*head)->next = tmp;
    }   
}

考慮到我們的 linked list 結構比較簡單，node 裡只有下一個的位置和儲存的數值，這裡有另外一個也可以做到結果相同的 swap 方法。我們可以只是把節點中的 value 做交換。

#define XORSWAP_UNSAFE(a, b)                                                   \
  ((a) ^= (b), (b) ^= (a),                                                     \
   (a) ^= (b)) /* Doesn't work when a and b are the same object - assigns zero \
                  (0) to the object in that case */
#define XORSWAP(a, b)                                                         \
  ((&(a) == &(b)) ? (a) /* Check for distinct addresses */                    \
                  : XORSWAP_UNSAFE(a, b))

void swap_pair_by_value(node_t **head)
{
    for (; *head && (*head)->next;
         head = &((*head)->next->next)) {
        XORSWAP((*head)->value, (*head)->next->value);
    }
}

Bonus: 兩個方法的執行時間差異

我想要知道哪個方法可能運行的比較快，所以設計了一段測試程式。考慮到 cache 可能的影響，所以每次 swap 的都是一個新的 linked list，並且透過 taskset 命令僅在單核上運作。

  for (int num = 10; num < 2000; num++){
      for (int i=0; i<num; i++){
        add_entry(&head, (rand() % 1000));
      }   
 
      struct timespec tt1, tt2;
      clock_gettime(CLOCK_MONOTONIC, &tt1);
      swap_pair(&head);
      clock_gettime(CLOCK_MONOTONIC, &tt2);
    
      long long time = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                     (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);

      delete_list(&head);
    
      for (int i=0; i<num; i++){
        add_entry(&head, (rand() % 1000));
      }   
      clock_gettime(CLOCK_MONOTONIC, &tt1);
      swap_pair_by_value(&head);
      clock_gettime(CLOCK_MONOTONIC, &tt2);
    
      long long time2 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                     (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);
    
      printf("%d, %lld, %lld\n", num, time, time2);
      delete_list(&head);
  }

考慮到可能的誤差，因此我通過簡單的統計方法 standard deviation around the mean 來分析運行時間(詳細參閱 GitHub)。得到如下的圖：

原本我預期交換數值的方法會比較快，畢竟不用調整 next 指去哪，又可以通過 bitwise 運算提升交換的效率。然而在圖中驚訝的發現，兩個方法的快慢其實沒有顯著的差異。

初步猜測是 XOR 裡的 branch 判斷導致。因為可以確認自己對 XOR 的使用是對於兩個相異的 object(粗淺的說，不同的變數)，因此我們把程式調整為沒有分支的 XORSWAP_UNSAFE，然後得到的結果是：

感覺好像真的是 branch 產生影響？於是我試圖用 perf 去觀察使用 XORSWAP_UNSAFE 和 XOR 的在 node 數量 2000 時的 branch misses，

XORSWAP

sudo perf stat -e branch-misses:u,branches:u ./exec

 Performance counter stats for './exec':

             5,668      branch-misses:u           #    0.26% of all branches        
         2,214,808      branches:u                                                  

       0.005515600 seconds time elapsed

       0.005551000 seconds user
       0.000000000 seconds sys

XORSWAP_UNSAFE

sudo perf stat -e branch-misses:u,branches:u ./exec

 Performance counter stats for './exec':

             5,656      branch-misses:u           #    0.26% of all branches        
         2,213,809      branches:u                                                  

       0.007371779 seconds time elapsed

       0.007382000 seconds user
       0.000000000 seconds sys

從結果來看，XORSWAP_UNSAFE 的 branch miss 雖然看似少一些，但兩者的差異並不大。雖然也有可能是因為圖中的時間是用 ns 等級，所以看起來會差距比較明顯，但是如此接近的 branch miss 不該是導致如此差距的原因。為了可以得知更多的細節，我嘗試使用 Cachegrind 檢查記憶體的實際情況：

$ valgrind --tool=cachegrind ./exec
$ cg_annotate <file>
$ cg_diff <file1> <file2>

XORSWAP

--------------------------------------------------------------------------------
Ir         I1mr  ILmr  Dr        D1mr    DLmr  Dw        D1mw  DLmw  
--------------------------------------------------------------------------------
17,116,037 1,050 1,029 8,303,820 755,543 2,081 2,131,776 4,773 1,596  PROGRAM TOTALS

--------------------------------------------------------------------------------
Ir         I1mr ILmr Dr        D1mr    DLmr Dw        D1mw  DLmw   file:function
--------------------------------------------------------------------------------

    55,014    4    4    41,005   1,002    0     4,003     0     0  /home/rin/Github/linked-list/linked_list.c:swap_pair_by_value

XORSWAP_UNSAFE

--------------------------------------------------------------------------------
Ir         I1mr  ILmr  Dr        D1mr    DLmr  Dw        D1mw  DLmw  
--------------------------------------------------------------------------------
17,109,037 1,047 1,027 8,298,820 755,543 2,081 2,131,776 4,773 1,596  PROGRAM TOTALS

--------------------------------------------------------------------------------
Ir         I1mr ILmr Dr        D1mr    DLmr Dw        D1mw  DLmw   file:function
--------------------------------------------------------------------------------

    48,014    3    3    36,005   1,002    0     4,003     0     0  /home/rin/Github/linked-list/linked_list.c:swap_pair_by_value

觀察一下兩者的差異：

Ir(執行的總指令數)總體的差距為 17,116,037 - 17,109,037 = 7000 與 swap_pair_by_value 的 55,014-48014 = 7000 相等
Dr(memory 的讀取次數)總體的差距為 8,303,820 - 8,298,820 = 5000 與 swap_pair_by_value 的 41,005 - 36,005 = 5000 相等

仔細一想，就發現其實自己把問題複雜化了，因為 XORSWAP_UNSAFE 的指令會比 XORSWAP 少，不需要讀取記憶體位址檢查是否相同，所以可以執行的快一些原本就十分合理。而當節點變多，指令的差異量就會表現在時間上。

設計實驗時，應考慮 linked list 節點結構中的資料可能很多項，成員可能還指向其他記憶體空間。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

`reverse`

概念和原本的 reverse 並無太大差異，只是為了確保 head 最後會是指到原本 linked list 的尾端，把 while 迴圈中的判斷條件條件調整成判斷下一個是否為 NULL。












void reverse(node_t **head) {
    node_t *prev = NULL;
    node_t *next = (*head)->next;

    (*head)->next =  prev;
    while(next){
            prev = (*head);
            *head = next;
            next = next->next;
            (*head)->next = prev;   
    }   
}

遞迴版本的 `reverse`

整體的概念和前面的 reverse 相同：首先改變現在的 node 的指向，把它往前指。如果下一個要被調整的 node 為 NULL，表示已經找到原本 linked list 的尾端，因此要把 head 更新到該位置上並且 return。否則就繼續往下 recursive。





















void recursive_rev(node_t **head) 
{ 
    if (!head)
        return;

    recursive_rev_step(*head, NULL, head); 
} 

void recursive_rev_step(node_t *curr, node_t *prev, node_t **head)
{ 
    node_t *next = curr->next;
    curr->next = prev;    
    
    if (!next) {        
        *head = curr;
        return; 
    } 
  
    recursive_rev_step(next, curr, head);
}

Fisher–Yates shuffle

Fisher–Yates shuffle 是用來將一段有限的數列做隨機排序(排列的結果是等概率的)的演算法。

Pencil-and-paper method

最原始的方法是由 Ronald Fisher 和 Frank Yates 手寫的，大致的概念如下：

假設初始的序列如下:

隨機數範圍	選擇隨機數	原始序列	產生序列
		1 2 3 4 5

5 個數字的序列，因此從 1~5 間隨機選一數字，以這裡為例是 3，所以把原始序列從左開始數的第 3 個數字 3 放到結果中

隨機數範圍	選擇隨機數	原始序列	產生序列
1-5	3	1 2 3 4 5	3

4 個數字的序列，因此從 1~4 間隨機選一數字，以這裡為例是 4，所以把原始序列從左開始數的第 4 個數字 5 放到結果中

隨機數範圍	選擇隨機數	原始序列	產生序列
1-4	4	1 2 3 4 5	3 5

重複這個流程，隨機數範圍為 0 (原始序列的內容都被搬到產生的序列中)

Modern method

考慮到在計算機上的使用，Richard Durstenfeld 提出了改進。因為原始方法「從左開始數的第 n 個數字」這個過程涉及對原始 array 的額外調整，所以時間複雜度會是

O (n^{2})

，這裡的時間複雜度則是

O (n)

。此外，不需另外產生一個儲存的序列(inplace)，而是透過 swap 的方式達到同等的效果。

這裡的時間複雜度當是以 array 儲存的前題下，考慮到資料結構的差異可能也會有複雜度的差異，必須思考自己使用的資料結構給出最恰當的演算法。

假設初始的序列如下:

隨機數範圍	選擇隨機數	原始序列
		1 2 3 4 5

從 1~5 間隨機選一數字，以這裡為例是 3，所以把原始序列從左開始數的第 3 個數字和最後 1 個數字交換

隨機數範圍	選擇隨機數	更新後序列
1-5	3	1 2 5 4 3

從 1~4 間隨機選一數字，以這裡為例是 2，所以把原始序列從左開始數的第 2 個數字和倒數第 2 個數字交換

隨機數範圍	選擇隨機數	更新後序列
1-4	2	1 4 5 2 3

重複這個流程，直到隨機數範圍為 0

實作








































void shuffle(node_t **head)
{
    srand(time(NULL));
    
    // First, we have to know how long is the linked list
    int len = 0;
    node_t **indirect = head;
    while (*indirect) {
        len++;
        indirect = &(*indirect)->next;
    }   

    // Append shffling result to another linked list
    node_t *new = NULL;
    node_t **new_head = &new;
    node_t **new_tail = &new;

    while (len) {
        int random = rand() % len;
        indirect = head;

        while (random--)
            indirect = &(*indirect)->next;

        node_t *tmp = *indirect;
        *indirect = (*indirect)->next;

        tmp->next = NULL;
        if (new) {
            (*new_tail)->next = tmp;
            new_tail = &(*new_tail)->next;
        } else 
            new = tmp; 

        len--;
    }   

    *head = *new_head;
}

首先，先走訪整個原始的 linked list，算出原本的 linked list 有多長
用一個 new 作為新的 linked list 的 dummy node
- new_head 總是指向新 linked list 的頭，這是為了回傳時更新 head
- new_tail 總是指向新 linked list 的尾端，這是為了重新 append 的時候不需要從頭找起
每次產生舊 linked list 長度範圍的隨機亂數 n，找到第 n 個 node，拆下來 append 到新的 linked list 上
重覆直到舊的 linked list 上沒有 node (len == 0)

延伸問題：

檢驗洗牌後的結果是否「足夠亂」，確認演算法的實作正確性
思考現在的實作是否可以改善？或者是否有對於 singlely-linked list 更有效率的 shuffle 方式？(考慮到
$O (n)$ 的 access)

2021 年「資訊科技產業專案設計」課程範例: linked list

測驗 1

程式運作原理

add_entry

Issue 1: where to use assert

Issue 2: when to use assert?

My conclusion

find_entry

remove_entry

swap_pair

reverse

改寫為 pointer to pointer

Bonus: delete_list

swap_pair

Bonus: 兩個方法的執行時間差異

reverse

遞迴版本的 reverse

Fisher–Yates shuffle

Pencil-and-paper method

Modern method

實作

Read more

你所不知道的 C 語言：動態連結器篇

運用 Perf 分析程式效能並改善

Linux 核心專題: 虛擬無線網路裝置驅動程式

資訊科技詞彙翻譯

測驗 `1`

`add_entry`

`find_entry`

`remove_entry`

`swap_pair`

`reverse`

Bonus: `delete_list`

`swap_pair`

`reverse`

遞迴版本的 `reverse`