Yeah, a doubly-linked list is basically the worst possible choice for your first program in Rust. This is because Rust likes all of your memory to have one clear owner. And this means that cyclic data structures are unusually difficult compared to almost any other first program you might choose.<p>But if you really want to know how to do it, there's a really good tutorial on the subject titled "Learning Rust With Entirely Too Many Linked Lists": <a href="http://cglab.ca/~abeinges/blah/too-many-lists/book/" rel="nofollow">http://cglab.ca/~abeinges/blah/too-many-lists/book/</a><p>This will walk you through multiple different kinds of linked lists, and show you how to implement each in Rust. Along the way, you'll learn more about Rust's ownership system than most working Rust programmers generally need to know.<p>Personally, I've written quite a bit of production Rust code, and I've done so without ever touching 'unsafe' or needing a linked list. If I really did need a linked list, I'd either grab a good one off crates.io, or just knock out a quick one using `unsafe` and raw pointers. I mean, Rust can do basically anything C does if I ask nicely. It's just that if I choose to write "C in Rust", then I get about same safety guarantees that C offers.
That Rusts compiler fights against intuitive doubly linked lists is reasonable, because they wouldn't work when working in parallel on the list, while Rust by default also ensures safety doing that.<p>Having that in mind makes it easier for me to come up with ways how to appease the compiler. What measures would you take to write a thread-safe doubly linked list in C? Would you make it entirely exclusive and blocking? Well, then you might want let one "list" structure own all nodes. Would you want to allow parallel execution of operations on the list? Well, then break the ownership of the nodes up into smaller parts that you can hand out in parallel when they don't affect each other. What granularity of allowed and prepared-for parallelism gives the best performance depends on the use-case.
I've previously discussed on HN how Rust could support backpointers safely.[1] The idea is to have a "backpointer" attribute, with some additional checking. Backpointers are non-owning pointers locked in an invariant relationship with an owning pointer.<p>You need backpointers not only for doubly linked lists, but for some tree-type data structures. The backpointer invariant is easy to check at run-time, and it's often possible to eliminate that check at compile time. With this feature, few if any tree-type data structures need "unsafe". Tree update code is error-prone; you need all the help you can get there.<p>The other basic thing you can't express safely in Rust is a partially initialized array. If you had syntax for "This array is initialized up to element N", with suitable checking, "vec" could be written safely.<p>Rust is pretty close on this. Those are the two main gaps in the safety system. Calling external non-Rust code is a separate problem, one which hopefully will decline as more low-level libraries are rewritten in Rust.<p>[1] <a href="https://news.ycombinator.com/item?id=14303858" rel="nofollow">https://news.ycombinator.com/item?id=14303858</a>
Option #3(indexed tree) looks non-ideal but it actually has some really cool properties if you do it right.<p>1. If you know traversal order you can get <i>really</i> great cache coherency. We used to do this all the time with animation DAGs and the like in gamedev.<p>2. If everything is an "offset"/index instead of a pointer you can do things like in-place loading where creating something is just a single read() call. No constructors or annoying allocations to slow down loading. If you want to take this even further you can mmap() the entire file on disk and use massive(500mb+) files without using much actual memory overhead through letting the kernel page it in/out for you.
There is some good discussion on /r/rust [0] as well. I'm not trying to invalidate the author's post but rather share some more insight.<p>[0]: <a href="https://www.reddit.com/r/rust/comments/7z7p5m/why_writing_a_linked_list_in_rust_is_basically/" rel="nofollow">https://www.reddit.com/r/rust/comments/7z7p5m/why_writing_a_...</a>
Just a friendly reminder the you can get the Programming Rust book for only $15 along with a bunch of other good books for 3 more days at the Humble Bundle Functional Programming Bundle. I've been working my way through it and learned a lot so far about Rust.
I've struggled with Rust just a couple of times, nothing serious, so I'm not an experienced Rustacean by any means.<p>Question:<p>Ownership system obviously imposes some limitations, but gives safety in return.<p>Are there any data-structures or algorithms or something that you simply cannot implement in Rust without using unsafe?
> I find a bit of solace in the fact that implementing a data structure like this in a non-garbage collected language <i>without</i> Rust is also quite tricky<p>What? No it isn't. The entire problem here is incorrectly assuming that "A owns B" implies "A has a pointer to B". I don't know if this is a Rust-imposed constraint, but it certainly isn't a logically necessary one. Just do what C++ (and C#, etc.) do: the data structure (std::list, etc.) owns all the nodes, and the nodes merely reference each other. The nodes don't own their siblings. It makes sense and it doesn't get tricky.
Nobody mentioned that the Rust std has a doubly linked list in it? [1]<p>It uses shared pointers to reference other nodes in the sequence.<p>[1] <a href="https://doc.rust-lang.org/src/alloc/linked_list.rs.html#46-51" rel="nofollow">https://doc.rust-lang.org/src/alloc/linked_list.rs.html#46-5...</a>
I recently started to actually write some Rust code after reading about Rust here and there. The experience has been quite unique, it constantly forces me to think about the code at low level, which I find refreshing. And the compiler is truly impressive, it pinpoints me where things go wrong, and conveys the error messages in a very human-like fashion.
> // I actually don't understand why the line below compiles.<p>> // Since `head` was moved into the box, I'm not sure why I can mutate it.<p>> head.next = Some(Box::new(next));<p>I'm fairly new to Rust myself, but it's my understanding that since it was moved into the Box, the variable "head" is now just considered effectively uninitialized, so you can go ahead and set its fields, or overwrite it entirely with head = Node {...}, without affecting the value that was moved into the Box.
Tangentially, I'd love to see some list of "what does this language make easy" (C: raw memory manipulation!) and "makes hard" (C: memory-safe code)...<p>Does one exist for Rust?
"safe" means more than just memory safety.<p>Free from deadlocks, for one thing; who cares if no memory is misused if the show locks up.<p>Also, free from problems like thread A only traversing half the list because B removed a node in the middle which derailed A into a null pointer that looked like the list terminator (Even though no memory was misused.)
Also interesting is to figure out how Rust deals with closures, which reference the parent scopes, and how the corresponding (cyclic) data structures are managed.<p>Does Rust eliminate the cycles by copying? (expensive, and doesn't allow for writing)
You don't have to go as far as doubly-linked list. Writing a simple cons-list is hard enough:<p><pre><code> enum List<T> {
Nil,
Cons(T, Box<List<T>>)
}
</code></pre>
Imagine you're writing `Iterator`. You have a `&mut List<T>`. For `Nil`, you're done. For `Cons`, you take it apart, return the `T`, deref the `Box` and move your `&mut List<T>` to point to that value. Nothing could be easier, right?<p>Except in Rust you can't do that! One can resort to unsafe code or use ugly and inefficient workarounds to remain in safe-land.
I don't understand why there is a need for linked lists. I'm reading about fast insert in the middle, but there are other ways to insert data quickly. Maybe it's a need on hardware with specific memory management?<p>There are so many drawbacks to linked lists: cache incoherence, the use of pointers, no fast random access...<p>The single fact that rust makes it hard to implement a linked list should show that this data structure is a bad idea. Even when the C++ author is saying it, that should be enough, no?
Firefox is written in Rust, and I suspect that their DOM implementation has backpointers (from children back to parents), for performance reasons. It might be interesting to check how they did it.