链表、指针技巧与良好品味

引言

在2016年的一次TED采访中（14:10），Linus Torvalds谈到了他认为编码中的良好品味是什么。作为例子，他展示了两种在单链表中删除元素的实现方法（如下所示）。为了从列表中删除第一个元素，其中一个实现需要一个特殊情况，另一个则不需要。显然，Linus更喜欢后者。他的看法是：

我不希望你理解为什么它没有if语句。但我希望你理解，有时你可以以不同的方式看待一个问题，并重写它，使得一个特殊情况消失，变成了正常情况，这就是好代码。

他展示的代码片段是C风格的伪代码，简单易懂。然而，正如Linus在上述消息中提到的，这些片段缺乏概念性解释，立刻理解更优雅解决方案的工作原理并不明显。接下来的两部分详细展示了技术方法，并展示了间接寻址方法为何如此巧妙。最后一部分将解决方案从项删除扩展到插入项。

代码示例

图1展示了一个整数单链表的基本数据结构。

flowchart LR
	subgraph list_item
		value:int --- p1{{next:ptr}}
	end
	p{{head}} --> list_item
	p1 --> next_node

数字是随意选择的整数值，六边形表示指针。 head是一个类型为list_item *的指针，每个框都是list_item结构体的一个实例，每个实例都有一个成员变量（在代码中称为next）的类型为list_item*，它指向下一个元素next_node。该数据结构的C语言实现是：

struct list_item {
        int value;
        struct list_item *next;
};
typedef struct list_item list_item;

struct list {
        struct list_item *head;
};
typedef struct list list;

我们还包括了一个（最小化的）API：

/* The textbook version */
void remove_cs101(list *l, list_item *target);
/* A more elegant solution */
void remove_elegant(list *l, list_item *target);

有了这些，我们来看看remove_cs101() 和 remove_elegant() 的实现。这些示例的代码等价于 Linus 示例中的伪代码，并且也可以编译和运行。

CS101版本

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;
}

标准的CS101方法使用了两个遍历指针cur和prev，分别标记列表中当前和之前的遍历位置。cur从列表头head开始，并前进直到找到目标。prev开始时为NULL，并且每次cur前进时随后都会更新为cur之前的值。在找到目标后，算法测试prev是否非NULL。如果是，表示该项不在列表的开头，移除操作包括绕过cur重新连接链表。如果prev是NULL，cur就指向列表中的第一个元素，在这种情况下，移除意味着将列表头向前移动。

一个更优雅的解决方案

更优雅的版本代码更少，且不需要单独的分支来处理列表中第一个元素的删除。

void remove_elegant(list *l, list_item *target)
{
        list_item **p = &l->head;
        while (*p != target)
                p = &(*p)->next;
        *p = target->next;
}

该代码使用一个间接指针p，它持有一个指向列表项指针的地址，从head的地址开始。在每次迭代中，该指针被推进以持有指向下一个列表项的指针的地址，即当前list_item的下一个元素的地址。当指向列表项的指针*p等于目标项target时，我们退出搜索循环并从列表中删除该项。

它是如何工作的

关键在于使用间接指针p有两个实际上的好处：

它允许我们以一种方式解读链表，使得头指针成为数据结构的一个积极部分。这消除了移除第一个项所需的特殊情况。
它还允许我们在不放弃指向目标的指针的情况下评估while循环的条件。这让我们能够修改指向目标的指针，并且只用一个迭代器就可以摆脱prev和cur。

让我们依次分析这些好处。

整合头指针

标准模型将链表解读为一系列list_item实例。序列的开始可以通过头指针访问。这导致了头指针仅被视为访问列表开始的一个句柄。prev和cur是类型为list_item *的指针，总是指向一个项或NULL。优雅实现使用间接寻址方案，提供了对数据结构的不同视角：这里，p是类型为list_item **的，持有指向当前列表项的指针的地址。当我们推进指针时，我们转向指向下一个列表项的指针的地址。

在代码中，这转化为p = &(*p)->next，意味着我们

(*p)：解引用地址到当前列表项的指针
->next：再次解引用那个指针并选择持有下一个列表项地址的字段
&：取那个地址字段的地址（即获取一个指向它的指针）

这对应于一种解读数据结构的方式，其中列表是指向list_items的指针序列。

维护一个句柄

该解决方案的另一个额外好处是，它支持在整个遍历过程中编辑当前项的前驱的next指针。由于p持有指向列表项的指针的地址，搜索循环中的比较变为

while (*p != target)

如果*p等于target，搜索循环将退出，一旦它退出，我们仍然能够修改*p，因为我们持有它的地址p。因此，尽管迭代循环直到我们遇到目标，我们仍然保持一个句柄（下一个字段的地址或头指针），可以用来直接修改指向该项的指针。

这就是为什么我们可以使用*p = target->next修改进入项的指针以指向不同位置，以及为什么我们不需要prev和cur指针来遍历列表以移除项的原因。

更进一步

事实证明，remove_elegant()背后的思想可以应用于提供另一个列表API函数的特别简洁实现：insert_before()，即在另一个项之前插入给定项。

在现有项前插入

首先，让我们在list.h中的列表API添加以下声明：

void insert_before(list *l, list_item *before, list_item *item);

该函数将接受一个指向列表的指针，一个指向该列表中某个项的指针before，以及一个指向新列表项item的指针，该函数将在before之前插入item。

快速重构

在我们继续之前，我们将搜索循环重构为一个单独的函数

static inline list_item **find_indirect(list *l, list_item *target)
{
        list_item **p = &l->head;
        while (*p != target)
                p = &(*p)->next;
        return p;
}

并且像这样在 remove_elegant() 中使用那个函数

void remove_elegant(list *l, list_item *target)
{
        list_item **p = &l->head;
        while (*p != target)
                p = &(*p)->next;
        *p = target->next;
}

实现`insert_before()`函数

使用 find_indirect()，实现 insert_before() 就变得很直接了：

void insert_before(list *l, list_item *before, list_item *item)
{
        list_item **p = find_indirect(l, before);
        *p = item;
        item->next = before;
}

一个特别美妙的结果是，实现对边缘情况具有一致的语义：如果before指向列表头，新项将被插入到列表的开头；如果before为NULL或无效（即，项在链表中不存在），新项将被追加到末尾。

结论

更优雅的删除项解决方案的前提是一个简单的改变：使用间接的list_item **指针来遍历指向列表项的指针。其他一切都由此展开：不需要特殊情况或分支，一个迭代器就足以找到并移除目标项。同样的方法也为项的插入，特别是在现有项之前的插入，提供了一个优雅的解决方案。因此，回到Linus最初的评论：这是好品味吗？难说，但它肯定是对一个众所周知的计算机科学任务的创造性和非常优雅的解决方案。