在地狱中烧烤！
在地狱中烧烤！
AboutRSS
有品味的代码：以删除链表节点为例

有品味的代码：以删除链表节点为例

Tags
Published
Published July 15, 2022
Author
linus在 TED interview(14:10) ted演讲中说过要写“有品味的代码”，是以删除链表中的一个节点为例子的。
这篇文章对这一点进行了很详细的描述：Linked lists, pointer tricks and good taste 。
下面是我在阅读后，自己的一些理解。
 

代码：删除链表节点

这是品位版：
void remove_elegant(list *l, list_item *target)
{
        list_item **p = &l->head;
        while (*p != target)
                p = &(*p)->next;
        *p = target->next;
}
这是教科书版：
void remove_cs101(list *l, list_item *target)
{
        list_item *cur = l->head, *prev = NULL;
        while (cur != target) {
                prev = cur;
                cur = cur->next;
        }
        if (prev)
                prev->next = cur->next;
        else
                l->head = cur->next;
}
 
第一印象就是优雅版比教科书版更短，但是理解了以后会发现，品位版不仅仅是行数更短，看起来更好看，而是背后的思路也是更优雅的。
优雅处就是去掉了一个分支的判断。

代码分析

首先要注意到的是，这两个版本的作用都是找到列表中，第一次出现的目标节点，然后把这个节点删除。
注意：这隐含的意思是，这个目标节点是一定存在于链表中的。
 

教科书版

notion image
教科书般很容易理解，当cur就是目标节点的时候，让prev指向cur的下一个节点，也就是
prev->next = cur->next;
但是要处理一个意外条件，那就是如果cur是第一个节点，此时prev的值是NULL。因为在函数开始的时候：
list_item *cur = l->head, *prev = NULL;
所以要在指向操作的时候，要加一个判断：
        if (prev)
                prev->next = cur->next;

品味版

在品味版中，让人比较迷惑的就是list_item **p = &l->head;
二级指针总是会让人感到迷惑，因为有时候会没办法第一时间明白是指向的东西是什么。
让我们一步一步来理清楚，只要搞懂了p是指向哪里的，就没问题了。
 
notion image
 
1. p是一个地址
list_item **p = &l->head;
二级、三级指针这种名字总是会让人感觉到害怕，但是其实我们只需要牢记：任何指针变量的值都是一个地址。
所以p变量的值，就是head变量的地址。p存的值，是一个地址。
 
2. *p也是一个地址
  • p代表的就是p变量的值，上面说过，p变量的值就是另外一个地址。这个地址那一块的内存，存放的就是节点。
这和target变量的值是一样的，target变量的值，就是目标节点的内存地址。
3. *p的另外一个含义
这就是最关键的地方，*p变量的值和图中p撇，p撇撇的值是一样。
也就是说，其实*p是和上一个节点的关联的
3. 对比
while (*p != target)
    p = &(*p)->next;
通过对比*p和target来判断*p的值等不等于目标节点的地址
4. 更改节点
*p = target->next;
在第3点说了，*p其实就是上一个节点的next变量，让上一个节点，指向target的下一个节点
这样target节点被排除在链表外面了。
target是一个指针，在c语言中，target->操作可以看做是(*target).的语法糖。
Copyright 2022 0x5a57