That’s really only a problem if you spend a significant amount of time trying to “build data structures from introductory algos” without reaching for unsafe, though.
If you find it easy to build a linked list or graph in C, you can do it just as easily in Rust — use unsafe, and you have your easy linked list, with exactly as much safety as it had in C. Sure, it’s more challenging to build a fully memory and thread safe linked list or graph, but it’s actually hard as hell to do that in C too. Other languages make it easy to build one with these guarantees only by requiring significant runtime support, which is out of scope for Rust.
In the end, it’s pretty unrealistic to expect that any language would allow you to write a guaranteed memory and threadsafe graph structure with zero runtime overhead, without a lot of knowledge, time, and attention on your part — there are no silver bullets.
And if you’re using Rust for anything real you’re generally not doing sophomore computer science homework like this anyway.
The problem is that unsafe data structures are often less safe (harder to avoid UB) than in C, because in the presence of pointer aliasing and cycles (found in unsafe data structures including BTreeMap's node.rs https://doc.rust-lang.org/src/alloc/collections/btree/node.r...), Stacked Borrows places strict conditions on constructing &mut T (they invalidate some but not all aliasing *const T). And the user of an owning or intrusive linked list generally expects to receive &mut T, which is not always safe to construct because of Stacked Borrows. In fact, Gankra, a major contributor to unsafe Rust libraries, standards, and documentation, doesn't solve this problem through axiomatic reasoning, but instead an "oversimplified" "heuristic" (IMO hopes and prayers): https://rust-unofficial.github.io/too-many-lists/fifth-stack... (written 2022-01).
In practice, I find that unsound libraries frequently get written and used unknowingly in the wild. I've commented on this earlier at https://news.ycombinator.com/item?id=31897503.
In short, I believe that Stacked Borrows places unreasonable and unattainable requirements on authors of unsafe structures and algorithms, which serve as the foundation for practically all safe code (outside of the vanishingly rare case of code operating on tree-shaped fixed-size variables allocated solely on the stack, and never creating aliased mutable pointers).
And The “easy” C sophomore computing science graph is inevitably chock full of Undefined Behavior too, the implementers just never noticed or gave a shit because they cobbled something together that looked superficially correct, the compiler didn’t complain, so they decided they were all good. Sophomores, as it turns out, are hardly world-beating experts in C standard esoterica.
The rest of what your wrote is completely irrelevant to the original point: this seems hard in safe Rust only because you’re comparing it to doing something totally different and simpler in C.
I agree that sophomores are better off sticking with safe Rust than writing linked lists, but they'll be using libraries written in unsafe Rust, and a "safe" Rust program built on unsound foundations is undefined behavior anyway (through no fault of your own).
You said Rust linked lists have "exactly as much safety as it had in C". Are you seriously arguing that C linked lists are just as wrong as Rust ones, by saying a CS student is as likely to write an incorrect C linked list as a hardened professional is to write an incorrect Rust linked list (eg. Tokio and https://gist.github.com/Darksonn/1567538f56af1a8038ecc3c664a...)? Stacked Borrows ensures that translating sound C code into idiomatic Rust APIs produces needlessly unsound Rust code, and the Rust language (or a specification if it existed) means C translated directly into raw-pointer Rust is unidiomatic and you're fighting the language every step of the way (no autoderef, no -> operator). At this point, an experienced programmer is more likely to write and use a correct C linked list than write and use a Rust one.
> Are you seriously arguing that C linked lists are just as wrong as Rust ones, by saying a CS student is as likely to write an incorrect C linked list as a hardened professional is to write an incorrect Rust linked list
What?
No, I’m saying that writing a linked list in C is “easy” if and only if your implementation doesn’t even bother to try to cope with the 9000 foot guns C offers you — that your easy C graph data structure is basically always a disaster of Undefined Behavior and thread unsafety, because if you try to make it otherwise, it will cease being at all easy. It will become in fact really fucking hard
So when I say “you can have your easy C-style linked list in Rust, just use unsafe”, I agree entirely: the Rust implementation will also likely be a gigantic clusterfuck of Undefined Behavior. That’s the entire point: it’s only ever easy in either language if you’re willing to blow both of your feet and you dick clean off. It’s easy only if you’re so inexperienced and naive that you don’t even perceive the dangers of the highly efficient dick-and-leg removal device you’ve built in C, and whine on forums about how mean-old-Rust is hard in comparison because it keeps refusing to compile your dick_exterminator.rs file.
That’s the Apples to Apples comparison. Which unsafe thing is harder to get right, I don’t honestly give a flying fuck about. Now, it’s highly de-fucking-batable that it’s easier for “an expert C programmer” to avoid undefined behavior entirely in an arbitrary mutable graph implementation in the presence of multithreading unless we’re talking about an entirely mythical level of expert here, but that’s utterly offtopic to the discussion at hand. You were just looking to grind a fucking axe about Stacked Borrows and decided to rant at me about it, but it really has fuck all to do with anything I was saying, man.
You can have an easy graph structure in Rust in the only way you can easily have one in C: by not giving a single shit about correctness.
A C data structure is never a disaster of "thread unsafety" if, like most data structures, you don't use it across threads. Any Rust data structure which is Send and Sync, translated literally into C, is just as safe in C to read (or write in the rare cases &Structure is mutable) across threads, and create in one thread and destroy in another. It's only thread-unsafe if used in a thread-unsafe manner (and all Rust adds for non-multithreaded data structures is checks to prevent users from mutating across threads, though its pattern of "one handle per thread" is helpful for structures designed to be mutated across threads).
And C is not a dick-and-leg removal device, it's a direct representation of runtime semantics (aside from signed integer overflow which is avoidable, type-based alias analysis which is rare, etc.), and any sound Rust code which doesn't transmute types can be compiled into equally UB-free C code, and even Rust which commits UB by violating SB (many unsafe libraries) can be transpiled into UB-free C code as long as you don't use `restrict` when inappropriate. Rust is merely a possible way to organize a program to avoid UB, to be followed when helpful (RAII, catching use-after-free in application logic, avoiding reference counting errors, multithreading) and replaced when it impedes writing low-level code. It's not a religion where apostasy is punished by castration.
I'm criticizing Stacked Borrows because I've seen more than enough evidence that it's an unreasonably stringent memory model for writing unsafe code. Please stop putting words in my mouth and misrepresenting my positions as profanity-laced straw men, like "not giving a single shit about correctness".
If you find it easy to build a linked list or graph in C, you can do it just as easily in Rust — use unsafe, and you have your easy linked list, with exactly as much safety as it had in C. Sure, it’s more challenging to build a fully memory and thread safe linked list or graph, but it’s actually hard as hell to do that in C too. Other languages make it easy to build one with these guarantees only by requiring significant runtime support, which is out of scope for Rust.
In the end, it’s pretty unrealistic to expect that any language would allow you to write a guaranteed memory and threadsafe graph structure with zero runtime overhead, without a lot of knowledge, time, and attention on your part — there are no silver bullets.
And if you’re using Rust for anything real you’re generally not doing sophomore computer science homework like this anyway.