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!
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:
we have 3 lists, but three of them point to the same existing list (structural sharing), but if I choose to append instead:
Although
list_threehas the same values[5,6,7,8], it does not point to the same nodes inlist_oneandlist_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