Common Lisp 中的双链表

Question

我想在 SBCL 中实现一个简单的双向链表，其关键结构如下

(defstruct element
  (value 0 :type fixnum)
  (next nil :type element)
  (prev nil :type element))

问题是，无法实例化第一个元素，因为 next 和 prev 都不能为 nil。它们的类型是元素，所以它们必须是一个实例。

如果去掉类型属性，问题基本上很容易解决。但事实是，这部分程序需要非常快，所以我想给优化器一个机会来充分利用它。

有没有其他方法可以指定成员的类型并使它们为零？或者更好：有没有办法创建一个启动实例，next 和 prev 引用实例本身？

Answer 1

(defstruct element
  (value 0 :type fixnum)
  (next nil :type (or element null))
  (prev nil :type (or element null)))

Answer 2

用 NIL 表示 null 元素没有错，但如果你真的想强制执行该类型，你可以按如下方式进行。

ALLOCATE-INSTANCE generic function (but not INITIALIZE-INSTANCE apparently) is specified to work with instances of STRUCTURE-CLASS.

函数空元素的前向声明

此函数 return 是类型 element 的空值。对于 SBCL，如果您一次编译所有定义（即使用 compile-file）并不是绝对必要的。

(declaim (ftype function null-element))

定义结构

values 的 initform 是对 null-element 的调用，以便在形成新结构时该值满足类型。没有为此结构定义构造函数，这使得手动构建它变得更加困难（并避免命名问题）。

(defstruct (element (:constructor nil))
  (value 0 :type fixnum)
  (next (null-element) :type element)
  (prev (null-element) :type element))

实例化一个元素

这里的代码分配了结构，但没有初始化它。这避免了 sbcl 可能会自动检查其插槽类型的问题。这里，插槽的内容在分配后未定义，但随后它们被设置为适当类型的值（元素本身）。

(defun make-element (value)
  (let ((element (allocate-instance (find-class 'element))))
    (prog1 element
      (setf (element-value element) value
            (element-next  element) element
            (element-prev  element) element))))

使用 class，我会调用 initialize-instance，但我不认为这适用于所有实现。使用 setf 直接设置插槽有效。

在这里，我同意你的问题，并让该元素具有指向自身的链接。

Or better: Is there a way to create a start instance with next and prev referencing the instance itself?

您也可以将字段设置为 (null-element)，但这只是设计选择的问题。

单例空元素值

调用 (null-element) returns 一个表示空元素的标记值。在这里，我在加载时分配一个 element 实例，并在每次调用时分配 return 同一实例。存储在节点中的实际值并不重要。正如 RainerJoswig 所指出的，null 元素可能是一个结构的实例，其中没有这样的值。

(defun null-element ()
  (load-time-value (make-element 0)))

(defun null-element-p (element)
  (eq element (null-element)))

Answer 3

还可以设置层级：

(defstruct element)

(defstruct (null-element (:include element)))

(defstruct (link-element (:include element))
  (value 0                   :type fixnum)
  (next  (make-null-element) :type element)
  (prev  (make-null-element) :type element))

使用它：

* (compile-file "linked-list.lisp")
; compiling file "/Users/joswig/Desktop/linked-list.lisp"
;   (written 08 APR 2021 12:58:56 PM):
; processing (DEFSTRUCT ELEMENT)
; processing (DEFSTRUCT (NULL-ELEMENT #))
; processing (DEFSTRUCT (LINK-ELEMENT #) ...)

; wrote /Users/joswig/Desktop/linked-list.fasl
; compilation finished in 0:00:00.032
#P"/Users/joswig/Desktop/linked-list.fasl"
NIL
NIL
* (load *)
T
* (make-link-element)
#S(LINK-ELEMENT :VALUE 0
                :NEXT #S(NULL-ELEMENT)
                :PREV #S(NULL-ELEMENT))

Answer 4

I want to give the optimizer a chance to make the best out of it.

如果希望双向链表代码尽可能快，就不要nil终止指针。

使用哨兵节点终止链表，有效地使其循环。

也就是说，空链表是一个指向自身的节点：

(defun make-dl-list()
  (let ((do (make-element)))
     (setf (element-next sentinel) dl
           (element-prev sentinel) dl)
      dl))

列表的头部是 (element-next list)。如果该值是列表本身，则列表为空：

 (defun dl-list-empty (dl)
   (eq (element-next dl) dl))

前面插入：

 (defun dl-insert-front (list node)
   (let ((head (element-next list)))
     (setf (elem-next node) head
           (elem-prev node) list
           (elem-prev head) node
           (elem-next list) node)))

正在删除节点：不需要指向列表的指针！

 (defun dl-delete-node (node)
   (let ((next (elem-next node))
         (prev (elem-prev node))
     (setf (elem-next prev) next
           (elem-prev next) prev)))

注意这些操作中的 none 如何执行任何测试；它们只是更新指针的基本代码块。

Common Lisp 中的双链表

Double Linked List in Common Lisp

lisp

initialization

sbcl

common-lisp

data-structures

函数空元素的前向声明

定义结构

实例化一个元素

单例空元素值