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?

Ogata

Answer 1

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

Lorenzetti

Answer 2

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

Kostman

Answer 3

There is nothing wrong with having NIL represent null elements, but in case you really want to enforce the type, you can do it as follows.

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

Forward declaration of function null-element

This function returns the null value for type element. With SBCL it is not strictly necessary if you compile all definitions at once (i.e. with compile-file).

(declaim (ftype function null-element))

Define struct

The initform for values is a call to null-element, so that the value satisfies the type when a new struct is formed. No constructor is defined for this struct to make it harder to build it manually (and to avoid naming problems).

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

Instantiate an element

Here the code allocates the structure, but does not initialize it. This avoids the problem you may have with sbcl where it automatically checks the type of its slots. Here, the content of the slots is undefined after allocation, but then they are set to values of the appropriate type (the element itself).

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

Using a class, I would have called initialize-instance instead but I don't think this is expected to work on all implementations. Using setf to directly set the slots works.

Here I am going along with your question and have the element have links to itself.

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

You could also let the fields be (null-element), but this is only a matter of design choice.

Singleton null-element value

The call (null-element) returns a sentinel value representing the null element. Here I allocate one instance of element at load-time and return the same instance at each invocation. The actual value stored in the node is not important. As pointed out by RainerJoswig, the null element could be an instance of a struct where there is no such value.

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

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

Archipenko

Answer 4

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

If you want the doubly linked list code to be as fast as possible, do not have nil terminating pointers.

Use a sentinel node to terminate the linked list, effectively making it circular.

So that is to say, the empty list is a node which points to itself:

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

The head of the list is (element-next list). If that value is the list itself, the list is empty:

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

Inserting at the front:

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

Deleting a node: no pointer to list needed!

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

Notice how none of these operations perform any tests; they are just basic blocks of code updating pointers.

Paryavi

In SBCL (make-element) signals a TYPE-ERROR because NIL is not the right type, that's why this is a problem. I tried with a locally block around defstruct to lower the safety level to 0; it does break the environment if the slots are not set right away to a correct value, but if next and prev are set, then it works too – Archipenko