Would be really interested in a solid tree/list/doubly linked list structure. The borrow checker appeared to make the construction of such a structure impossible.
Linked lists get efficiently implemented with unsafe, but they're just not used by Rust folks a lot because they're a pretty niche data structure.
I don't mind the callout that you need to use unsafe for recursive structures, but it would be useful to acknowledge that as part of the language design in the rust book. As a beginner you can easily pick up a simple LeeCode problem to learn the syntax and accidentally pick an impossible problem.
In general, it's not possible to enumerate all negatives, but it is for all positives, so I try to say more about what is than what is not.
The issue is not graphs, trees, and lists. These are useful! It's implementing them the way that you do in CS 101 that is the issue.
Cyclic/recursive datastructures are common in web services, where one needs to model bidirectional relationships ( just think of friends on a social graph ). As well as several primitive datastructures such as the O(1) LRU cache.
Checking the Rust docs out, a dev who encounters this problem for the first time will eventually need
- "Reference Cycles Can Leak Memory" https://doc.rust-lang.org/book/ch15-06-reference-cycles.html -- caveat: what if ownership is truly bidirectional?
- "unsafe" https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html
- 5 different primitive lists which don't tell you how to make a friends graph: https://rust-unofficial.github.io/too-many-lists/infinity-do...
- Someone elses attempt: https://rcoh.me/posts/rust-linked-list-basically-impossible/
- Careful reading of the LinkedList implementation to see that unsafe is probably the best approach: https://doc.rust-lang.org/beta/src/alloc/collections/linked_...
I'm a little biased on this front, when I first picked up Rust I chose to tackle an O(1) LRU cache as a quick learning exercise. I ended up beating my head against a wall for 20 hours. However on my current project I'm analyzing the wikipedia dataset ( another bidirectional structure ).
It would be useful to have a canonical/standard way to address such programming tasks other than "don't" - particulary if the way to address them is substantially different from what someone would have learned in a different language.
Do you really think the majority of professionals have CS degrees? I’m not so sure. And beyond that, it would have to be “a majority with a degree” and “a majority that choose to implement data structures as an initial/early task.” I’m really not convinced the numbers actually play out that way.
I think while my early experience biased me, the pain would have happened at one point or another eventually. I'd be surprised if the majority of web devs, and data science folks exploring rust wouldn't hit this problem at some point or another. As an example, one could easily run into this problem while writing an wiki,instagram, or twitter clone!
You may want to use something with those characteristics, sure, but that doesn't mean most users start by trying to implement, rather than use something existing.
Although that may or may not be flexible enough for your needs
You don't, really. Recursion is not the important part. The ownership model is hierarchical. If your structure is a directed tree with all links (pointers) flowing out from the root, it can easily be built. As soon have you have cycles or multiple parents, you'll need either unsafe or some ownership extension like shared ownership (Rc/Arc).
Singly linked list => Easy
Tree => Easy
Tree with backreferences => probably best to use unsafe
Graph => probably needs unsafe for best performance