Data structures in functional programming languages:

Ain't no law that says you can't use arrays.

LISP does offer a built-in array data structure...but it's not often used.

What is an array anyway? (Definitions vary.)

Array:  a fixed number of like items stored in contiguous memory.
Meaning:  if I have 253 objects in my array, I always have 253; I can't grow or shrink, and the objects are all of the same type and they take
up exactly the same amount of space as each other.

What is the HUGE advantage to such a strictly defined data type?

If my array in memory begins at position A, and each object in the array takes up exactly sz bytes.  The position of A[i] is found A+sz*i;

I do not need a lookup table.  I do need "indirection."  I can jump directly to where I need to be.  It is fast.

Downside of arrays:  fixed size:  inflexible.  (Fixed size means once
an array is allocated you have to deallocate and reallocate to change
the size, meaning you're really making a new array.)
Along with the fixed size is the problem adding or removing from the
interior of the array.  How do you do it?  Do you have move everything up or down to either make a hole or fill a hole?

A lot of C++ educators don't even bother with arrays anymore.  They use "vectors."  (In modern languages, like Swift and Kotlin, even "arrays" aren't really arrays, and you can grow and shrink them, and add stuff in the middle and all of that.)

The exact nature of a "real" array simply can't be done with linked lists.  But you can do something very much like it, and surprisingly efficiently.

Binary trees:  Each node has a pointer to a left tree and a right tree.  Every value in the left tree precedes my value, and every value in the right tree succeeds my value.  This is a very efficient way to store, say, a database, and an awful lot of modern databases are still stored in some variation of this.  If you do it right, search, add, remove, all done in lg n time.

                      SUPER
               EXTRA
           BRAND  GREEN
                    PHONE
                   LEVEL

In a world with only linked lists, trees have to stored as a collection
of linked lists.

In an imperative language, we might say

class Node;
 string Value;
 Node *left, *right;
}

But in LISP, we wouldn't have to declare a class, we would just "remember"
that a node is a list of size 3.  The head is the value, the next is another list representing the left subtree, and the last is another list representing the right subtree.

NIL is an empty list.
(NIL) is a list containing one element.  That one element is NIL.

Internally, linked lists in LISPs are handled with pointers, just as they are in C-like languages.  There's no direct syntax for the pointers,
but they're there.

NIL is just a null pointer.
(NIL) is a pointer to a list whose head contains the NIL list and whose next pointer also points to NIL because it's a one-element list.

(("DOG" NIL NIL))  this is a pointer that points to a linked list.
That linked list's head is "DOG" and it's next points to a node that contains a NIL list and THAT next points a node that contains another NIL list and THAT next pointer is NIL, because this is a three-element list.

-->"DOG"--> |   --> |  -->
            v       v
            NIL     NIL

When you pass a list into a function, you are passing the pointer to the function.  The function is pass-by-value, but since you are passing a pointer,
you can change what the pointer points to.

So if pass (NIL) into a function, my function can look at, say,
(first a) (which is NIL) and change (first a) to something else.
It can't change a directly, since the function is pass-by-value.
But it change the stuff in the list, since it is following a pointer.

This is why (setf (first a) a) gives us grief.  A is originally (NIL)

So changing the NIL to another A means that this list is pointing to itself, which is why it crashes when we try to print it.

So, understanding this, you can build any data structure you want to
using linked lists.  You can make "circular" linked lists if you want to.  You can make "doubly" linked lists.  You can make Binary Trees, you can make Red-Black Trees, you can make anything you want out of linked lists.  And it really won't be any less efficient than in any other language because your pointer structure is still pretty much the same.

C:\Users\apoe\Desktop\cs556-01-24w>"C:\Program Files\clisp-2.49\clisp.exe"  -K full
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.49 (2010-07-07) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010

Type :h and hit Enter for context help.

[1]> (load "tree.lisp")
;; Loading file tree.lisp ...
;; Loaded file tree.lisp
T
[2]> (setf MYTREE (empty-tree))
(NIL)
[3]> MYTREE
(NIL)
[4]> (search-tree MYTREE "SUPER")
NIL
[5]> (search-tree MYTREE "EXTRA")
NIL
[6]> (search-tree MYTREE "GREEN")
NIL
[7]> MYTREE
(NIL)
[8]> (load "tree.lisp")
;; Loading file tree.lisp ...
;; Loaded file tree.lisp
T
[9]> (add-tree MYTREE "SUPER")
"SUPER"
[10]> (search-tree MYTREE "SUPER")
"SUPER"
[11]> (search-tree MYTREE "GREEN")
NIL
[12]> MYTREE
(("SUPER" NIL NIL))
[13]> (add-tree MYTREE "EXTRA")
"EXTRA"
[14]> (add-tree MYTREE "EXTRA")
NIL
[15]> (search-tree MYTREE "EXTRA")
"EXTRA"
[16]> (search-tree MYTREE "SUPER")
"SUPER"
[17]> (search-tree MYTREE "VELMA")
NIL
[18]> MYTREE
(("SUPER" ("EXTRA" NIL NIL) NIL))
[19]> (add-tree MYTREE "GREEN")
"GREEN"
[20]> (add-tree MYTREE "PHONE")
"PHONE"
[21]> (add-tree MYTREE "LEVEL")
"LEVEL"
[22]> (add-tree MYTREE "BRAND")
"BRAND"
[23]> MYTREE
(("SUPER" ("EXTRA" ("BRAND" NIL NIL) ("GREEN" NIL ("PHONE" ("LEVEL" NIL NIL) NIL))) NIL))
[24]> (load "tree.lisp")
;; Loading file tree.lisp ...
;; Loaded file tree.lisp
T
[25]> MYTREE
(("SUPER" ("EXTRA" ("BRAND" NIL NIL) ("GREEN" NIL ("PHONE" ("LEVEL" NIL NIL) NIL))) NIL))
[26]> (print-tree MYTREE)

*** - EVAL: too few arguments given to EQ: (EQ (FIRST (REST NODE)))
The following restarts are available:
ABORT          :R1      Abort main loop
Break 1 [27]> abort
[28]> (load "tree.lisp")
;; Loading file tree.lisp ...
;; Loaded file tree.lisp
T
[29]> (print-tree MYTREE)
"BRAND""EXTRA""GREEN""LEVEL""PHONE""SUPER"
T
[30]> (load "tree.lisp")
;; Loading file tree.lisp ...
;; Loaded file tree.lisp
T
[31]> (print-tree MYTREE)
BRAND
EXTRA
GREEN
LEVEL
PHONE
SUPER
T
[32]> (setf a (list nil))
(NIL)
[33]> A
(NIL)
[34]> (setf (first a) a)

*** - Lisp stack overflow. RESET
[35]> A

*** - Lisp stack overflow. RESET
[36]> A

*** - Lisp stack overflow. RESET
[37]> A

*** - Lisp stack overflow. RESET
[38]> (setf a (list nil))
(NIL)
[39]> (let () (setf (first a) a) T)
T
[40]> A

*** - Lisp stack overflow. RESET
[41]> A

*** - Lisp stack overflow. RESET
[42]> A

*** - Lisp stack overflow. RESET
[43]>