Linked Lists

https://blog.djhaskin.com/blog/common-data-structures-in-common-lisp/

Lets pretend that the only things how to do in Common Lisp is…

`struct S` - macro DEFSTRUCT defstruct defines a structured type, named structured-type

• with named slots specified by the slot-options
• it defines readers for the slots and arranges setf to work properly on such reader funcs
• unless overridden, it defines a predicate named name-p
  • which defines a constructor for function named make-constructor-name
    • and defines a copier function named copy-constructor-name

args and vals conc-name—a string designator constructor-arglist—a boa lamdda list constructor-name—a symbol copier-name—a symbol included-structure-name—an already defined struct name inital-offset—a non-negative integer predicate-name—a symbol printer-name—a function name or lambda expr slot-name—a symbol slot-initform—a form slot-read-only-p—a generalized boolean structure-name—a symbol type—one of the type specifiers list, vector, or vector size, or some other type specifier defined by the implementation to be appropriate documentation—a string; not evaluated

`simple-array S` - type SIMPLE-ARRAY

• the type of an array that is not displaced to another array

  • has not fill pointer, and is not expressly adjustable is a subtype of type simple-array

    simple-array exists to allow the implementation to use a specialized representation

    • and to allow the user to declare that certain values will always be simple arrays

Linked Lists

LinkedLists have boxes that point to other boxes

———- ———- ———-

———- ———- ———-

• a linked list is comprised of a series of nodes with 2 fields in them

  • one to point to data
    • one to point to more list

  ——+ ——+ ——+

  O	O	——->	O	O	…——->	O	X

  ——+ ——+ ——+

  v v v (data) (data) (data)

• here we notice that its not the list thats special

  • but the pointer-pairs

    O	O

    v (data)

pair

——+

——+

v v (data)(data) tree

——+

----+

——— ———

—v— —v—

----+ ----+

— — — —

—v— —v— —v— —v—

----+ ----+ ----+ ----+

v v v v (data) (data) (data) (data)

Implementation

;;; Define a node struct
(defstruct cons ;; theres already a const in Common Lisp!
  car
  cdr)

;; new list
(defparameter my-list-nil)

;; add to a list
(setf my-list (make-pair :car 1 :cdr my-list))
(setf my-list (make-pair :car 2 :cdr my-list))
(setf my-list (make-pair :car 3 :cdr my-list))
(setf my-list (make-pair :car 4 :cdr my-list))

;; traverse a list
(loop for node = my-list then (pair-cdr node)
      while node
      do (format t "~A " (pair-car node)))

;; remove the front item from a list
(setf my-list (pair-cdr my-list))

;; remove a specific item (2) from a list
(if (eql (pair-car my-list) 2)
    (setf my-list (pair-cdr my-list))
    (loop for node = my-list then (pair-cdr node)
          while (pair-cdr node)
          until (eql (pair-car (pair-cdr node)) 2)
          finally (setf (pair-cdr node) (pair-cdr (pair-cdr node)))))