Hacker News new | ask | show | jobs
by trishume 3278 days ago
Linked lists make way more sense in languages with bump-pointer allocating garbage collectors specifically. In those languages (e.g Haskell, OCaml, Java) allocation is really cheap and they preserve locality so allocating all the links isn't as much of a penalty.

Also if you don't have a garbage collector you have to do reference counting, and if you want parallelism your reference counting has to be atomic, which when you're sharing a lot of linked list nodes, is another large penalty.
1 comments
deathanatos 3278 days ago
> Linked lists make way more sense in languages with bump-pointer allocating garbage collectors specifically. In those languages (e.g Haskell, OCaml, Java) allocation is really cheap and they preserve locality so allocating all the links isn't as much of a penalty.

Such allocation is possible in languages such as C++/Rust/C as well. (Though to how much the standard library in each supports you may vary.)

My point was that at least I choose linked lists for the O(1) node insertion/removals in addition to maintaining a sequence of items, a trait pretty much unique to linked lists. It's a matter of whether or not the order notation beats out any additional allocation time and cache effects (Vec/std::vector/continuous-memory lists being more friendly towards cache)

> Also if you don't have a garbage collector you have to do reference counting, and if you want parallelism your reference counting has to be atomic, which when you're sharing a lot of linked list nodes, is another large penalty.

Neither Rust nor C++'s linked list implementations require ref counting, and neither have a GC. A node is essentially,

  struct LLNode<T> {
    LLNode *next;
    LLNode *prev;  // if doubly linked
    T item;
  }
(the above is pseudo-syntax, adjust appropriately) Rust, for example, knows the linked list is only ever owned by a single person. (Barring either the list or the items being wrapped in Rc/Arc/Mutex/etc., but in that case, of course it is, but that's yet different and doesn't really impinge upon a linked list's general usefulness)
link
trishume 3271 days ago
Yah I know normal linked lists are totally possible in all languages. I should have specified I was talking about the use case of sharing data through immutable singly-linked lists.

In these languages you use them specifically because you can prepend without worrying about other things still holding a reference, even in other threads. In Rust you'd need Arc to do that.

Also yes you can use custom allocators in Rust/C++, but then you have to have everything have the same lifetime. With GC'd functional languages you don't because the GC will move them to the old generation if necessary.

I'm mainly talking about the empirical question of why Lisp/Haskell/OCaml use linked lists so much, but in other languages they're rare (e.g I see/use them less than heaps). In most cases where you want fast prepend you just append to a vector and just treat it as reversed or reverse it after.

link