Struggle with rust compiler — 2 Link to heading

Let’s imagine writing a simple linked list in rust. In particular, let’s implement push_front() method, which inserts an element at the…

Struggle with Rust compiler — take Option Link to heading

Let’s imagine writing a simple linked list in Rust. In particular, let’s implement push_front() method, which inserts an element at the head. (link)

struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}

struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> LinkedList<T> {
    fn push_front(&mut self, val: T) {
        self.head = Some(Box::new(Node{val, next: self.head}))
    }
}

We create a new node with the given value, set its next field with current head value, and then set self.head with the new node. Beautiful, except the Rust compiler complains

error[E0507]: cannot move out of `self.head` which is behind a mutable reference
  --> <source>:12:51
   |
12 |         self.head = Some(Box::new(Node{val, next: self.head}))
   |                                                   ^^^^^^^^^ move occurs because `self.head` has type `Option<Box<Node<T>>>`, which does not implement the `Copy` trait

error: aborting due to previous error

For more information about this error, try `rustc --explain E0507`.
Compiler returned: 1

You can also try it yourself here from Compiler Explorer. Let’s dig in a bit and try to understand why the compiler is complaining. The root cause is two-folds

we cannot move a value self.head behind a mutable reference &mut self, just as the compiler is saying. This is because if we move self.head to some other variable, then self.head drops and becomes invalid, and thus self also becomes invalid. The call Node{val, next: self.head} is where self.head is being moved.
Rust compiler is not that smart just yet. In our code, we move self.head to the new node, but then we immediately assign a new valid value to self.head, i.e., self.head = Some(Box::new(Node{…})). Unfortunately, the compiler can’t analyze that far. All it cares is that at one time, self.head was moved out, and this is not allowed.

The solution is to make sure self.head is always valid. That is, if we were to move its value away, then we need to supply it with a new value simultaneously — not literally but logically. This is done with std::mem::repalce() or std::mem::swap() functions. In our case, we need to use std::mem::replace().

// Moves src into the referenced dest, returning the previous dest value.
// Neither value is dropped.
pub fn replace<T>(dest: &mut T, src: T) -> T

So, our fix would be as follows:

--- before
+++ after
@@ -9,6 +9,7 @@

 impl<T> LinkedList<T> {
     fn push_front(&mut self, val: T) {
-        self.head = Some(Box::new(Node{val, next: self.head}))
+        let head = std::mem::replace(&mut self.head, None);
+        self.head = Some(Box::new(Node{val, next: head}))
     }
 }

We replace self.head with a dummy value, this case None and hold its previous value in a local variable head. We then create a new node that points to head, and set self.head to point to the new node. This is a generic solution, but there also exits a specific method for Option type —Option::take() does exactly that. Since our head variable is Option<...> type, we can simplify our code as follows too

--- before
+++ after
@@ -9,6 +9,6 @@

 impl<T> LinkedList<T> {
     fn push_front(&mut self, val: T) {
-        self.head = Some(Box::new(Node{val, next: self.head}))
+        self.head = Some(Box::new(Node{val, next: self.head.take()}));
     }
 }

Now as an exercise, try implementing pop_front() method, which should have the signature as follows.

fn pop_front(&mut self) -> Option<T>

The method shall

if the head node is empty, return None
else update head to point to the second node and return the first value

References: Link to heading

Learning Rust With Entirely Too Many Linked Lists

So let’s write pushing a value onto a list. push mutates the list, so we’ll want to take&mut self. We also need to take…rust-unofficial.github.io

replace in std::mem - Rust

Moves src into the referenced dest, returning the previous dest value.doc.rust-lang.org

cannot move out of dereference of &mut-pointer while building a sorted linked list

So, I’m learning Rust and decided to build a sorted linked list.stackoverflow.com