Greetings friends!

I am reading through SCIP and using Elixir to help me work through the material (to better understand both the material itself and how Elixir works). Livebook is a great tool for such work!

Anyways, I been thinking through linked lists and would be very grateful and appreciative for any feedback/comments/corrections on the below.

In Elixir a list is really a linked list. Ok, sounds simple enough, let’s to test my understanding:

iex> [1, 2] == [1, [2]]
false

Huh? Isn’t a linked list a list where the next element is a list?

Ah, I think I see my mistake. I need to think of linked lists in terms of their underlying pair structures.

A linked list is a sequence of pairs: a data element and a link to the next node. Harkening back to Scheme, the car is the data element and the cdr is the link to the next node. (hd and tl in Elixir).

We can capture these concepts in Elixir using the | cons operator:

iex> [1, 2] == [1 | [2 | []]]
true

Wonderful!

I am still curious about that first example though…what would [1, [2]] actually look like in terms of the pair structure?

iex> [1, [2]] == [1 | [[2 | []] | []]]
true

Ah, it appears that my mistake was to think of the second element [2] as “the next node”, but the underlying structure is very different: this is itself a list that is the data element of the next pair. In this case it is a nested list within the first list and not, as I oversimplified, “the next node”.

Let’s use some stunning ASCII art to illustrate the differences:

----------------
    [1, 2]

      *
     / \
    1   *
       / \
      2  []
----------------
    [1, [2]]

      *
     / \
    1   *
       / \
      *  []
     / \
    2  []
----------------

Those are very different data structures!

Thoughts? Insights? Corrections? Thanks!