通过 Lisp 语言理解编程算法：链表篇（上）

本文是本系列文章的第六篇，Lisp（历史上曾拼写为 LISP）是具有悠久历史的计算机编程语言家族，有独特和完全括号的前缀符号表示法。本文旨在通过 Lisp 编程语言理解链表的基本概念，由于原文篇幅较长，InfoQ 通过上下篇的形式进行翻译发布。

在许多方面，链接数据结构与我们在上一章中以数组为例在某种程度上探讨过的连续数据结构相反。就复杂性而言，它们不适用于那些需要重复修改的地方（首先是随机存取），但在需要重复修改的场景中会占上风。一般来说，它们更加灵活，因此允许程序员表示几乎任何一种数据结构，尽管需要这种灵活性的结构可能不太常见。通常，它们是专门的树或图。

基本的链接数据结构是单向链表（singly-linked list）。

就像数组一样，Lisp 的列表可以用常量的文字语法创建，也可以通过调用一个函数 make-list 来创建一个由 nil 元素填充的特定大小的列表。此外，还有一个方面的 list 使用程序，用于创建具有指定内容的列表（类似于 vec）。

CL-USER> '("hello" world 111)
("hello" WORLD 111)
CL-USER> (make-list 3)
(NIL NIL NIL)
CL-USER> (list "hello" 'world 111)
("hello" WORLD 111)

空列表表示为 ()，有趣的是，在 Lisp 中，它也是逻辑假（nil) 的同义词。这个属性经常被使用，我们将会有机会看到它的使用。

如果我们要引入自己的列表，这可能是非常常见的场景之一，以防内置列表的功能不适合我们的需求，我们需要定义结构“节点”，并且我们的列表将被构建为这样的节点链。我们可能希望存储列表头部（head），可能还有尾部（tail），以及其他属性，如大小。总而言之，它加你看起来像下面这样的：

(defstruct list-cell
  data
  next)

(defstruct our-own-list
  (head nil :type (or list-cell null))
  (tail nil :type (or list-cell null)))

CL-USER> (let ((tail (make-list-cell :data "world")))
           (make-our-own-list
            :head (make-list-cell
                   :data "hello"
                   :next tail)
            :tail tail))
#S(OUR-OWN-LIST
   :HEAD #S(LIST-CELL
            :DATA "hello"
            :NEXT #S(LIST-CELL :DATA "world" :NEXT NIL))
   :TAIL #S(LIST-CELL :DATA "world" :NEXT NIL))

列表作为序列

除了数组之外，列表是实现序列抽象数据类型的另一种基本数据结构。让我们考虑一下链表的基本序列操作的复杂性：

• 所谓的随机访问，即通过随机元素的索引进行访问，需要 O(n) 的时间，因为我们必须遍历所有前面的元素，才能达到所需的元素（平均需要 n/2 次操作）。
• 然而，一旦我们到达某个元素，删除它或者在它取 O(1) 之后插入某个元素。
• 子序列也需要 O(n) 的时间。

在基本情况下，获取列表的长度也是 O(n)，即需要完整的列表遍历。不过，可以将列表长度存储为一个单独的槽（slot），动态跟踪每个更改，这意味着 O(1) 的复杂性。然而，Lisp 实现了列表的最简单的变体，不需要对大小的跟踪。这是一个微小但很重要的决策的例子，现实编程中充满了这个决策。

在这种情况下，为什么这样的解决方案是正确的？为每个列表添加大小计数器，肯定会使这种常见的 length 操作更加有效，但这样做的成本包括：增加了所有列表的占用存储空间，需要在所有列表修改操作中更新大小，以及可能需要更复杂的 cons（构造列表）单元实现 [1]。这些考虑使得列表的情况几乎与数组相反，对于数组来说，大小跟踪是非常合理的，因为它们更改频率要低得多，而且不跟踪长度在历史上被证明是一个糟糕的安全决策。

所以，我们该选择哪一边呢？默认的方法是选择不完全排除替代策略的解决方案。如果我们选在一个简单的 cons-cell sans size（正如 Lisp 作者所做的）, 我们总是能够在它的上面添加带有 size 字段的 “智能” 列表数据结构。然而，从内置列表中剥离 size 字段是不可能的。类似的推理也适用于其他问题，例如：为什么 Lisp 中的列表不是双向链接的。此外，这有助于避免安全隐患，因为列表不用做数据交换缓冲区，而问题就在于此。

为了演示，让我们将 size 字段添加到 our-own-list （同时，考虑需要更新它的所有函数）：

(defstruct our-own-list
  (head nil :type (or list-cell nil))
  (tail nil :type (or list-cell nil))
  (size 0 :type (integer 0)))

考虑到在 Lisp 中，获取列表长度是一项昂贵的操作，在需要对 size 字段发出多个请求的程序中，常见的模式是在算法开始时将其值存储在某个变量中，然后使用该缓存值，必要时进行更新。

正如我们看到的，列表在随机访问场景中，效率非常低。然而，许多序列并不需要随机访问，只需使用顺序访问即可满足特定用例的所有要求。这也是为什么它们被称为序列的原因之一。如果我们考虑索引 0 处的列表操作的特殊情况，它们显然是高效的：访问和添加 / 删除都是 O(1)。此外，如果算法需要顺序扫描，列表遍历也相当高效，尽管不如数组遍历好，因为它仍然需要跳过内存指针。有许多基于顺序扫描的序列操作。最常见的是 map，我们在上一章中已经分析过了。它是循环的函数式编程的替代，是一种更为高级的操作，因此对于常见的情况来说更容易理解，尽管通用性较差。

map 是一个处理不同类型的内置序列的函数。它将目标序列类型作为第一个参数（如果提供了 nil，则不会创建结果序列，因此仅用于副作用）。下面是一个涉及列表和向量的多态示例：

CL-USER> (map 'vector '+
              '(1 2 3 4 5)
              #(1 2 3))
#(2 4 6)

map 将作为第二个参数（此处为加法）提供的函数顺序应用于作为其他参数提供的序列的每个元素，直到其中一个参数结束，并将结果记录在输出序列中。map 如果只使用结果序列的第一个参数的类型，它将会更直观，也就是说，是一个“做我想做的” dwim-map，而一个单独的具有结果类型选择的高级变体可能已经在后台使用。不幸的是，当前的标准方案不是为了改变，但我们可以定义自己的包装器函数：

(defun dwim-map (fn seq &rest seqs)
  "A thin wrapper over MAP that uses the first SEQ's type for the result."
  (apply 'map (type-of seq) fn seqs))

Lisp 中的map 在历史上用于列表。因此，在该语言的早期版本中，还有一些特定于列表的 map 变体，这些变体在通用 map 出现之前就存在了，至今仍在广泛使用。其中包括 mapcar、mapc 和 mapcan（在 RUTILS 中由更安全的 flat-map 代替）。现在，让我们看几个使用映射的例子。假设我们想从一个数字列表中提取奇数。使用 mapcar 作为特定于列表的 map，我们可以尝试用匿名函数来调用它，该函数测试它的参数是否“古怪”，并在这种情况下保留它们：

CL-USER> (mapcar (lambda (x) (when (oddp x) x))
                 (range 1 10))
(1 NIL 3 NIL 5 NIL 7 NIL 9)

然而，问题是，非奇数在结果列表中仍然保留了它们的位置，尽管它并没有被它们填充。只保留满足（或不满足）某些标准的结果，然后丢弃其他结果，这是一种非常常见的模式，称为“过滤”。对于这样的场景，有一组 Lisp 函数：remove、remove-if 和 remove-if-not，以及 RUTILS 对它们的补充：keep-if 和 keep-if-not。我们可以在图片中添加 remove，从而达到预期的效果：

CL-USER> (remove nil (mapcar (lambda (x) (when (oddp x) x))
                             (range 1 10)))
(1 3 5 7 9)

更优雅的解决方案是使用 remove-if(-not) 或 keep-if(-not) 变量。remove-if-not 是这些函数中最常用的。它接受一个谓词和一个序列，并返回仅包含满足谓词的元素的相同类型的序列：

CL-USER> (remove-if-not 'oddp (range 1 10))
(1 3 5 7 9)

使用这种高级映射函数非常方便，这就是为什么有许多其他的 -if(-not) 操作，比如 find(-if(-not))、member(-if(-not))等。

mapcar 或任何其他列表映射函数的实现，包括你自己的特定于任务的变体，都遵循同样的模式，即遍历列表，将结果累加到另一个列表中，最后将其反转：

(defun simple-mapcar (fn list)
  (let ((rez ()))
    (dolist (item list)
      (:= rez (cons (call fn item) rez)))
    (reverse rez)))

函数 cons 用于将在列表的头部添加一个项。它创建一个新的列表头部，该列表头部指向以前的列表作为其尾部。

从复杂性的角度来看，如果我们将这种迭代与在数组上的循环进行比较，我们就会发现，它也是一个线性遍历，需要的操作数是数组的两倍，因为我们需要再次完整地遍历结果，最终才能将其反转。然而，它的优势是更高的通用性：如果我们不知道结果序列的大小（例如，在 remove-if-not 的情况下），我们不必改变这个方案中的任何内容，只需添加一个过滤器行 ((when(oddp item)…) 即可，而对于数组，我们要么使用动态数组（这将需要不断调整大小，因此至少有相同的双倍操作数），要么预先分配完整大小的结果序列，然后缩小它以适应实际累积的元素数量，这在处理大型数组时可能会出现问题。

列表作为函数数据结构

数组和链表之间的区别，在许多方面反映了命令式编程范式和函数式编程范式之间的区别。在命令式方法中，或者在这种情况下，过程式方法中，程序是由低级块（条件、循环和序列）构建的，这些低级块以抽象级别和模块化能力为代价进行最精细和高效的实现。它还大量利用原位修改和手动资源管理，以将开销保持在最低限度。对于这种编程方式而言，数组是最合适的数据结构。相反，函数式编程努力提高抽象级别，这可能以牺牲效率为代价（仅在必要时，理想情况下，仅针对非关键部分）。函数式程序是通过结合在更高级的数据结构上运行的引用同名计算过程（又称为 “纯函数”）来构建的，这些数据结构（持久的数据结构或具有特殊的访问语义，例如事务性的）管理起来成本也更高，但提供了额外的好处。

单向链表是函数式数据结构的一个简单例子。函数或持久性数据结构是不允许原位修改的。话句话说，要更改结构的内容，应该创建具有所需更改的新副本。链接数据结构的灵活性使它们适合用作函数式结构。我们已经看到了 cons 操作，它是非破坏性（即函数式）修改的最早示例之一。此操作将元素添加到列表的头部，当我们处理单向链表时，不必更新原始列表：在它的前面添加一个新的 cons 单元，它的 next 指针引用成为原始列表，这个列表成为新的尾部。这样，我们既可以保留指向原始头部的指针，又可以添加新的头部。这种方法是大多数函数式数据结构的基础：函数树，例如，添加一个新的头部，和从头部到新添加的元素的新路由，沿途添加新节点，都遵循同样的原则。

不过，有趣的是，列表同样可以以破坏性和非破坏性的方式使用。Lisp 中，既有执行列表修改的低级函数，也有执行列表修改的高级函数，许多算法中的用例证明了它们的存在。纯函数式列表使许多有效的列表算法变得毫无用处。高级列表修改功能是 nconc。它将两个列表连接在一起，并在此过程中，更新第一个列表的最后一个 cons 单元的 next 指针：

CL-USER> (let ((l1 (list 1 2 3))
               (l2 (list 4 5 6)))
           (nconc l1 l2)  ; note no assignment to l1
           l1)            ; but it is still changed
(1 2 3 4 5 6)

这个操作有一个函数变体 append，一般来说，使用 nconc 被认为是不合适的，原因有二：

• 不必要的修改风险
• 有趣的是，ncons 的实现实际上并不要求比 append 的实现更高效。

所以，忘记 nconc，append 所有列表！

使用 append，我们需要修改前一段代码，否则新创建的列表将立即被垃圾回收：

CL-USER> (let ((l1 (list 1 2 3))
               (l2 (list 4 5 6)))
           (:= l1 (append l1 l2))
           l1)
(1 2 3 4 5 6)

低级列表修改操作是 rplaca 和 rplacd。它们可以与列表特定的访问器 nth 和 nthcdr 组合，这两个访问器分别提供对列表元素和尾部的索引访问。例如，下面是如何在列表中间添加元素的示例代码段：

CL-USER> (let ((l1 (list 1 2 3)))
           (rplacd (nthcdr 0 l1)
                   (cons 4 (nthcdr 1 l1)))
           l1)
(1 4 2 3)

只是为了重新迭代，虽然函数式列表操作是默认选择，但为了高效地实现某些算法，你需要求助于难看的、破坏性的算法。

列表的不同类型

到目前为止，我们已经看到了最基本的链表变体：单向链表。它有很多限制：例如，不可能从头到尾进行遍历。然而，有许多算法需要从两个方面访问列表，或者用它做其他事情，这些对于单向链表来说效率很低，甚至不可能，因此存在其他更高级的列表变体。

但首先，让我们考虑对常规单向链表进行的有趣的调整：循环列表。它可以通过最后一个 cons 单元指向第一个单元，可以在普通的 cons 单元来创建。它看起来像是一个有问题的数据结构，但是如果我们保留一个指向任何节点的指针，并在第二次遇到这个节点时停止迭代，那么遍历它时无限循环的所有潜在问题都会得到解决。这样的结构有什么用？嗯，不是很多，但有一个突出的用处：循环缓冲区。环形或循环缓冲区是一种结构，它可以容保存预定数量的项，每个项都被添加到当前项目的下一个槽中。这样，当缓冲区被完全填满时，它将回绕到第一个元素，这个元素将在下一次修改时被覆盖。通过我们的缓冲区填充算法，要覆盖的元素是当前项集最早写入的元素。使用循环立案别是实现这种缓冲区的最简单方法之一。另一种方法是使用一定大小的数组，通过将索引递增到数组中，将指针移动到下一项。显然，当索引达到数组大小时，应该将其重置为零。

更高级的列表变体是双向链表，其中所有元素都有 next 和 previous 指针。下面的定义使用继承，通过一个指向前一个元素的指针扩展了原始 list-cell。由于结构具有基本的面向对象功能，所以它也将与 our-own-list 的当前定义一起工作，并允许它作为一个双向链表运行。

(defstruct (list-cell2 (:include list-cell))
  prev)

然而，我们仍然没有展示在 our-own-list 中添加和删除元素的高级操作的实现。显然，对于单向链表和双向链表，它们会有所不同，这种区别要求我们区分双向链表类型。反过来，这将要求调用一种相当沉重的 OO（面向对象）机制，这已经超出了本书主题的范畴。现在，让我们来看看双向链表的基本列表添加函数：

(defun our-cons2 (data list)
  (when (null list) (:= list (make-our-own-list)))
  (let ((new-head (make-list-cell2
                   :data data 
                   :next (when list @list.head))))
    (:= @list.head.prev new-head)
    (make-our-own-list
     :head new-head
     :tail @list.tail
     :size (1+ @list.size))))

首先要注意的是，使用了 RUTILS 的 @ 语法糖，实现了槽值访问（slot-value access）的主流点符号（即 @list.head.prev，指的是所提供的假定 our-own-list 类型的 list 结构的 head 字段的 prev 字段，在更经典的 Lispy 中，尽管有些繁琐，但其变体可能看起来像下面这样： (our-cons2-prev (our-own-list-head list)) 或 (slot-value (slot-value list 'head) 'prev)[2]）。

这里更重要的是，与单向链表不同，这个函数需要对原始列表的头部元素进行原位修改：设置它的 prev 指针。立即使双向链表成为非持久性的。

最后，第一行是防止试图访问空列表（这将导致非常令人担心的错误，尤其是在 Java 语言中的空指针异常类的错误）。

乍一看，双向链表似乎比单向链表更有用。但它们也有较高的开销，因此，在实践中，它们只是偶尔使用。我们可以在本书看到一些用例。其中一个将在下章中介绍：双端队列（double-ended queue）

除了双向链表之外，还有关联列表（association lists），是键值数据结构的变体。在 Common Lisp 的代码中至少能找到 3 种类型，我们将在关于键值结构的章节中简要讨论它们。最后，跳跃列表（skip list）是基于单向链表的概率数据结构，它允许更快的搜索，我们还将在关于概率结构的单独章节中讨论。至于其他更深奥的列表变体，如自组织链表（self-organized list）和异或链表（XOR-list），也可以在文献中找到，但在实践中非常少见。

作者介绍：

Vsevolod Dyomkin，Lisp 程序员，居住在乌克兰基辅。精通乌克兰语、俄语和英语。目前正在撰写关于 Lisp 的书籍 Programming Algorithms in Lisp，该书将使用 CC BY-NC-ND 许可（创作公用许可协议），供公众免费阅读。

原文链接：

LISP, THE UNIVERSE AND EVERYTHING

本系列文章最初发布于 Vesvolod Dyomkin 的 Blogger 博客，经原作者授权，由 InfoQ 中文站翻译并分享。