Doubly linked lists are used all over for low level programming. For low access, large dynamic data they're a pretty good solution AFAIK.

You are absolutely right. They are used everywhere in the Linux, OpenBSD, and FreeBSD kernels, and likely many other kernels.

Replacing large linked lists with arrays is rarely an actual win. With an array, insertion and deletion become far more expensive, virtual memory is more likely to become fragmented or grow monotonically, and the cache misses avoided are almost certainly irrelevant to total performance.

I wasn't speaking of low-level programming. I was referring to very low-latency code.

Highly performant code tends to get complex. One way to ensure high performance and reduce complexity is to deal with values, not pointers; it is good for concurrency (no aliasing), excellent for cache locality, and the value is right there. Multi-versioned stable values work excellently, like RCU-locks in the Linux kernel.

Doubly linked lists are perhaps not the best example, but there are lots of practical data structures that aren't compatible with the single ownership restriction. It's possible to implement them in safe Rust using various techniques, but it's not ideal.

Then there is the fact that mutation makes things even harder. So for example, you can easily implement a tree using Box to hold pointers to child nodes, but you'll then need a little bit of unsafe code to write a mutable iterator over the tree. (Even mutable iterators for slices require unsafe code under the hood.)

And that should be fine. unsafe is not something to be forbidden, it is a marker for "here-be-dragons, as the compiler can't check that all invariants are correct when you dereference a raw pointer or modify a mutable static variable". In reality I've found the need for unsafe to be minimal, either when doing something that is actually forbidden for good reason or interacting with C libraries.

Yes, the OP said explicitly that he decided to use unsafe to deal with these cases.

>I decided this time I should just ignore all the dislike of `unsafe` and just use it as much as I need to. I think I was making life more difficult on myself by trying to avoid it so much, but when you have a lot of pointers that have multiple refereces between then, you kind of have to. Doulble linked and mutually linked structures - where any pointer chance can lead to a mutation - are Rust's achillies heel.

Sriram_malhar pointed out that doubly linked lists are usually not a good data structure to use anyway. I was pointing out that there are lots of more useful data structures that raise similar issues in Rust.

I don't think that using unsafe is "fine", necessarily. It is much better to implement a data structure on top of safe Rust if at all possible.