# 2020q3 Week1

:::warning
課堂問答簡記
:::

## ccs100203
Q: 將 `add_entry` 裡的 `new_node` 插在 `head` 的前面要怎麼改?
如果傳進來的是前面 node 的 next 的 reference，那直接 dereference 後接上去就可以了
e.g. `add_entry(&(head->next), 109);`

void add_entry(node_t **head, int new_value)
{
    node_t *new_node = malloc(sizeof(node_t));
    assert(new_node);
    new_node->value = new_value;
    new_node->next = *head;
    *head = new_node;
}

但如果不是的話，e.g. `node_t *head2 = head->next; add_entry(&head2, 109);`，就變成用下面的方法，加一個 node 在後面，然後把資料移過去

void add_entry(node_t **head, int new_value)
{
    node_t *new_node = malloc(sizeof(node_t));
    assert(new_node);
    if(*head){
        new_node->value = (*head)->value;
        new_node->next = (*head)->next;
        (*head)->value = new_value;
        (*head)->next = new_node;
    }else{
        new_node->value = new_value;
        new_node->next = NULL;
        *head = new_node;
    }
}

## ZhuMon
Q 如何改 reverse 為 pointer to pointer

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

## tigger12613
Q 將 `add_entry` 裡的 `new_node` 插在 list 的最前面要怎麼改? (head前面可能還有node，請在確保整體linked list依舊正常的情況下在head前面插入`new_node` ．另外，不可新增傳入的參數)
我贊同 `ccs100203` 的方法，以下內容皆參考 `ccs100203` 的答案
`head'`是參數的(*head)

digraph structs {
        rankdir=LR;
        node[shape=box];
        struct0 [label= "real head",color=purple];
        struct5 [label= "head'"];
        struct1 [label= "last"];
        struct2 [label= "node1\n value of node1",color=purple];
        struct3 [label= "node2\n value of node2"];   
        struct4 [label= "node3\n value of node3"];
        
        {
            rank="same";
            struct0 -> struct2[color=purple]     
        }
        {
            rank="same";
            struct1 -> struct4        
        }
        {
            rank="same";
            struct5 -> struct3        
        }
        struct2 -> struct3[arrowhead=vee, tailclip=true, arrowsize=1,color=purple];
        struct3 -> struct4[arrowhead=vee, tailclip=true, arrowsize=1];
}

我們並不知道紫色的那些東西存不存在，所以新增一個 node ，把 node2 的 value 丟給 new node

digraph structs {
        rankdir=LR;
        node[shape=box];
        struct0 [label= "real head",color=purple];
        struct5 [label= "head'"];
        struct1 [label= "last"];
        struct2 [label= "node1\n value of node1",color=purple];
        struct3 [label= "node2\n value of node2"];   
        struct4 [label= "node3\n value of node3"];
        struct6 [label= "new node\nno value"];
        {
            rank="same";
            struct0 -> struct2[color=purple]     
        }
        {
            rank="same";
            struct1 -> struct4        
        }
        {
            rank="same";
            struct5 -> struct3        
        }
        struct2 -> struct3[arrowhead=vee, tailclip=true, arrowsize=1,color=purple];
        struct6 -> struct4[arrowhead=vee, tailclip=true, arrowsize=1];
        struct3 -> struct6[arrowhead=vee, tailclip=true, arrowsize=1];
}

copy value of node2 to new node

digraph structs {
        rankdir=LR;
        node[shape=box];
        struct0 [label= "real head",color=purple];
        struct5 [label= "head'"];
        struct1 [label= "last"];
        struct2 [label= "node1\n value of node1",color=purple];
        struct3 [label= "node2\n value of node2"];   
        struct4 [label= "node3\n value of node3"];
        struct6 [label= "new node\nvalue of node2"];
        {
            rank="same";
            struct0 -> struct2[color=purple]     
        }
        {
            rank="same";
            struct1 -> struct4        
        }
        {
            rank="same";
            struct5 -> struct3        
        }
        struct2 -> struct3[arrowhead=vee, tailclip=true, arrowsize=1,color=purple];
        struct6 -> struct4[arrowhead=vee, tailclip=true, arrowsize=1];
        struct3 -> struct6[arrowhead=vee, tailclip=true, arrowsize=1];
}

copy the new value to node2

digraph structs {
        rankdir=LR;
        node[shape=box];
        struct0 [label= "real head",color=purple];
        struct5 [label= "head'"];
        struct1 [label= "last"];
        struct2 [label= "node1",color=purple];
        struct3 [label= "node2\n new value"];   
        struct4 [label= "node3"];
        struct6 [label= "new node\nvalue of node2"];
        {
            rank="same";
            struct0 -> struct2[color=purple]     
        }
        {
            rank="same";
            struct1 -> struct4        
        }
        {
            rank="same";
            struct5 -> struct3        
        }
        struct2 -> struct3[arrowhead=vee, tailclip=true, arrowsize=1,color=purple];
        struct6 -> struct4[arrowhead=vee, tailclip=true, arrowsize=1];
        struct3 -> struct6[arrowhead=vee, tailclip=true, arrowsize=1];
}

這樣就可以在維持 link list 的正確性的情況下，插入一個node