4 ms·
Funnily, I personally think linked lists are unintuitive. "We have a sequential block of memory, and we want to store a sequence in it... hrm... I know, why do
by Veedrac 11y ago
Funnily, I personally think linked lists are unintuitive.
"We have a sequential block of memory, and we want to store a sequence in it... hrm... I know, why don't we put the first element in this struct, and... I'll deal with the rest of the items elsewhere."
- Jtsummers 11y agoLinked lists would only be unintuitive if you wanted to apply them to a sequential block of memory like that. Linked lists are used in non-sequential blocks of memory, though you can use them in sequential blocks. It sometimes makes sense to, but really only in an embedded systems context where you're doing some other fun things like writing your own memory management system using preallocated arrays as heaps so that your memory usage doesn't grow unbounded.
- Veedrac 11y agoI'm aware there are circumstances where linked lists are useful, but IMHO they're rarely introduced alongside a context that justifies them. Unintuitive doesn't mean bad, FWIW.
- Jtsummers 11y agoI wrote that after a very, very long day and long after I should've gone to bed (stupid needing to wear clothes, and not wanting to wear dirty clothes). The main point I wanted to make was that you described linked lists as unintuitive specifically in the context of having access to sequential memory space. Linked lists are not, typically, used in that circumstance. They make much more sense, and I think become more intuitive, when you consider them in the context of non-sequential memory space.
- Retra 11y agoLinked lists are just trees that only have one child on each node.
- Veedrac 11y agoExactly - I think storing a sequence of values in a degenerate tree is unintuitive.
- xamuel 11y agoOkay... the sequence has length measured in the billions, and we want to be able to rapidly remove its elements, or insert new elements in front of existing elements. Suddenly linked lists (doubly-linked) are looking pretty intuitive :)
- Veedrac 11y agoI'm not convinced. I obviously can't say what I'd do if I had to think these up, but I think I'd be more likely to try and impart ordering on a contiguous array than building a multiple-allocation one. Going down this route would probably result in a contiguous linked list. You can argue that this is still a linked list, but I still find it conceptually more obvious. For a billion elements, it's probably also a lot faster, too.