[ok123456]

The ownership rules make it very difficult to write data structures.

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.

[fleventynine]

> Even the most trivial singly linked lists....

Uh, a singly linked list is trivial to implement...

  struct LinkedListNode<T> {
    value: T,
    next: Option<Box<LinkedListNode<T>>>,
  }

Any data structure where chunks of heap memory are owned by a single pointer (red black trees, singly-linked lists, vectors, deques, circular queues, etc) can be represented easily in safe rust.

Implementing a double-linked list is where things get tricky, as the nodes don't have a singular owner.

[likeabbas]

Yep. It’s even why the standard library implementation of a doubly link list uses unsafe! Which, I don’t think it a problem. If you’re writing a data structure, it will be under heavy scrutiny, review, and testing so we should be okay with bypassing the compiler checks.

[codedokode]

As I understand, in low-level languages the concept of ownership exists anyway, no matter whether the language allows to declare it explicitly or not. Rust just makes you write it out explicitly.

[ok123456]

Yes ownership exists, but the semantics of Rust's automatic ownership system are different as they're enforced as a linear type.

[tmtvl]

The only concept of ownership that exists in low level languages is that the kernel owns memory and gives your program a chunk of it. Aside from that I think the closest equivalent concept is the system break, but that just determines where in memory your stack and heap are divided.

[mtlmtlmtlmtl]

Ownership doesn't exist in the C language per se, but it is still an important concept you have to reason about when manually managing memory. I think that's what GP meant.

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.

[tmtvl]

I mean sure, but we're not talking about C, we're talking about low-level languages, like IA32 assembly.

[mtlmtlmtlmtl]

No one uses "low level language" to mean only assembler anymore. Besides, you also have to reason about ownership in assembler. It's not something you can really get away from at any level of the stack.

[tcfhgj]

> Even the most trivial singly linked lists....

Well you exactly named the most difficult to handle data structures for Rust.

There are plenty that are easy

[ok123456]

A linked list is the simplest data structure there is.

Is a Red-Black tree simpler than a linked list to implement than a linked list in Rust? What about a Fibonacci heap?

[howinteresting]

The simplest data structures are pairs (A, B) and Option<T>.

[ok123456]

Wouldn't call those data structures. Those are data types.

[howinteresting]

They are structured data. The restriction of the term "data structures" to what's asked in interview puzzles is ridiculous IMHO.

Edit: and even among "interview puzzle data structures", stacks and queues have much simpler semantics than linked lists.

[mtlmtlmtlmtl]

I think using data structures as an example is sort of missing the forest for the trees. It's definitely harder to do, but you generally don't need to as there's an excellent standard library and wider ecosystem of libraries that do this for you.

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.

[ok123456]

> implementing data structures in any language is hard.

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.

[antonvs]

> Why make it harder.

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.

[mtlmtlmtlmtl]

As someone coming from C I find the stdlib is fine. It has all the datastructures you need for the vast majority of code. It doesn't have very domain specific things like the kind of structures a text editor might use, for instance. That's fine.

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.

[bitwize]

The simplest data structure there is (aside from scalars) is the array or vector.

Which you should be using anyway instead of linked lists so you don't blow up your cache.