linked-list-good-taste

链表、指针技巧和良好的品味

在 2016 年的 [TED 采访][ted] (14:10) 中,Linus Torvalds 讲述了他所认为的编码中的"良好风格"。作为一个例子,他介绍了单链表中项删除的两种实现(如下所示)。为了从列表中删除第一个项,其中一种实现需要特殊情况,另一种则不需要。Linus 显然更喜欢后者。

他所提供的代码片段是 C 语言的伪代码,足够简单以便理解。然而,正如 Linus 在注释中提到的,这些代码片段缺乏概念性解释,而且并不明显地表明更优雅的解决方案是如何工作的。接下来的两节将详细介绍技术方法,并展示间接地址方式是如何实现的,以及为什么如此简洁。最后一节将将解决方案从项删除扩展到插入。

数字是任意选择的整数值,箭头表示指针。head 是类型为 list_item* 的指针,每个方框都是 list_item 结构的实例,每个结构都有一个成员变量(在代码中称为 next),其类型为 list_item。