> Are there any data-structures or algorithms or something that you simply cannot implement in Rust without using unsafe?
No. If you wrap every piece of data in your whole program in RefCell, the borrow checker will leave you alone, and it will be like programming in most other languages. (There are some minor differences, like the fact that your program will be refcounted rather than garbage collected, which doesn't deal with cyclic references, but let's ignore those.) Alternatively, you can wrap your whole program in "unsafe{...}", and use raw pointers everywhere, and it will be similar to programming in C.
EDIT: My comment is trying to give a general understanding that will hold most of the time. See the other comments for fun edge cases :-).
But if you use RefCell, then you won't get any useful compile-time checks, will you?
In other words: if you have Rust _without_ unsafe and without RefCell (and similar stuff), will you still be able to implement anything in it and keep compile-time checks and other benefits of ownership system?
> But if you use RefCell, then you won't get any useful compile-time checks, will you?
If you use RefCell, then the compile-time checks won't be necessary. For example, in Java there are no compile-time checks: everything is just garbage-collected at runtime. Likewise, RefCell is lightweight garbage-collection (modulo cyclic references).
> In other words: if you have Rust _without_ unsafe and without RefCell (and similar stuff), will you still be able to implement anything in it and keep compile-time checks and other benefits of ownership system?
Ah, in that case there are a lot of things you can't implement: Strings, doubly-linked lists (which is the point of this article), trees with backpointers, graphs, vectors, etc. Fortunately, you rarely need to: if you need a data structure, it's probably already implemented in Rust. The standard library has most common data structures, and there are often crates for less common ones. If you do need to write unsafe Rust, it's about as scary as C. I've written a reasonable amount of Rust code, and only ran into one situation where I (think) I need unsafe code.
No. If you wrap every piece of data in your whole program in RefCell, the borrow checker will leave you alone, and it will be like programming in most other languages. (There are some minor differences, like the fact that your program will be refcounted rather than garbage collected, which doesn't deal with cyclic references, but let's ignore those.) Alternatively, you can wrap your whole program in "unsafe{...}", and use raw pointers everywhere, and it will be similar to programming in C.
EDIT: My comment is trying to give a general understanding that will hold most of the time. See the other comments for fun edge cases :-).