data-structures - Common Lisp 中的双链表

Question

我想在 SBCL 中实现一个简单的双链表，具有以下关键结构

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

问题是，实例化第一个元素是不可能的，因为 next 和 prev 都不可能是 nil。它们的类型是元素，因此它们必须是实例。
如果我删除 type 属性，这个问题基本上很容易解决。但事实是，这部分程序需要非常快，所以我想给优化器一个充分利用它的机会。
有没有其他方法可以指定成员的类型并使它们为零？或者更好:有没有办法用 next 和 prev 引用实例本身来创建一个启动实例？

Answer 1

还可以设置层次结构:

(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))