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


tail sharing makes a good candidate for locality of reference/caching

I'd love to hear about how that is implemented contemporarily, I'd really appreciate if you gave me a poke if you find/write a nice article about that.

AFAIK: In statically typed languages where the linked list is part of core/stdlib,
(as opposed to some kind of JS where you implement it as nested length-2 arrays ([4,[3,[2,[1]]]]))
they are actually stored as arrays of significant size with pointer to next slice.
(And previous, as since the data structure is already quite large, they are often a doubly-linked list. What's another pointer?)

This makes them still more expensive to index into than a contiguous/dense array but makes both indexing AND iteration several orders of magnitude faster.

Pretty much the same thing that turned binary trees into massively wide trees used today.

There's more complexity, especially since this cancels some size optimizations of structural sharing, but that's what the compiler is for.

code of conduct - report abuse