二级指针链表删除

最近看到linux之父的一些视频切片，十分的有感悟、他说的一句特别有意思的话：

”我自己不是一个梦想家，只是一个工程师，很高兴有这么多的人在仰望天空，但我只是看着地面，想在我自己摔倒之前填上面前的坑洼。“

结合视频里面看到的两段代码，尽管我对c语言并不熟练、但是在好奇心以及十分在意代码简洁度和美丽的洁癖心理作用下，我尝试去理解了代码神奇之处。

代码讲的是链表节点的删除操作，第一段代码是常规的链表节点删除，需要将目标节点的上一个节点指针指向目标节点的下一个指针，达到跳过该节点的目的，最后将内存释放即可。第二段则是让我有些眼花，二级指针一出来我直接蒙圈了、这指针的指针是用来干什么的。想了半天都没有答案。代码及其的简单，看上去和第一段代码没有任何关联，可他们做的是相同的事情，这一下子勾起了我的求知欲。

因为第一段代码看似逻辑简单，但是他需要区别三种情况

当删除节点是头结点时
当删除节点是尾节点时
当删除节点是中间节点时

typedef struct node
{
    struct node * next;
    ....
} node;

typedef bool (* remove_fn)(node const * v);

// Remove all nodes from the supplied list for which the
// supplied remove function returns true.
// Returns the new head of the list.
node * remove_if(node * head, remove_fn rm)
{
    for (node * prev = NULL, * curr = head; curr != NULL; )
    {
        node * const next = curr->next;
        if (rm(curr))
        {
            if (prev)
                prev->next = next;
            else
                head = next;
            free(curr);
        }
        else
            prev = curr;
        curr = next;
    }
    return head;
}

由于需要区分这几种情况，导致代码变得冗杂、所以第一段代码显得稍长，但只用到了一级指针、理解起来稍微没有那么费力。

但linus不同意、认为这样的代码比第二种更差，第二种代码明显是更加以思考的。

我大致复刻了一下代码的样子：

void remove_node0(node_t * pHead,bool (*should_remove)(node_t* pNode))
{
    for (node_t ** curr = &pHead; *curr; /*curr will move*/) {
        node_t * node = *curr;
        if(should_remove(node))
        {
            *curr = node -> next;
            free(node);
        }
        else curr = &node -> next;
    }
}

写这段代码很有意思，利用二级指针指向头结点去遍历指针节点，这样删除的方式我认为是有区别第一种方式的

删除指针并不是将前面节点的next指向当前节点的下一个节点，也就是说不是改变前面节点的next指向的地址、说白了与前面节点没有任何关系了
他真正实现删除节点是通过将下一个节点指针的地址拖到了当前指针的地址处（后面节点的地址覆盖当前节点的地址）这样的好处是不需要考虑前节点是否真的存在，哪怕是最后一个节点大不了就覆盖了一个NULL过来，也是合理的。

用Linus的原话来讲___”纠正细节是令人自豪的事。也许这段代码并非庞大和重要，但我喜欢看那些注重代码细节的人写的代码，也就是清楚地了解如何才能编译出有效代码（而不是寄望于聪明的编译器来产生有效代码，即使是那些原始的汇编代码））。”___

Shen的博客

Two star programming

二级指针链表删除