從刪除 linked-list node 看程式設計的品味

fcamel

·

Follow

Published in

fcamel的程式開發心得

·

4 min read

·

Feb 22, 2017

--

Share

偶然看到 Linus 在 TED 的演講，對多數人來說不是什麼吸引人的演講。不過從工程師的角度來說，滿有共鳴的。若要說 Linus 和一般工程師有什麼特別的不同，大概是他相當長時間專注在一件事上吧。用比較流行的說法，就是很有恆毅力！

演講的 14:27 開始，Linus 以刪除 singly-linked list node 為例，舉了兩個例子對照，說明何謂好品味。作為練習，我用 C 實作影片裡的兩個版本，加上我自己平常的寫法，共計寫了三版。這裡有完整的程式，後面逐一說明。另外，大概是為了方便聚焦說明，影片內的版本假設要刪除的目標一定在 list 內，我也基於同樣的假設實作。

Linus 舉的初學者版

void remove_list_node_v1(List* list, Node* target)
{
  Node* prev = NULL;
  Node* current = list->head;  // Walk the list
  while (current != target) {
    prev = current;
    current = current->next;
  }  // Remove the target by updating the head or the previous node.
  if (!prev)
    list->head = target->next;
  else
    prev->next = target->next;
}

最後需要用 if 處理不同的情況，顯得複雜。

我的版本

void remove_list_node_v2(List* list, Node* target)
{
  // Check the special case first.
  if (target == list->head) {
    list->head = list->head->next;
    return;
  }  // Walk the list and remove the target if it exists.
  for (Node* current = list->head; current->next; 
       current = current->next) {
    if (current->next == target) {
      current->next = current->next->next;
      break;
    }
  }
}

先用 early return 排除特例，再處理常例，方便閱讀。不過對這個問題來說，這和上面的版本沒差多少。

Linus 舉的有品味版

void remove_list_node_v3(List* list, Node* target)
{
  // The "indirect" pointer points to the *address*
  // of the thing we'll update.
  Node** indirect = &list->head;  // Walk the list, looking for the thing that 
  // points to the node we want to remove.
  while (*indirect != target)
    indirect = &(*indirect)->next;  *indirect = target->next;
}

想通 head 和 next 並沒有不同，我們的目標其實是「更新原本指向 target 的變數」，所以只有一個情況要處理。

結語

不知不覺寫了 18 年的程式，沒想到移除 singly-linked list node 可以寫得更精簡。和半年前看到 intrusive list 的時候有類似的感受：一但覺得習慣的作法已經夠好了，就不會再進步。在保持務實的同時，仍要提升自己的品味，才能持續地精進。

2017–02–26 更新

看到一些朋友的討論後，有了更具體的想法。從第三個例子衍生幾個有趣的點：

• 對多數人來說第三版有比較好讀嗎？這依開發者背景而定。開發 Linux kernel、常和指標打交道的人，大概會覺得比較好讀。開發一般應用程式、常用高階語言的人，大概覺得比較難讀。
• 這和 object-oriented programming、functional programming 類似，還不習慣這類思維前，會覺得不好讀；習慣後會覺得好讀。比方說 FP 的 map、filter、reduce 也是如此 (可以參考 Python 的例子)。
• 前兩個例子是從物件的角度思考，所以有分 head 和 non-head；第三個例子從「要更新什麼位置的資料」思考，於是察覺要更新的是同一類型的資料，不用分 head 和 non-head 處理。習慣 OOP 的思考方式後，有時反而將問題變複雜了，如何有效率地刪除資料結構節點是類似的例子。