Seeking feedback on my understanding of linked lists

Questions / Help
1

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!

2

The super quick TL;DR is that

[1, 2, 3]

is simply sugar for

[1 | [2 | [3 | []]]]

The thinking that it’s a list where the next element is another list is a little flawed. Each node is a value and a pointer to the next node (value/pointer combo).

2 Likes
3

Thinking in data structures used in imperative languages will not do you any good here. A list is just a list, the internal implementation might be based on linked lists or not, doesn’t matter either way as we are operating at a higher abstraction in the language.

In your first example:

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

You are comparing a list that has elements 1 and 2 to a list that has 1 and a list containing element 2.

The cons operator in your second example is used for destructuring, it has nothing to do with linked lists. It will always follow the pattern:

[head | tail]

Where the head is the first element and tail is the rest of the list.