Singly linked lists in Scheme (Lisp)

linked_list_1.scm

; One may form pairs in Scheme with (cons ITEM1 ITEM2)
; For example, (cons 1 2) represents the pair 1 and 2
; Let's define a the pair of 1 and 2 as one-and-two:

(define one-and-two (cons 1 2)) 

; Now one can invoke the pair with one-and-two
;1 ]=> one-and-two
; Value 11: (1 . 2)

; car and cdr are used to invoke elements in the pair,
;respectively for first and second

;1 ]=> (car one-and-two)
;Value: 1

;1 ]=> (cdr one-and-two)
;Value: 2

; Now let's make a linear, singly-linked list that
; represents the numbers one through four

(define one-through-four (cons 1 
                         (cons 2 
                         (cons 3 
                         (cons 4 ()
                         )))))

; NOTE: The last node is (cons 4 ())
; this represents a pair of 4 and a null value.
; () is a null value in Scheme.

; To better understand how this makes up a linked list,
; let's car and cdr it

;1 ]=> (car one-through-four)
;Value: 1

;1 ]=> (cdr one-through-four)
;Value 12: (2 3 4)
; This returns (2 3 4) which is actually:
(cons 2 (cons 3 (cons 4 ())))

; Another simple graphical way to look at one-through-four:
; 1,L->2,L->3,L->4,()
; Each comma-separated group represents a node.

; In each node there is datum (the integer)
; and a link (L->) pointing to a node

; We can expand this linked-list in two ways, first:
(cons 5 one-through-four)
(5 1 2 3 4)
; Null is still the last value
;the last pair in the list is 4 and ()

; Secondly: 
; [Doing the following changes the fundamental structure.
; Do you see why?]
(cons one-through-four 5)
(1 2 3 4 5)

; We've added another datum, 5,
; but it has no position for a potential outgoing link. 

;Think about what:
(cdr (cons one-through-four 5))
; would bring up, as opposed to:
(car (cons 5 one-through-four)) ; and
(cdr (cons 5 one-through-four))

; You may use append to extend lists,
; it technically concatenates lists,
; so you can preserve the structure.