"mut" location is unintuitive but works. Why?

Question

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?

Answer 1

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.

Also, linked lists in rust are not a trivial program.