The borrow checker makes a doublily linked list difficult, from my understanding.
They're almost always a bad data structure to pick though, as the speed difference between being able to iterate a contiguous list, and even completely rebuild it, vs having to follow arbitrary pointers mean that the 'complexity' improvements of a linked list often become irrelevant.
------
Open Question)
I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level.
Is there any credence to that, and if so, is it happenstance, or is there some more fundamental reason?
> I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level.
No, I think you are reading too much into it. One is free to Box-allocate/pointer-chase on every line in Rust without any trouble. Sure, as other low level languages, rust also prefers/makes stack-allocation more ergonomic/the default, which is a quite cache-friendly way of operation but not even the stack is “native” in and of itself - it is just a frequently and extensively used part of the “heap”.
Because of cache locality issues, linked lists are a bad data structure for almost all purposes. A plain old vector, or maybe a VecDeque, wins for almost all workloads.
For the few times they are useful (e.g. if you're writing lock-free algorithms, you want a hard upper bound O(1) append rather than just amortized O(1) append, or you don't have malloc available), Rust is a fine language to write them in. But also there are plenty of high-quality libraries on crates.io, so you probably won't have to write your own.