Depends whether by "safe" you mean "not using unsafe" or "the implementation is safe". Many core data structures in Rust use unsafe, but I think most people would consider them safe implementations.

In the same way my c++ code is safe, yeah, the 'unsafe' code in this random-looking repo very well may be safe.

Unsafe rust has numerous safety checks above and beyond C++...

I’m very surprised that the rbtree needs to be unsafe at all.

It feels like a very early attempt. Skip the parent pointers and use Option rather than raw null pointers. Should get rid of the unsafe.

Linked list strikes again.

Is there not a way to do safe linked lists in Rust?

You can do a singly linked list just fine.

But with a doubly linked list, who owns the memory to each node?

In reality, you can do a doubly linked list with something like `RefCell`.

See the famous blog post on linked lists in rust here: https://rust-unofficial.github.io/too-many-lists/fourth-buil...

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.