在 2016 年的 TED 演講 The mind behind Linux 中,Linus Torvalds 談到了程式碼的「品味」,並在投影片上以單向連結串列(singly linked list)的兩種實作方式來作說明。

以下是兩種實作的虛擬碼(pseudocode),第一種實作方式非常的直觀,我想也是我們大多數人的寫法。需要用到一個 if 條件來判斷要移除的節點是否是此串列的第一項,因為要移除的節點位置在首項還是在中間,會有不同處理方式。

Bad Taste

// Bad taste
remove_list_entry(entry) {
    prev = NULL;
    walk = head;

    // Walk the list
    while (walk != entry) {
        prev = walk;
        walk = walk->next;
    }

    // Remove the entry by updating the
    // head or the previous entry
    if (!prev)
        head = entry->next;
    else
        prev->next = entry->next;
}

要注意的是,這段虛擬碼著重在移除節點的思維方式,不討論記憶體釋放、串列為空或節點不存在等問題。

如果要移除的節點是第一個,那我們需要把 head 指到下一個節點,也就是 head = entry->next;反之若在中間,則需要將所移除節點的上一個節點指到下一個去,意即 prev->next = entry->next

Good Taste

而第二種實作方式,則完全不需要 if 條件判斷,不會有例外狀況的產生,我們來看程式碼:

// Good taste
remove_list_entry(entry) {
    // The "indirect" pointer points to the
    // *address* of the thing we'll update
    indirect = &head;

    // Walk the list, looking for the thing that
    // points to the entry we want to remove
    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    // ..and just remove it
    *indirect = entry->next;
}

畢竟是虛擬碼,又涉及指標操作,所以可能比較難讀懂。所以我改寫成以下能動的版本,完整程式則附於文末。

void remove_list_entry(List **head, List *entry) {
    // The "indirect" pointer points to the
    // *address* of the thing we'll update
    List **indirect = head;

    // Walk the list, looking for the thing that
    // points to the entry we want to remove
    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    // ..and just remove it
    *indirect = entry->next;
}

這裡用到的是指標的指標(pointer to pointer),再經過 List **indirect = head 後,此時會讓指標 indirect 指向指標 head,就是指標的指標。

注意,傳入函式時 remove_list_entry(&head, entry) 已經是傳入指標 head 的位址,所以這裡跟原先的虛擬碼不同,並非 List **indirect = &head

// Walk the list, looking for the thing that
// points to the entry we want to remove
while ((*indirect) != entry)
    indirect = &(*indirect)->next;
  1. (*indirect):用取值(dereference)運算子 * 拿到指標所指向的節點
  2. (*indirect)->next:得到 next 欄位所儲存的下一個節點
  3. &(*indirect)->next:用取址(reference)運算子 & 取得 next 欄位的位址
  4. indirect = &(*indirect)->next:將 next 欄位的位址存回 indirect
// ..and just remove it
*indirect = entry->next;

如果 *indirect 是要刪除的節點 entry,則指標 indirect 指向前一個節點中的 next 指標(指標的指標),所以 *indirect 設為 entry 的下一個節點,即 *indirect = entry->next

data-model-indirect

看一下記憶體的位址可能會比較好理解:

node 1: 0xa0
node 2: 0xc0
node 3: 0xe0

-------- p ---------
*p:             0xa0
(*p)->next:     0xc0

------ p -> p' -----
&(*p)->next:    0xa8

-------- p' --------
*(&(*p)->next): 0xc0
(*(&(*p)->next))->next: 0xe0

Conclusion

I don't want you to understand why it doesn't have the if statement. But I want you to understand that sometimes you can see a problem in a different way and rewrite it so that a special case goes away and becomes the normal case, and that's good code. — Linus Torvalds

Linus 透過這個例子是要跟讀者說明,有的時候只要我們換個角度去思考問題,或許可以將其中的特殊情況簡化為普通問題,而這就是好的程式。

Code Example

注意,此程式一樣沒有考慮記憶體釋放、串列為空或節點不存在等問題。

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

typedef struct list {
    int data;
    struct list *next;
} List;

void insert(List **head, int data) {
    List **indirect = head;
    List *tmp = malloc(sizeof(*tmp));
    tmp->data = data;
    tmp->next = NULL;

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

    *indirect = tmp;
}

void print(List *ptr) {
    while (ptr != NULL) {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

void remove_list_entry(List **head, List *entry) {
    // The "indirect" pointer points to the
    // *address* of the thing we'll update
    List **indirect = head;

    // Walk the list, looking for the thing that
    // points to the entry we want to remove
    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    // ..and just remove it
    *indirect = entry->next;
}

int main() {
    List *head;
    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    insert(&head, 4);
    insert(&head, 5);

    List *rm2 = head->next;
    List *rm4 = head->next->next->next;

    print(head);

    remove_list_entry(&head, head);
    print(head);

    remove_list_entry(&head, rm2);
    print(head);

    remove_list_entry(&head, rm4);
    print(head);

    return 0;
}
$ gcc -o goodtaste goodtaste.c && ./goodtaste

1 2 3 4 5
2 3 4 5
3 4 5
3 5

Reference