Linus Torvalds对链表的良好品味论点解释

在2016年TED的一次采访中（14:10），Linus Torvalds谈到了他认为编码方面的良好品味。作为一个示例，他提出了单链接列表中项目删除的两种实现方式（如下所示）。为了从列表中删除第一项，其中一种实现需要特殊情况，而另一种则不需要。显然，Linus更喜欢后者。

[...]我不想让您理解为什么它没有if语句。但是我想让您理解有时您会以不同的方式看到问题并重写它，因此情况消失了，变成了正常情况，这就是很好的代码。 [...]-L. Torvalds

他呈现的代码段是C样式的伪代码，并且足够简单以至于可以遵循。但是，正如Linus在评论中提到的那样，这些代码片段缺乏概念上的解释，而且尚无法立即证明更优雅的解决方案实际上是如何工作的。

接下来的两节将详细介绍技术方法，并说明间接寻址方法如此整洁的方式以及原因。最后一部分将解决方案从项目删除扩展到插入。

整数单链表的基本数据结构如图1所示。

数字是任意选择的整数值，箭头表示指针。 head是IntListItem *类型的指针，每个框都是IntListItem结构的实例，每个都有一个IntListItem *类型的成员变量（在代码中称为next），该成员变量指向下一个项目。

struct IntListItem {int value; struct IntListItem * next;}; typedef struct IntListItem IntListItem; struct IntList {IntListItem * head;}​​; typedef struct IntList IntList;

/ *教科书版本* / void remove_cs101（IntList * l，IntListItem * target）; / *一个更优雅的解决方案* / void remove_elegant（IntList * l，IntListItem * target）;

有了这个，让我们看一下remove_cs101（）和remove_elegant（）的实现。这些示例的代码与Linus的伪代码相同。示例，并进行编译和运行。

void remove_cs101（IntList * l，IntListItem * target）{IntListItem * cur = l->头* prev = NULL; while（cur！= target）{prev = cur; cur = cur-＆gt;下一个; } if（prev）{prev-＆gt;下一个= cur-＆gt;下一个; }其他{l-＆gt;头=当前->下一个; }}

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

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

void remove_elegant（IntList * l，IntListItem * target）{IntListItem ** p =＆l-＆gt;头;而（（* p）！=目标）{p =＆amp;（* p）-＆gt;下一个; } * p = target-＆gt;下一个;}

该代码使用一个间接指针p，该指针从头的地址开始保存指向列表项的指针的地址。在每次迭代中，该指针都会前进以保存指向下一个列表项的指针的地址，即当前IntListItem中下一个元素的地址。当指向列表项（* p）的指针等于target时，我们退出searchloop并将其从列表中删除。

它使我们能够以使指针成为数据结构不可或缺的一部分的方式来解释链表。这样就无需特殊情况下即可删除第一个项目。

它还允许我们评估while循环的条件，而不必放开指向目标的指针。这使我们可以修改指向目标的指针，并使用单迭代器来代替prev和cur。

标准模型将链接列表解释为IntListIteminstances的序列。序列的开头可以通过头指针访问。

这导致图2中所示的分块。头指针仅被视为访问列表开头的句柄。类型IntListItem *的prev和curare指针，始终指向一个项目或NULL。

优雅的实现使用间接寻址方案，该方案对数据结构产生了不同的看法：

在这里，p的类型为IntListItem **，并保存指向当前列表项的指针的地址。当我们前进指针时，我们将前进到下一个列表项的指针的地址。

->下一个：再次取消引用该指针，然后选择保存下一个列表项地址的字段

这对应于对数据结构的解释，其中列表是一个指向IntListItems的指针序列（请参见图3）。

该特定解释的另一个好处是，它在整个遍历过程中都支持编辑当前项目的前任的下一个指针。

通过p持有指向列表项的指针的地址，搜索循环中的比较变为

如果（* p）等于目标，则搜索循环将退出，并且一旦完成，由于我们保留了它的地址p，我们仍然可以修改（* p）。因此，尽管重复循环直到我们达到目标，我们仍然维护一个句柄（下一个字段的地址或头指针），该句柄可用于直接修改指向该项目的指针。

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

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

该函数将使用指向列表l的指针，指向该列表中anitem的指针以及指向该函数将在其之前插入的新列表项的指针。

静态内联IntListItem ** find_indirect（IntList * l，IntListItem * target）{IntListItem ** p =＆amp; l-＆gt;头; while（（（* p）＆amp;＆amp;（* p）！= target）{p =＆amp;（* p）-＆gt;下一个; } return p;}

void insert_before（IntList * l，IntListItem *之前，IntListItem * item）{IntListItem ** p = find_indirect（l，before）; * p =项目；项目-＆gt;下一个=之前；}

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

删除项目的更优雅解决方案的前提是一个简单的更改：使用间接IntListItem **指针迭代指针到列表项。所有其他一切都从那里流动：不需要特殊的情况或分支，并且仅需要一个迭代器就可以找到和删除目标项目。同样，该方法还为一般的项目插入和在现有项目之前插入提供了优雅的解决方案特别是项目。

因此，回到Linus＆＃39;初步点评：味道好吗？很难说，但是对于著名的CS任务，它无疑是一种不同的，创造性的且非常优雅的解决方案。