Why writing a linked list in Rusts is basically impossible(rcoh.me)
rcoh.me
Why writing a linked list in Rusts is basically impossible
https://rcoh.me/posts/rust-linked-list-basically-impossible/
8 comments
Rust is very different in other languages. In many languages, implementing data structures is easy, and so it's how you start out. In Rust, it's not easy. But luckily, you don't have to write them yourself! That's what crates.io is for. Or, if you want a basic linked list, there's one in the standard library.
That said, linked lists are almost never what you want anyway, so it's not particularly relevant to most Rust programmers. And when you do, you use one of the ones that have already been implemented and move on with life.
The "Too many linked lists" book linked from the post goes into this in great detail.
That said, linked lists are almost never what you want anyway, so it's not particularly relevant to most Rust programmers. And when you do, you use one of the ones that have already been implemented and move on with life.
The "Too many linked lists" book linked from the post goes into this in great detail.
Well having written a lot of C and a lot of data structures, particular in low resource devices, I'm well aware of the details needed to do so. I suspect many others are in the same camp. Pointers are hard, however after 10 years of practice there not so bad ;)
I feel that saying ohh you should never need to write your own pointer chain (linked list, trees etc) is a bit too sweeping and doesn't match my experience.
"not particularly relevant to most Rust programmers" begs the question is their less of an overlap from C programmers and Rust programmers than is being generally touted?
I feel that saying ohh you should never need to write your own pointer chain (linked list, trees etc) is a bit too sweeping and doesn't match my experience.
"not particularly relevant to most Rust programmers" begs the question is their less of an overlap from C programmers and Rust programmers than is being generally touted?
> however after 10 years of practice there not so bad ;)
I know; I've been using them for over 20 years.
If you're that confident in your knowledge here, then using Rust wouldn't be a problem for you: you can go the unsafe route and just do the same thing you'd do in C.
> doesn't match my experience.
Sure. Your experience hasn't been in Rust. That is, when you have generics, and a good package manager, there's virtually no reason to write your own, as you can always use one that already exists. C doesn't have those things, and so you end up doing a lot more work yourself compared to Rust.
I know; I've been using them for over 20 years.
If you're that confident in your knowledge here, then using Rust wouldn't be a problem for you: you can go the unsafe route and just do the same thing you'd do in C.
> doesn't match my experience.
Sure. Your experience hasn't been in Rust. That is, when you have generics, and a good package manager, there's virtually no reason to write your own, as you can always use one that already exists. C doesn't have those things, and so you end up doing a lot more work yourself compared to Rust.
"If you're that confident in your knowledge here, then using Rust wouldn't be a problem for you: you can go the unsafe route and just do the same thing you'd do in C."
That's what I didn't understand - why the author didn't just use "unsafe". There's nothing intrinsically bad about using "unsafe", you just have to test that code thoroughly. There's plenty of robust C code out there.
That's what I didn't understand - why the author didn't just use "unsafe". There's nothing intrinsically bad about using "unsafe", you just have to test that code thoroughly. There's plenty of robust C code out there.
Okay thats the bit that I was missing, seems a reasonable compromise!
Yup. It’s a totally reasonable thing to do here. It’s why it exists!
I think the key is the following quote at the end of the article:
> I find a bit of solace in the fact that implementing a data structure like this in a non-garbage collected language without Rust is also quite tricky; you need to carefully keep track of when a node has no more references and can be freed
The main difference between Rust and most other non-garbage collected languages is when the trickiness occurs: for Rust, the compiler complains about problems a lot, while for other languages, the problems usually only manifest at runtime.
If you're doing something that requires a pointer soup and can't use garbage collection, the choice is between Rust with compile-time checks and C or C++ with (at best, by using the appropriate sanitizers) runtime checks.
> I find a bit of solace in the fact that implementing a data structure like this in a non-garbage collected language without Rust is also quite tricky; you need to carefully keep track of when a node has no more references and can be freed
The main difference between Rust and most other non-garbage collected languages is when the trickiness occurs: for Rust, the compiler complains about problems a lot, while for other languages, the problems usually only manifest at runtime.
If you're doing something that requires a pointer soup and can't use garbage collection, the choice is between Rust with compile-time checks and C or C++ with (at best, by using the appropriate sanitizers) runtime checks.
The author is quite open about his lack of expertise with Rust, would be good for someone more knowledgeable to explain the right approach. Also does the benefits actually outweight the cost?