---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)
tags: [sysprog2020]

---

# 2020q3 Homework1 (quiz1)
contributed by < `KairC` >
[Github](https://github.com/KairC/sysprog_quiz1/blob/master/quiz1.c)

---

## 程式運作原理
### void add_entry(node_t **head, int new_value)
* 目的：以 new_value 建立新的節點，並在傳入的 linked list 的尾端，加入新的節點。
* 方法：
    * 傳入的參數 head 是一個指向 node_t 節點的指標的 address。
    * 利用 pointer to pointer ，建立一個指標的指標，node_t **indirect，它能夠指向 head 或是 node->next ，因為這兩個變數都是用來指向 node_t 節點的指標。
    * 對 indirect 取值，也就是 *direct ，可以得到 head 或 node->next 所儲存的資料，為一 node_t 節點的 address ，因此只要判斷 *direct 不是 NULL，就能夠確認 head 或 node->next 指向一個存在的 node_t 節點。
    * 利用 indirect = &(*indirect)->next 改變 indirect 所指向的指標，當 *indirect 為 NULL ，代表 indirect 目前指向了 linked list 中最後一個用來指向 node_t 節點的指標，該指標指向了 NULL ，將該指標的值重新設定為新節點的 address，即完成加入新節點。 

* Graphviz 圖例
    * 將 indirect 指向 head
    * 建立一個新節點 ，並用 new_node 指向它 (所謂"指向"，代表 new_node 儲存著新節點的記憶體位置)
    ```graphviz
   digraph add_entry1 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        new_node [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">new_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
        NULL_0 [label="NULL" shape=none]
        NULL_1 [label="NULL" shape=none]
        new_node_ptr [label="new_node" shape=none]
        
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        
        indirect [label="indirect" shape=none]
        head [label="head" shape=none]
        {rank=same new_node_ptr -> new_node}
        {rank=same head->node_0 indirect->head [color=red]}
    }
    ```

    
    * 判斷 *indirect 是否為 NULL 。意思就是 indirect 所指向的指標，該指標的儲存內容是否為 NULL ，如果不是 NULL 就代表該指標確實有指向某一塊記憶體位置，反之就代表該指標指向 NULL 。
    * 若不是 NULL 代表還沒到 linked list 的尾端，繼續往下一節點移動
    
    ```graphviz
   digraph add_entry2 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        new_node [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">new_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
        NULL_0 [label="NULL" shape=none]
        NULL_1 [label="NULL" shape=none]
        new_node_ptr [label="new_node" shape=none]
        
        
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        
        indirect [label="indirect" shape=none]
        head [label="head" shape=none]
        {rank=same new_node_ptr -> new_node}
        {rank=same head->node_0 indirect->head [color=red]}
    }
    ```
    ---
    ```graphviz
   digraph add_entry3 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        new_node [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">new_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
        NULL_0 [label="NULL" shape=none]
        NULL_1 [label="NULL" shape=none]
        new_node_ptr [label="new_node" shape=none]
        
        
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        
        indirect [label="indirect" shape=none]
        useless [shape=none label=""]
        useless->indirect [color=transparent]
        head [label="head" shape=none]
        {rank=same new_node_ptr -> new_node}
        {rank=same useless head->node_0 }
        indirect->node_0:next [color=red] 
    }
    ```
    ---
    ```graphviz
   digraph add_entry4 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        new_node [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">new_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
        NULL_0 [label="NULL" shape=none]
        NULL_1 [label="NULL" shape=none]
        new_node_ptr [label="new_node" shape=none]
        
        
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        
        indirect [label="indirect" shape=none]

        head [label="head" shape=none]
        {rank=same new_node_ptr -> new_node}
        {rank=same  head->node_0 }
        {rank=same indirect->node_1:next [color=red]} 
    }
    ```
    ---
    ```graphviz
   digraph add_entry5 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        new_node [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">new_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
        NULL_0 [label="NULL" shape=none]
        NULL_1 [label="NULL" shape=none]
        new_node_ptr [label="new_node" shape=none]
        
        
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        
        indirect [label="indirect" shape=none]

        head [label="head" shape=none]
        {rank=same new_node_ptr -> new_node}
        {rank=same  head->node_0 }
        {rank=same indirect->node_1:next [color=red]} 
    }
    ```
    ---
    ```graphviz
   digraph add_entry6 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        new_node [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">new_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
        NULL_0 [label="NULL" shape=none]
        NULL_1 [label="NULL" shape=none]
        new_node_ptr [label="new_node" shape=none]
        
        
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c ->NULL_0 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        
        indirect [label="indirect" shape=none]

        head [label="head" shape=none]
        {rank=same new_node_ptr -> new_node}
        {rank=same  head->node_0 }
        {rank=same indirect->node_2:next [color=red]} 
    }
    ```
    ---
    * 對於 indirect 指向的指標，改變其所儲存的內容。也就代表將該指標重新指向另外一塊記憶體位置。如此一來即可將 linked list 的尾端重新指向新的節點。
    ```graphviz
   digraph add_entry7 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        new_node [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">new_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
 
        NULL_1 [label="NULL" shape=none]
        new_node_ptr [label="new_node" shape=none]
        
        
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c ->new_node [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        new_node:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        
        indirect [label="indirect" shape=none]

        head [label="head" shape=none]
        {rank=same new_node_ptr -> new_node}
        {rank=same  head->node_0 }
        {rank=same indirect->node_2:next [color=red]} 
    }
    ```
    
### node_t *find_entry(node_t *head, int value)

* 目的：依照輸入的 value ，在 linked list 中找到第一個符合該 value 的節點。(若找不到會回傳 NULL ，但是該程式在後續並未對找不到做額外處理)
* 方法：建立 current 指標，指向 head 所指向的節點，在 linked list 上移動 current 以搜尋目標節點，在迴圈中止後回傳 current 所指向的記憶體位置。
* Graphviz 圖例：
  ```graphviz
     digraph find_entry {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">target_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    current [shape=none label="current"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
   
    
    {rank=same head->node_0 current->node_0 [color=red]}
    }    
  ```
  ---
  
    ```graphviz
     digraph find_entry {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">target_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    current [shape=none label="current"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
   
    
    {rank=same head->node_0 }
    {rank=same current->node_1 [color=red]}
    }    
  ```
  ---
     ```graphviz
     digraph find_entry {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">target_value</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]   
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    current [shape=none label="current"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
   
    
    {rank=same head->node_0 }
    {rank=same current->node_2 [color=red]}
    }    
  ```

### void remove_entry(node_t **head, node_t *entry)

* 目的：移除目標節點。
* 方法：
    * 利用 pointer to pointer ，可以將 head 與 node->next 看作一樣的東西，不必考慮移除第一個節點時還要搬動 head 的特殊情況。
    * *indirect 可以得到當前 indirect 所指向的指標，其所指向的節點的記憶體位置。因此根據傳入的參數 entry ，可以得到欲移除的節點的記憶體位置，比較 *indirect 與 entry 即可確認是否已找到欲移除的節點。
    * 找到目標節點後，更改 *indirect 所儲存的內容，即可將 *indirect 指向的節點改指向後一個節點，也就完成了移除。
* Graphviz 圖例：
  ```graphviz
    digraph remove_entry {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">target_entry</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="indirect"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 indirect->head [color=red]}
    }   
  ```
  ---
  ```graphviz
    digraph remove_entry {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">target_entry</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="indirect"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 }
    {rank=same indirect->node_0:next [color=red]}
    }   
  ``` 
    ---
  ```graphviz
    digraph remove_entry {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">target_entry</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="indirect"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 }
    {rank=same indirect->node_1:next [color=red]}
    }   
  ``` 
     ---
  ```graphviz
    digraph remove_entry {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">target_entry</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="indirect"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 }
    {rank=same indirect->node_1:next [color=red]}
    }   
  ``` 
     ---
  ```graphviz
    digraph remove_entry {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]

    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 }
    }   
  ```

### node_t *swap_pair(node_t *head)

* 目的：兩兩交換，i.e. 節點 0 與 節點 1 交換，節點 2 與 節點 3 交換，以此類推。
* 方法：
    * 先假設要對第一個節點與第二個節點作交換，第三個節點與第四個節點作交換。
    * 利用 pointer to pointer ，在 for-loop 的初始值設定時建立指標的指標 node_t **node 。
    * 在 linked list 中，每一個節點必定會被一個指標指著，node_t **node 藉由指向該指標，可以在 *node 指向第二節點時得知第三個節點的記憶體位置。
    * 如此一來就能將第一個節點改成指向第三個節點，並將第二節點改成指向第一個節點，即可完成交換。
    * 最後再將 node_t **node 移往指向一個用來指向第三個節點的指標，也就是第二個節點的 next 。
    * 再重複一次以上操作就能交換第三第四個節點。
* Graphviz 圖例：
  ```graphviz
    digraph swap_pair1 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 indirect->head [color=red]}
    }   
  ```
  ---
  ```graphviz
    digraph swap_pair2 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="blue">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    tmp [shape=none label="tmp"]
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_0 indirect->head [color=red] }
    {rank=same tmp->node_0 [color=blue]}
    }   
  ```
  ---
  ```graphviz
    digraph swap_pair3 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="blue">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    tmp [shape=none label="tmp"]
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1 indirect->head [color=red] }
    {rank=same tmp->node_0 [color=blue]}
    }   
  ```
  ---
  ```graphviz
    digraph swap_pair4 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="blue">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>> group=1]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>> group=1]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>> group=1]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    tmp [shape=none label="tmp"]
   
    
    node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1 indirect->head [color=red] }
    {rank=same tmp->node_0 [color=blue]}
    }   
  ```
  ---
  ```graphviz
    digraph swap_pair5 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="blue">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    tmp [shape=none label="tmp"]
   
    
    node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1 indirect->head [color=red] }
    {rank=same tmp->node_0 [color=blue]}
    }   
  ```
  ---
  ```graphviz
    digraph swap_pair6 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]

   
    
    node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1 indirect->head [color=red] }
    }   
  ```
    ---
  ```graphviz
    digraph swap_pair7 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]

   
    
    node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
    node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1}
    {rank=same indirect->node_0:next [color=red]}
    }   
  ```
    ---
  ```graphviz
    digraph swap_pair8 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="blue">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    tmp [shape=none label="tmp"]
   
    
    node_0:next:c->node_2 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
    node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1}
    {rank=same indirect->node_0:next [color=red]}
    {rank=same tmp->node_2 [color=blue]}
    }   
  ```
    ---
  ```graphviz
    digraph swap_pair9 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>> group=2]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>> group=2]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="blue">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>> group=1]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>> group=1]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    tmp [shape=none label="tmp"]
   
    
    {rank=same node_0:next:c->node_3 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]}
    node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]

    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1}
    {rank=same indirect->node_0:next [color=red]}
    node_2:next:c -> node_3 [tailclip=false arrowtail=dot dir=both]
    {rank=same tmp->node_2 [color=blue]}
    }   
  ```
    ---
  ```graphviz
    digraph swap_pair10 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="blue">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>> ]
    tmp [label="tmp" shape=none]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    

    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    
    
    node_0:next:c->node_3 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
    node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1}
    {rank=same indirect->node_0:next [color=red]}
    
    {rank=same tmp->node_2 [color=blue] }
    }   
  ```
    ---
  ```graphviz
    digraph swap_pair11 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="blue">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0" color="red">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    indirect [shape=none label="node"]
    tmp [shape=none label="tmp"]
   
    
    node_0:next:c->node_3 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
    node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1}
    {rank=same indirect->node_0:next [color=red]}
    {rank=same tmp->node_2 [color=blue]}
    }   
  ```
    ---
  ```graphviz
    digraph swap_pair12 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]


   
    
    node_0:next:c->node_3 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false]
    node_1:next:c -> node_0 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    
    
    
    {rank=same head->node_1}

    }   
  ```
### node_t *reverse(node_t *head)

* 目的：反轉 linked list
* 方法：
    * 利用三個指標，cursor、head、next 各指向三個節點。
    * 將 head 指向的節點，從原先指向 next 所指向的節點，改為指向 cursor 所指向的節點。
    * 再將 cursor 重新指向 head 指向的節點， head 重新指向 next 指向的節點，如此不斷重複以上步驟，直到 head 指向了 NULL ，即完成反轉。 
    * 起始時先將 cursor 指向 NULL ，因為反轉後原先的 head 會成為最後一個 node ，而最後一個 node 會指向 NULL。 
* Graphviz 圖例：
  ```graphviz
    digraph reverse1 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    cursor [shape=none label="cursor"]
   
    NULL_1->node_0 [color=transparent]
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 [color=red]}
    {rank=same cursor->NULL_1 [color=blue]}
    }   
  ```
  ---
  ```graphviz
    digraph reverse2 {
    rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    cursor [shape=none label="cursor"]
    next [shape=none label="next"]
   
    NULL_1->node_0 [color=transparent]
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 [color=red]}
    {rank=same cursor->NULL_1 [color=blue]}
    {rank=same next->node_1 [color=green]}
    }   
  ```
  ---
  ```graphviz
    digraph reverse3 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    cursor [shape=none label="cursor"]
    next [shape=none label="next"]
   
    node_0->node_1 [color=transparent]
    NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    {rank=same cursor->NULL_1 [color=blue]}
    {rank=same head->node_0 [color=red]}
    {rank=same next->node_1 [color=green]}
    }   
  ```
  ---
  ```graphviz
    digraph reverse4 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    cursor [shape=none label="cursor"]
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    next [shape=none label="next"]
   
    node_0->node_1 [color=transparent]
    NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 [color=red]}
    {rank=same cursor->node_0 [color=blue]}
    {rank=same next->node_1 [color=green]}
    }   
  ```
  ---
  ```graphviz
    digraph reverse5 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    cursor [shape=none label="cursor"]
    next [shape=none label="next"]
   
    node_0->node_1 [color=transparent]
    NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_1 [color=red]}
    {rank=same cursor->node_0 [color=blue]}
    {rank=same next->node_1 [color=green]}
    }   
  ```
  ---
  ```graphviz
    digraph reverse6 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    cursor [shape=none label="cursor"]
    next [shape=none label="next"]
   
    node_0->node_1 [color=transparent]
    NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_1 [color=red]}
    {rank=same cursor->node_0 [color=blue]}
    {rank=same next->node_2 [color=green]}
    }   
  ```
  ---
  ```graphviz
    digraph reverse7 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    cursor [shape=none label="cursor"]
    next [shape=none label="next"]
   
    node_0->node_1 [color=transparent]
    node_1->node_2 [color=transparent]
    NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_0:next:c->node_1:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_1 [color=red]}
    {rank=same cursor->node_0 [color=blue]}
    {rank=same next->node_2 [color=green]}
    }   
  ```
  ---
  ```graphviz
    digraph reverse8 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    cursor [shape=none label="cursor"]    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    next [shape=none label="next"]
   
    node_0->node_1 [color=transparent]
    node_1->node_2 [color=transparent]
    NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_0:next:c->node_1:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_1 [color=red]}
    {rank=same cursor->node_1 [color=blue]}
    {rank=same next->node_2 [color=green]}
    }   
  ```
  ---
  ```graphviz
    digraph reverse9 {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    cursor [shape=none label="cursor"]    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    NULL_1 [shape=none label="NULL"]
    next [shape=none label="next"]
   
    node_0->node_1 [color=transparent]
    node_1->node_2 [color=transparent]
    NULL_1->node_0:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_0:next:c->node_1:next [arrowhead=dot, arrowtail=normal, dir=both, tailclip=true constraint=true];
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_2 [color=red]}
    {rank=same cursor->node_1 [color=blue]}
    {rank=same next->node_2 [color=green]}
    }   
  ```
### void print_list(node_t *head)

* 目的：依序輸出 linked list 中所有的節點的 value 。
* 方法：利用 for-loop，建立指向 node_t 節點的指標 current，由 head 所指向的第一個節點開始，(1) 輸出 value ，(2) 將 current 往下一節點移動，重複以上步驟直到 current 指向 NULL 即完成依序輸出所有節點的 value 。
* Graphviz 圖例：
  ```graphviz
    digraph print_list {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    current [shape=none label="current"]
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 current->node_0 [color=red]}
    }   
  ```
  ---
  ```graphviz
    digraph print_list {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    current [shape=none label="current"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 }
    {rank=same current->node_1 [color=red]}
    }   
  ```
  ---
  ```graphviz
    digraph print_list {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    current [shape=none label="current"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 }
    {rank=same current->node_2 [color=red]}
    }   
  ```
  ---
  ```graphviz
    digraph print_list {
        rankdir=LR
    node [color=black shape=none margin=0 height=.3 ]
    node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">value_0</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_1</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_2</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">           <tr>
    <td port="data">value_3</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
    
    
    
    NULL_0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    current [shape=none label="current"]
    
   
    
    node_0:next:c->node_1 [arrowhead=normal, arrowtail=dot, dir=both, tailclip=false];
    node_1:next:c -> node_2 [tailclip=false, arrowtail=dot, dir=both]
    node_2:next:c -> node_3 [tailclip=false, arrowtail=dot, dir=both]
    node_3:next:c -> NULL_0 [tailclip=false, arrowtail=dot, dir=both]
    
    
    {rank=same head->node_0 }
    {rank=same current->node_3 [color=red]}
    }   
  ``` 

## 程式實際執行過程

* `node_t *head = NULL;`
```graphviz
    digraph main1 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        head [label="head" shape=none]
        NULL [label="NULL" shape=none]
        {rank=same head->NULL}
    }
```
---
* `add_entry(&head, 72);`
```graphviz
   digraph main2 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
    
        node_0:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        
 
    }
```
---
* `add_entry(&head, 101);`
```graphviz
   digraph main3 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">101</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
    
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        
 
    }
```
---
* `add_entry(&head, 108);`
```graphviz
   digraph main4 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">101</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]        
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
    
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        
 
    }
```
---
* `add_entry(&head, 109);`
```graphviz
   digraph main5 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">101</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
    
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        
 
    }
```
---
* `add_entry(&head, 110);`
```graphviz
   digraph main6 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">101</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
    
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        
 
    }
```
---
* `add_entry(&head, 111);`
```graphviz
   digraph main7 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">101</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_5 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">111</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
    
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> node_5 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_5:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        
 
    }
```
---
* `node_t *entry = find_entry(head, 101);`
```graphviz
   digraph main8 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_1 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">101</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_5 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">111</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        entry [label="entry" shape=none]
    
        node_0:next:c -> node_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_1:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> node_5 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_5:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        {rank=same entry->node_1 [color=red]}
        
 
    }
```
---
* `remove_entry(&head, entry);`
```graphviz
   digraph main9 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_5 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">111</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        entry [label="entry" shape=none]
        address [label="<memory address which has been freed>" shape=none]
    
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> node_5 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_5:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        {rank=same entry->address [color=red]}
    }
```
---
* `entry = find_entry(head, 111);`
```graphviz
   digraph main10 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_5 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">111</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        entry [label="entry" shape=none]
    
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> node_5 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_5:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        {rank=same head->node_0}
        {rank=same entry->node_5 [color=red]}
    }
```
---
* `remove_entry(&head, entry);`
```graphviz
   digraph main11 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]

 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        entry [label="entry" shape=none]
        address [label="<memory address which has been freed>" shape=none]
    
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]

        {rank=same head->node_0}
        {rank=same entry->address [color=red]}
    }
```
---
* `head = swap_pair(head);`
```graphviz
   digraph main12 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]

 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        entry [label="entry" shape=none]
        address [label="<memory address which has been freed>" shape=none]
    
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]

        {rank=same head->node_0}
        {rank=same entry->address [color=red]}
    }
```
---
* `head = reverse(head);`
```graphviz
   digraph main13 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]

 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        entry [label="entry" shape=none]
        address [label="<memory address which has been freed>" shape=none]
    
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]

        {rank=same head->node_0}
        {rank=same entry->address [color=red]}
    }
```

## 用指標的指標改寫 swap_pair 和 reverse
* 將傳入的參數 node_t *head 都改成指標的指標，也就是 node_t **head 。
* 將原先直接對 head 做操作的地方，都改成對指標的指標做操作，也就是將 head 代換成 *head_ptr ，可避免出現 `head = ... ` 的操作，雖然實際上一樣是在改變 head 儲存的記憶體位置。
* 最後以 `*head_pty = cursor` 直接將 *head_ptr ，也就是 head ，指向反轉後的第一個節點，達到避免回傳指標的目的。
```diff=
- node_t *swap_pair(node_t *head)
- {
-  for (node_t **node = &head; *node && (*node)->next;
+  void swap_pair(node_t **head) {
+  for (node_t **node = head; *node && (*node)->next;
       /*BB1*/ node = &(*node)->next->next) {
    node_t *tmp = *node;
    // BB2;
    *node = (*node)->next;
    tmp->next = (*node)->next;
    (*node)->next = tmp;
  }
-    return head;
}
```
```diff=
-node_t *reverse(node_t *head)
-{
-    node_t *cursor = NULL;
-    while (head) {
-        node_t *next = head->next;
-        // CCC;
-        head->next = cursor;
-        cursor = head;
-        head = next;
-    }
-    return cursor;
+void reverse(node_t **head) {
+  node_t *cursor = NULL;
+  node_t **head_ptr = head;
+  while (*head_ptr) {
+    node_t *next = (*head_ptr)->next;
+    // CCC;
+    (*head_ptr)->next = cursor;
+    cursor = *head_ptr;
+    *head_ptr = next;
+  }
+  *head_ptr = cursor;
}
```

## 用遞迴改寫 reverse
* 終止條件：當 indirect 所指向的指標，該指標所指向的節點的 next 指向了 NULL，則終止遞迴，往回傳值。
* 回傳值一律為已完成反轉的 linked list 的最後一個節點的記憶體位置。
* 由於 head 會在遞迴的最後一層移往原始 linked list 的最後一個節點，因此會遺失原始的 linked list 的第一個節點的記憶體位置。需要額外建立 node_t *tail 指標去保留該節點的記憶體位置。

==往下遞迴==
```graphviz
   digraph rev_recursive1 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        tail [label="tail" shape=none]
        {rank=same tail->node_0} 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
   
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]

        {rank=same head->node_0}
        {rank=same indirect->head [color=red]}
    }
```
---
```graphviz
   digraph rev_recursive2 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        tail [label="tail" shape=none]
        {rank=same tail->node_0} 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
   
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]

        {rank=same head->node_0}
        {rank=same indirect->node_0:next [color=red]}
    }
```
---
```graphviz
   digraph rev_recursive3 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        tail [label="tail" shape=none]
        {rank=same tail->node_0} 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
   
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]

        {rank=same head->node_0}
        {rank=same indirect->node_2:next [color=red]}
    }
```
---
==找到最後一個節點，將 head 指向它==
```graphviz
   digraph rev_recursive4 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        tail [label="tail" shape=none]
        {rank=same tail->node_0}
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
   
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]

        {rank=same head->node_4}
        {rank=same indirect->node_2:next [color=red]}
    }
```
---
==開始回傳==

```graphviz
   digraph rev_recursive5 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        tail [label="tail" shape=none]
        {rank=same tail->node_0} 
        NULL_1 [label="NULL" shape=none]
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
        tmp [label="tmp" shape=none]
        
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_4:next:c -> NULL_1 [arrowhead=normal arrowtail=dot tailclip=false dir=both]

        {rank=same head->node_4 tmp->node_4 [color=blue]}
        {rank=same indirect->node_2:next [color=red]}
    }
```
---
```graphviz
   digraph rev_recursive6 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        tail [label="tail" shape=none]
        {rank=same tail->node_0}
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
        tmp [label="tmp" shape=none]
        
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]

        {rank=same head->node_4 tmp->node_4 [color=blue]}
        {rank=same indirect->node_2:next [color=red]}
    }
```
---
```graphviz
   digraph rev_recursive7 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        tail [label="tail" shape=none]
        {rank=same tail->node_0}
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
        tmp [label="tmp" shape=none]
        
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:next:c -> node_4 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]

        {rank=same head->node_4 }
        {rank=same indirect->node_0:next [color=red]}
        {rank=same node_3 tmp->node_3 [color=blue]}
    }
```
---
```graphviz
   digraph rev_recursive8 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        tail [label="tail" shape=none]
        {rank=same tail->node_0}
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
        tmp [label="tmp" shape=none]
        
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:s -> node_3:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
        node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]

        {rank=same head->node_4 }
        {rank=same indirect->node_0:next [color=red]}
        {rank=same node_3 tmp->node_3 [color=blue]}
    }
```
==回到 void reverse(node_t **head)==

```graphviz
   digraph rev_recursive9 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        tail [label="tail" shape=none]
        {rank=same tail->node_0  [color=red]}
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
        tmp [label="tmp" shape=none]
        
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:next:c -> node_3 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_2:s -> node_3:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
        node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]

        {rank=same head->node_4 }
        {rank=same indirect->head}
        {rank=same node_2 tmp->node_2 [color=blue]}
    }
```
---
```graphviz
   digraph rev_recursive10 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        tail [label="tail" shape=none]
        {rank=same tail->node_0  [color=red]}
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
        tmp [label="tmp" shape=none]
        
        node_0:next:c -> node_2 [arrowhead=normal arrowtail=dot tailclip=false dir=both]
        node_0:s -> node_2:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
        node_2:s -> node_3:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
        node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]

        {rank=same head->node_4 }
        {rank=same indirect->head}
        {rank=same node_2 tmp->node_2 [color=blue]}
    }
```
---
```graphviz
   digraph rev_recursive11 {
        
        rankdir=LR
        node [color=black shape=none margin=0 height=.3 ]
        node_0 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">108</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_2 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">72</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_3 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">110</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
        node_4 [label=<
    <table border="0" cellborder="1" cellspacing="0">
    <tr>
    <td port="data">109</td>
    <td port="next">&nbsp;</td>
    </tr>
    </table>>]
 
        tail [label="tail" shape=none]
        {rank=same tail->node_0  [color=red]}
        head [label="head" shape=none]
        indirect [label="indirect" shape=none]
        tmp [label="tmp" shape=none]
        NULL [label="NULL" shape=none]
        

        node_0:s -> node_2:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
        node_2:s -> node_3:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
        node_3:s -> node_4:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]
        NULL -> node_0 [color=transparent]
        NULL:s -> node_0:next:s [arrowhead=dot arrowtail=normal tailclip=false dir=both]

        {rank=same head->node_4 }
        {rank=same indirect->head}
        {rank=same node_2 tmp->node_2 [color=blue]}
    }
```
## 實作 Fisher–Yates shuffle
* 對長度為 N 的 linked list，隨機骰出一數 k ， k 介於 1 到 N 之間
* 在 linked list 中找到第 k 個節點，將它移除並加入到新的 linked list 中。
* 重複以上兩步驟直到原先的 linked list 都被移除，即可得到經過隨機排列的 linked list 。

```clike=
node_t *pick_entry(node_t **head, node_t *entry) {
  node_t **indirect = head;

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

  *indirect = entry->next;
  entry->next = NULL;
  return entry;
}

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

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

  *indirect = entry;
}

void FisherYates_shuffle(node_t **head) {
  /* Get length of linked list */
  int len = 0;
  for (node_t **indirect = head; (*indirect); indirect = &(*indirect)->next)
    len++;
  if (len == 1)
    return;

  node_t *new_head = NULL;
  srand(time(NULL));
  for (; len > 0; len--) {
    /* Roll */
    int roll = (rand() % len) + 1;

    /* Strike-out */
    node_t **strike_out = head;
    for (; roll > 1; roll--, strike_out = &(*strike_out)->next)
      /* iterate */;

    add_entry_(&new_head, pick_entry(head, *strike_out));
  }

  *head = new_head;
}
```
::: warning
延伸問題：
* 檢驗洗牌後的結果是否「足夠亂」，確認演算法的實作正確性
* 思考現在的實作是否可以改善？或者是否有對於 singlely-linked list 更有效率的 shuffle 方式？(考慮到 O(n)的 access)
:::

###### tags: `sysprog2020`