re: [ Elixir | Why Linked Lists? ] VIEW POST



I don't understand "Adding to list has low memory cost, while retaining the immutability that we desire."

I have a list A -> B -> C
I want to add D to the list end.
next(C) == nil?
I expect that next(C) should be D.
I need to mutate C, so I must copy it.
But if C was changed then I need to change B...
So I get full list copy then I add element to the list end.

Looks like this is suboptimal algorithm.

Can you please explain how it really works?


Good point! Yes you're right, I should've clarified by adding I in fact meant prepending.

In the end, it's just a normal linked lists that Elixir uses under the hood, so it inherits the same appending Big O for time. What you're asking is a little more, which is the fact that we have to maintain immutability for structural sharing, so yes you're also right in that regard - we'd need to recopy the entire linked lists and then only append it.

If we look back on my structural sharing example:

list = [5,6,7,8]
list_one = [1 | list]
list_two = [2 | list]

we have 3 lists, but three of them point to the same existing list (structural sharing), but if I choose to append instead:

list_three = [ list | 3 ] # => This creates an entirely new list

Although list_three has the same values [5,6,7,8], it does not point to the same nodes in list_one and list_two. I hope that makes sense!

There's this another really good article that even comes with Benchmark that shows this in action :)

You can also see it on the official language guide here too

code of conduct - report abuse