Rust users are the only ones who have convinced themselves that linked lists are "obsolete" (i.e., "myth 3"). The fact that something that in most other languages could be accomplished effortlessly now requires so many epicycles, where some are better than others, is a polemic.
Doing rust the "right way" you end up with FP just by a slightly different path: make everything immutable, clone data, use multiple returns and so on.
> Rust users are the only ones who have convinced themselves that linked lists are "obsolete" (i.e., "myth 3"). The fact that something that in most other languages could be accomplished effortlessly now requires so many epicycles, where some are better than others, is a polemic.
I agree with you that the Rust community is far too defensive and dismissive about linked lists.
However, the underlying problem is that the C/C++ community thinks linked lists are "simple". This is ALSO not true.
They're fundamental. They're simple in that they're easy to define and reason about. That doesn't mean that it's impossible to make mistakes with them and so on.
> They're simple in that they're easy to define and reason about.
Only they aren't.
Who allocates a node? Who owns a list node? Who deallocates a node? Who owns a list node when you disconnect it? How do you handle walking a list when someone may update it at the same time? How do you ensure that you don't deallocate a list underneath somebody? What happens when a list is circular? How do you detect that a list is circular? How do you deallocate a circular list?
In fact, a "linked list" is a particularly nasty data structure to reason about in the presence of concurrency if you don't have garbage collection.
Personally, I think that Rust's inability to deal with linked lists points out some fundamental failing of the language itself. However, that doesn't make linked lists simple or easy.
To answer your questions: 1. The allocator. 2. The caller. 3. The caller, typically via list operations. 4. Synchronization 5. Have only one owner or reference counting. 6. Never had to do it outside studying for an interview. 7. mark and sweep.
You could make the same exact argument about arrays or any kind of structure with reference semantics.
I guess you could say that computers in general are hard. Doing real systems programming, where you can't do garbage collection, is hard.
But then again Rust isn't especially good for systems programming with the lack of a stable ABI, lack of a memory model, and so on. So it's really the worst of both worlds: a horribly constrained language that attempts to solve a subset of trivial memory errors in a way that is painful for the programmer, and it's effectively worthless for systems programming (even for the three targets it supports).
Which allocator? Your program happens to have more than one. The caller owns a node? Which caller? There are three iterators moving through your list. Synchronization, hmmm? Is your priority throughput or latency? Is your priority fairness or progress? Only one owner sure makes your linked list a LOT less useful--so much so that you probably want to use a different data structure. If you wish to ignore circularity, you may wish to use a different data structure. Mark and sweep? Oh, apparently you're good with large pauses while you traverse the universe? Well, apparently those people who use incremental garbage collection or generational garbage collectors need to avoid linked lists, eh?
The fact that you think these answers are easy and obvious should give you pause.
Concurrency in non-GC languages is not at all a solved problem. So much so, that "use GC" is often the only acceptable answer.
1. Unless you have a good reason, the default one. 2. call the right allocator/do RAII. 3. The 'borrow checker' doesn't solve concurrency problems. 4. it's not a graph data structure, if you're using normal list operations you won't introduce cycles---concurrency bugs not withstanding (see 3). Not sure why you're hung up on that.
Pretending linked lists are some sort of unsolved computer science problem that necessitates all this pain is quite silly and quite telling.
Doing rust the "right way" you end up with FP just by a slightly different path: make everything immutable, clone data, use multiple returns and so on.