Just use a generational arena (for example, thunderdome) as the backend buffer instead of a Vec. It solves the deletion issue automaticly. (And I'm suprised no one mentioned it, yet.)
1 Like
Yeah, the generational-arena or slotmap crate can solve this problem.
Such an arena usually has a linked list of its own as a backend 
// If there was a previously free entry, we can re-use its slot as long
// as we increment its generation.
if let Some(free_pointer) = self.first_free {
let slot = free_pointer.slot();
let entry = self.storage.get_mut(slot as usize).unwrap_or_else(|| {
unreachable!("first_free pointed past the end of the arena's storage")
});
let empty = entry
.as_empty()
.unwrap_or_else(|| unreachable!("first_free pointed to an occupied entry"));
// If there is another empty entry after this one, we'll update the
// arena to point to it to use it on the next insertion.
self.first_free = empty.next_free;
I agree with your second point.
For me, as someone who learned about linked lists long time ago, it was an obvious choice to try it. I try to implement something I'm familiar with in an unfamiliar language. it wasn't the first thing I tried with Rust, but it was early and of course I failed, but luckily there is the already mentioned too-many-lists...
In hindsight, it was good, mainly because of the question why are single linked lists so easy (once you know Box and Option and how to use it - I'd even argue a correct implementation is easier in Rust than in C) and why are double linked list such a problem.
You can know how the pieces move in chess, but that doesn't make you a good chess player. Or you can know the rules of Conway's Game of Life, but that doesn't mean you know how to build a Turing Machine with it.
Similar with Rust. You can know the ownership and borrowing rules, but that doesn't mean you already understand how this impacts your design.
For me, seeing double linked list as an ownership problem was a step to better understand Rusts ownership model.
3 Likes
Umm, yes? If you are conflating general purpose linked list (what OP's doing) with ad hoc intrusive list (what thunderdome's doing), then sure. I'm not sure what's the message you are trying to convey here.
Thank you very much for such detailed analysis.
Yeah, I was planning in evolving this to a double linked list, I wasn't aware of the recursion problem (I think I will probably test without implementing Drop trait first, just to see it breaking).
For display trait, that is interesting, I actually didn't look at traits at all, I think I'm getting ahead of myself in implementing a linked list without knowing everything about rust.
For the deletion part, yeah, you got two bugs there, in fact, I didn't test very much this list, I only tried happy scenarios, the main intent was basically having the list in rust. I wasn't aware unwrap threw exceptions though, good to know.
Not exactly am exception, unwrap is really just saying "I am sure this will never happen so exit prematurely the program if the condition is not met".
Whereas an exception in other languages is meant to be caught by the caller.
By the way, if you have not yet fully learned about Result in rust to handle errors, it is an important and very nice part of the language.
Exactly, when you use Rust, you should find other way to code usual stuff. It took about a year until I got comfortable using Rc/Arc. I still have problems with them occasionally. But overall, they do not bother me anymore and I can focus on functionality of my product.
I had to address ProgramCrafters issue with my very "unsafe" linked list example snippet I posted above.
Turned out recent versions of Miri don't like this line in my push_pack method:
// Initialize the new node
(*new_node).element = elt;
I had to change it to:
// Initialize the new node
// Write the element without reading uninitialized memory in the field
let elem_ptr = core::ptr::addr_of_mut!((*new_node).element);
ptr::write(elem_ptr, elt);
Now Miri is happy again 
2 Likes
Heya, I took a shot at how I would write your code. I'm not saying my way is better, just something to consider.
NodederivesDebugself: &mut List->&mut self- Change
Liststruct to have only 1Option(The two options need to stay in sync) - Moved the
displayfunction into implementation ofDebugtrait
A naive idea to have this simpler is to use Vec for holding the next element:
struct Node {
next: Vec<Node>
}
You can have invariant that next holds at most one element. Unlike for Option, the structure with Vec would compile. An interesting idea would be to have multiple members of next also as elements of the list, optimizing when it is common to add more than one element at the time and still making removal faster than from Vec.
Option<Box<Node>> is the at-most-one Vec
3 Likes
As a much less important issue than dropping uninitialized memory, the safety section in the push_back docs is incorrectly explaining why the implementation is using unsafe (and incompletely, at that!), instead of just the intent of a safety section, which is to explain to the caller of an unsafe-to-call method what their responsibilities are to not be unsound.
Further, just saying the self pointer should be "valid" is by itself is sufficiently ambiguous it's both "obvious" (then why bother with the section) or useless (not actually listing the specific requirements and forcing the caller to just guess what you meant, like they would anyway without the section)
A better safety section might read something like:
- self must be an aligned pointer to an initialized LinkedList value
- self.tail most be either null or an aligned pointer to Node valid to write
Note the lack of mentioning len or element being initialized, or anything about nodes forming a list etc., since those are correctness requirements, not safety requirements.
However, given a real implementation would probably have a bunch of these methods and probably doesn't want a compatibility burden of having specific requirements for each method the implementation would be constrained by, you could simply define what a "valid list" is in type or module level docs and declare all methods require or return that... but then you have the question of why are these methods even unsafe or bothering to document safety for them because you should then treat it as opaque and only use the type's methods to maintain a "valid list" instance given that would likely completely constrain the values.
There's another type of "safety" comment you're probably confusing them with, closely related, that are typically placed on an unsafe block or method call, that explains specifically how and why the safety requirements of the unsafe mechanisms used are being met.
Eg in this case, every deref of a raw pointer has safety requirements listed in the std::ptr module docs (instead of the pointer primitive type, for some reason), you would in theory go down that list for each dereference and qualify that malloc returned an aligned pointer to a T value... except that it actually didn't. It returned an aligned pointer for a T value sized block of uninitialized memory that you forgot to initialize.
This is the real issue with Crust (not that I think it's all that serious and needs criticism): "unsafe Rust" is actually a lot harder than C because you have a lot more rules to follow (arguably for very good reasons) due to the normal language still all being there.
1 Like