Double Linked List in Common Lisp

Question

I want to implement a simple double linked list in SBCL with the following key structure

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

The problem is, that it's impossible to instantiate the first element, because neither next nor prev may be nil. Their type is element and so they have to be an instance.

The problem is basically easy to fix if I remove the type property. But the fact is, that this part of the programm needs to be really fast, so I want to give the optimizer a chance to make the best out of it.

Is there any other way to specify the type of the member AND to make them nil? Or better: Is there a way to create a start instance with next and prev referencing the instance itself?

Answer 1

One can also set up a hierarchy:

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

Using it:

* (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 2

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