Even the most trivial singly linked lists have caused innumerable blog articles to be penned on how exactly to do that in the most idiomatic Rusty way.
Personally, I don't see any problem with using unsafe Rust in these instances, because linear types are not appropriate model as you don't have a single source and sink.
Uh, a singly linked list is trivial to implement...
struct LinkedListNode<T> {
value: T,
next: Option<Box<LinkedListNode<T>>>,
}
Implementing a double-linked list is where things get tricky, as the nodes don't have a singular owner.
E.g if you add some object to a generic hash table as a key by pointer, you better treat that pointer as being owned by the hash table and not mutate it, or interesting stuff will happen.
Well you exactly named the most difficult to handle data structures for Rust.
There are plenty that are easy
Is a Red-Black tree simpler than a linked list to implement than a linked list in Rust? What about a Fibonacci heap?
And implementing data structures in any language is hard. It's just a harder thing to do than most things because there's always gonna be a lot of gnarly implementation details and edgecases.
Why make it harder.
> excellent standard library.
The standard library is intentionally bare-bones. They don't want to maintain libraries in std, and want you to use crates.
> wider ecosystem of libraries
The quality of these is quite poor in a lot of cases. People literally make blog posts into crates.
As for the quality of crates, yes, this is the case in any language. Using a library includes the responsibility of making sure the quality is up to scratch. This is not unique to Rust.
To achieve static memory safety.
If you don’t need or want that, you’re probably better off sticking to other languages. Although hopefully, not something like C or C++ which the US government now advises against using for security reasons.
Edit: and even among "interview puzzle data structures", stacks and queues have much simpler semantics than linked lists.
Which you should be using anyway instead of linked lists so you don't blow up your cache.