https://dystroy.org/blog/how-not-to-learn-rust/
Mistake 7 : Build lifetime heavy API
Am I reading this right? In rust, a language designed for managing lifetimes, it's prohibitively difficult and inefficient to manage lifetimes.
Solution: freaking copy everything... marvelous...
PS: mistake 3 - linked lists are not hard in rust, they are impossible in safe rust, both to implement and to use properly, and that will always be embarrassing. Even worse when you religiously refuse to admit it, and intentionally miss the whole point of the data structure.
@namark what is the quintessential use case for a linked list that can be more efficiently and securely implemented in #c or #cpp? Come to think of it, are there *any* use cases at all where a #Rust developer would actually need to *implement* a #LinkedList ? Aren't there libraries for that? (I haven't taken CS, so feel free to school me)
@hobson
> what is the quintessential use case for a linked list
There is no quintessential use case, there are many different use cases, real and potential. What I've encountered in the wild can maybe be split in two major categories:
1. High level control flow. The nodes of the list represent the entire state of your program, and the list itself becomes some sort of a self modifying linear state machine. It could be a GUI wizard with next and back buttons for example, that decides what screen to show based on user input and system state. Nodes represent the screens, traversing and modifying this linked list is essentially your whole program in that case.
2. Optimization of complex algorithms. When you need to insert or remove elements from the middle of the container often, a linked list with a custom allocation strategy can be your best bet. I think there is an example of that somewhere in these lectures
https://yewtu.be/playlist?list=PLHxtyCq_WDLXryyw91lahwdtpZsmo4BGD
https://yewtu.be/playlist?list=PLHxtyCq_WDLXryyw91lahwdtpZsmo4BGD
when implementing some sort of a tournament scheduling algorithm. Shame they don't have meaningful titles...
In both cases the memory allocation pattern is irrelevant, as in case of 1 the iteration is slow by definition, it's a high level logical state change, and in case of 2 the allocation is handled separately and not tied to logical creation of nodes.
I'm sure there are many more examples where the data structure can be used, and there are many more potential use cases. The whole idea of a linked list is that you can independently modify parts of it in various ways without affecting readers or writers that are working on other parts of the list, even in parallel. This goes directly against rust model of safety for containers.
The argument of "it's not cache friendly" is just a marketing cop-out. Ignoring that memory allocation strategy is not in any way definitive of the data structure and then telling people they should be aspiring to write their code with idiosyncrasies of some popular CPU architectures in mind, and that everything that doesn't fit in that box is just a useless niche is either naive or sinister.
> be more efficiently and securely implemented
Note than rust's model of safety is not synonymous with security. Expressiveness of the language is more important for security than any mechanical guarantees you can provide. Programmers need to be able to understand the code to maintain it correctly, and if a linked list is a perfect fit for the given problem it should be used. Can you substitute it with something else that is just as efficient and adheres to rust safety model? In some cases - maybe, but even if you do you will certainly be sacrificing some expressiveness and ergonomics.
Said expressiveness also helps the compilers to optimize code for various architectures, not even just CPUs. otherwise if you are thinking of a specific architecture, you'll have to throw all the code away for the next one. (Or, you know, you could instead acquire an international monopoly on software by abusing copyright and force hardware manufacturers to come up with increasingly perverse designs, to optimize your inline assembly code).
> Aren't there libraries for that?
Here are my thoughts on using a library implementation in rust:
https://qoto.org/web/statuses/107394401941447264
Rust is so fundamentally against linked lists that you can't even use a linked list properly. As workaround they introduce the notion of a cursor, which makes lists into special case, not eligible for any generic code that handles containers, so really a backwards hack, that doesn't even unlock the full potential of the structure, since it only models the "single writer multiple reader" scenario, which is the best safe rust can do. You might ask yourself where did this cursor thing come from? The answer is in rust's intrusive linked list library,
https://docs.rs/intrusive-collections/0.9.0/intrusive_collections/
where you can finally witness the concession under the Cursors section: "This is similar to how a C++ iterator works". Never in any front facing marketing material though, that would be disastrous.
I might difficult to understand if you haven't worked with or these data structures, especially in context of c++ standard library, were rust draws its inspiration from, but for anyone who did, I assure you these things should be obvious. Linked list is an example of a major weak point in rust, and the big question is how many other safe and efficient programs can you not write if you adhere to rust's definition of safety.
@hobson yeah in a garbage collected language such designs often are emergent. Like for the GUI wizard each screen would just have a reference to the previous and next screens and you'd get a doubly linked list without even realizing it. You don't necessarily need a rigid data structure, and otherwise you can at least arrive at it indirectly, and layer maybe even improve the clarity of the code by identifying it and substituting a library implementation.
Rust slapping you in the wrist and preventing such patterns at compile time can be really confusing, and it often feels like you need to be a c++ expert to correctly resolve some of these situations and not resort to workarounds.
@namark got it. I'm imagining "nested python ``dict``s" whenever you say #LinkedList. For your example 1. (compiler/interpreter) Guido uses nested dicts. For your example 2, Norvig and Russel use ``dict``s in AIMA. And may other people use graph dbs with graphql. These are indeed powerful *use cases* for existing linked list data structures that leverage existing high level libraries (or #database s) for CRUD.