Linus: 这样写的人根本不懂指针

关注公众号【高性能架构探索】，第一时间获取最新文章；公众号内回复【pdf】，免费获取经典书籍

你好，我是雨乐！

但凡刷过leetcode或者参加面试，大抵都遇到过如下这种问题：删除单链表中value为给定值的所有节点。

假设链表节点定义如下：

struct ListNode {
  int value;
  ListNode* next;
};

那么，为了实现该功能，我们需要从头到尾遍历链表，同时删除value等于给定值的节点，显然，我们会像如下这样写：

void Remove(ListNode *head, int to_remove) {
  ListNode *entry = head;
  ListNode *prev = NULL;

  while (entry) {
    if (entry->val == to_remove) {
        if (prev)
           prev->next = entry->next;
        else
           head = entry->next;
   } else {
      prev = entry;
  }
    entry = entry->next;
  }
}

代码实现中，我们所做的是遍历列表，直到entry为 NULL(第5行)。当我们遇到要删除的节点时（第 6 行），我们将当前next指针的值分配给前一个，进而从当前链表中摘除当前元素（第 8 行）。

上述这种写法，相对来说简单、易理解，但 Linus Torvalds却不这么认为，其曾经评价这种写法：

At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I’ve seen too many people who delete a singly-linked list entry by keeping track of the “prev” entry, and then to delete the entry, doing something like

if (prev)
prev->next = entry->next;
else
list_head = entry->next;

and whenever I see code like that, I just go “This person doesn’t understand pointers”. And it’s sadly quite common.

People who understand pointers just use a “pointer to the entry pointer”, and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a “*pp = entry->next”

其大概意思就是，对于写出本文一开始那种代码的评价就是：这个人不懂指针(This person doesn’t understand pointers)。

那么，Linus推荐的写法又是什么样的呢？

void Remove(ListNode *head, int to_remove) {
  ListNode **pp = &head;
  ListNode *entry = head;

  while (entry) {
    if (entry->val == to_remove)
        *pp = entry->next;
    else
        pp = &entry->next;
    entry = entry->next;
  }
}

这块代码看起来相对简洁，但是，如果第一次遇到这种实现，可能需要花一点时间进行理解~~

实际上刷过题的都知道，list相关问题首先声明个栈上的dummy node，能简化各种插入删除操作代码。使用dummy node操作后，代码如下：

void Remove(ListNode *head, int to_remove) {
  ListNode tmp;
  tmp.next = head;
  ListNode *pre = tmp;
  while (pre->next) {
    if (pre->next->val == to_remove) {
      pre->next = pre->next->next;
    } else {
      pre = pre->next;
    }
  }
}

相比来说，较Linus的实现方式更为简洁，但明显的，需要生成一个dummy节点，最明显的，内存使用上并不是最优，尽管其更易于理解和实现。

链表属于LC中相对来说比较简单的部分，选择一种适合自己的方式，并不一定非要选择最优，选择一个适合自己的。至于Linus实现的这种，可以保留意见，且当其最优吧，毕竟：没有人比Linus更懂指针，哈哈哈~