In order to learn Rust I'm just writing trivial programs. Here I've written a LinkedList with an insert function that adds nodes to the end of the list. The function works as expected but I don't understand why my mut positioning in the struct is working as intended. Here's the code:
struct LinkedNode<'a, T> {
val: T,
next: Option<&'a mut LinkedNode<'a, T>>
}
impl<'a, T> LinkedNode<'a, T> {
fn new(val: T, next: Option<&'a mut LinkedNode<'a, T>>) -> LinkedNode<'a, T> {
LinkedNode { val, next }
}
fn insert(&mut self, node: &'a mut LinkedNode<'a, T>)
where T: Display {
let mut i = &mut self.next;
while let Some(n) = i {
i = &mut n.next;
}
*i = Some(node);
}
}
Everything makes sense except this part:
struct LinkedNode<'a, T> {
...
next: Option<&'a mut LinkedNode<'a, T>>
}
What I'm mutating here is next and not the &'a LinkedNode<'a, T> within it.
I would have expected to need the following code instead:
struct LinkedNode<'a, T> {
...
next: mut Option<&'a LinkedNode<'a, T>>
}
but this doesn't even compile. It gives me this error instead:
error: expected type, found keyword `mut`
--> src/lib.rs:5:11
|
3 | struct LinkedNode<'a, T> {
| ---------- while parsing this struct
4 | val: T,
5 | next: mut Option<&'a LinkedNode<'a, T>>
| ^^^ expected type
Can someone explain what's going on here to me please?
There's two meanings for mut.
In &mut, it means a mutable, exclusive reference. An &mut value can change the contents it points to and give out &mut references to itself and its contents.
In patterns, like let mut x = y;, mut means that the binding is mutable. This value itself is mutable, and can give out &mut references to itself and its contents. There's also ref mut, which creates an &mut binding, but that doesn't apply here. You can also have &mut in a pattern, like let &mut x = y, which destructures the reference, copying the value. This also doesn't apply here.
Having a bare mut in a type, like you tried above, doesn't make any sense. Immutable and mutable owned values (not references) are the same type. The only type-level mut is &mut.
It might make theoretical sense to have something like this.
struct LinkedNode<'a, T> {
val: T,
mut next: Option<&'a mut LinkedNode<'a, T>>
}
However, this is not allowed either, because in rust, the mutability of each member is inherited from the owner of the whole struct.
let a = LinkedNode { val: 1, next: None }; // immutable
a.val = 2 // does not compile
let mut b = LinkedNode { val: 3, next: None }; // mutable
b.val = 4 // compiles
If you struct was this.
struct LinkedNode<'a, T> {
val: T,
next: Option<&'a LinkedNode<'a, T>>
}
Then you couldn't insert more than one node because you can't get a mutable reference to the node in next, regardless of the mutability of next itself.