[DonaldFisk]

(Singly linked) lists have many advantages (e.g. useful operations on them are side-effect free), but whether they should be used depends upon which problems you solve and which languages you use. It's unsurprising they're used all the time in Lisp, and functional programming languages generally. I'd advise against their use in C or other languages without garbage collectors. They're rarely needed in languages (such as Python and Java) which have vectors and hash tables as basic data structures. I've never found a need for doubly linked lists in any language, for any problem.

So you'll either have them built in to the language you'll be using, the company's using the wrong language, or you'll be tackling problems where they're not really needed.

[deathanatos]

What language would you recommend using a singly-linked list in, aside from Lisp? Why is it any less valid in non-GC'd languages? (Aside from memory management in C is fraught with error, but that's a problem not unique to singly-linked lists.)

I've never looked (at least, that hard) at the language; it was always a question of "is this the appropriate data structure for this task?". Linked-lists have somewhat peculiar time complexities, but occasionally those line up with what you need. (Usually a vector is also as good, time-complexity-wise, and wins out by being contiguous. But if you need O(1) removal…)

[trishume]

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.

[deathanatos]

> 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)

[trishume]

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.