12.6 示例：双向链表 (Example: Doubly-Linked Lists)

普通的 Lisp 列表是单向链表，这意味着其指针指向一个方向：我们可以获取下一个元素，但不能获取前一个。在双向链表中，指针指向两个方向，我们获取前一个元素和下一个元素都很容易。这一节将介绍如何创建和操作双向链表。

图 12.10 展示了如何用结构来实现双向链表。将 cons 看成一种结构，它有两个字段：指向数据的 car 和指向下一个元素的 cdr 。要实现一个双向链表，我们需要第三个字段，用来指向前一个元素。图 12.10 中的 defstruct 定义了一个含有三个字段的对象 dl (用于“双向链接”)，我们将用它来构造双向链表。dl 的 data 字段对应一个 cons 的 car，next 字段对应 cdr 。 prev 字段就类似一个 cdr ，指向另外一个方向。(图 12.11 是一个含有三个元素的双向链表。) 空的双向链表为 nil ，就像空的列表一样。

  1. (defstruct (dl (:print-function print-dl))
  2.   prev data next)
  4. (defun print-dl (dl stream depth)
  5.   (declare (ignore depth))
  6.   (format stream "#<DL ~A>" (dl->list dl)))
  8. (defun dl->list (lst)
  9.   (if (dl-p lst)
  10.       (cons (dl-data lst) (dl->list (dl-next lst)))
  11.       lst))
  13. (defun dl-insert (x lst)
  14.   (let ((elt (make-dl :data x :next lst)))
  15.     (when (dl-p lst)
  16.       (if (dl-prev lst)
  17.           (setf (dl-next (dl-prev lst)) elt
  18.                 (dl-prev elt) (dl-prev lst)))
  19.       (setf (dl-prev lst) elt))
  20.     elt))
  22. (defun dl-list (&rest args)
  23.   (reduce #'dl-insert args
  24.           :from-end t :initial-value nil))
  26. (defun dl-remove (lst)
  27.   (if (dl-prev lst)
  28.       (setf (dl-next (dl-prev lst)) (dl-next lst)))
  29.   (if (dl-next lst)
  30.       (setf (dl-prev (dl-next lst)) (dl-prev lst)))
  31.   (dl-next lst))

图 12.10: 构造双向链表

../_images/Figure-12.11.png

图 12.11: 一个双向链表。

为了便于操作，我们为双向链表定义了一些实现类似 car ， cdr ， consp 功能的函数：dl-data ， dl-next 和 dl-p 。 dl->list 是 dl 的打印函数(print-function)，其返回一个包含 dl 所有元素的普通列表。

函数 dl-insert 就像针对双向链表的 cons 操作。至少，它就像 cons 一样，是一个基本构建函数。与 cons 不同的是，它实际上要修改作为第二个参数传递给它的双向链表。在这种情况下，这是自然而然的。我们 cons 内容到普通列表前面，不需要对普通列表的 rest (译者注： rest 即 cdr 的另一种表示方法，这里的 rest 是对通过 cons 构建后列表来说的，即修改之前的列表) 做任何修改。但是要在双向链表的前面插入元素，我们不得不修改列表的 rest (这里的 rest 即指没修改之前的双向链表) 的 prev 字段来指向这个新元素。

几个普通列表可以共享同一个尾端。因为双向链表的尾端不得不指向它的前一个元素，所以不可能存在两个双向链表共享同一个尾端。如果 dl-insert 不具有破坏性，那么它不得不复制其第二个参数。

单向链表(普通列表)和双向链表另一个有趣的区别是，如何持有它们。我们使用普通列表的首端，来表示单向链表，如果将列表赋值给一个变量，变量可以通过保存指向列表第一个 cons 的指针来持有列表。但是双向链表是双向指向的，我们可以用任何一个点来持有双向链表。 dl-insert 另一个不同于 cons 的地方在于 dl-insert 可以在双向链表的任何位置插入新元素，而 cons 只能在列表的首端插入。

函数 dl-list 是对于 dl 的类似 list 的功能。它接受任意多个参数，它会返回一个包含以这些参数作为元素的 dl ：

  1. > (dl-list 'a 'b 'c)
  2. #<DL (A B C)>

它使用了 reduce 函数 (并设置其 from-end 参数为 true，initial-value 为 nil)，其功能等价于

  1. (dl-insert 'a (dl-insert 'b (dl-insert 'c nil)) )

如果将 dl-list 定义中的 #'dl-insert 换成 #'cons，它就相当于 list 函数了。下面是 dl-list 的一些常见用法：

  1. > (setf dl (dl-list 'a 'b))
  2. #<DL (A B)>
  3. > (setf dl (dl-insert 'c dl))
  4. #<DL (C A B)>
  5. > (dl-insert 'r (dl-next dl))
  6. #<DL (R A B)>
  7. > dl
  8. #<DL (C R A B)>

最后，dl-remove 的作用是从双向链表中移除一个元素。同 dl-insert 一样，它也是具有破坏性的。