Mutation of a variable inside while loop

Question

I am trying to build a singly linked list:

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

struct List<T> {
    head: Option<Node<T>>,
}

impl<T> List<T> {
    fn new() -> Self {
        List { head: None }
    }

    fn add(&mut self, element: T) {
        let node = Node {
            next: None,
            element,
        };
        // get the node at the end of the list
        match self.head {
            None => self.head = Some(node),
            Some(_) => {
                let mut last_node: Option<Box<&Node<T>>> =
                    Some(Box::new(self.head.as_ref().unwrap()));
                while let Some(node) = last_node {
                    let n = node.next.take().map(|n| &n);
                    last_node = n;
                }
            }
        }
    }
}

fn main() {}

I am getting a compilation error:

error[E0308]: mismatched types
  --> src/main.rs:28:33
   |
28 |                     last_node = n;
   |                                 ^ expected struct `std::boxed::Box`, found reference
   |
   = note: expected type `std::option::Option<std::boxed::Box<&Node<T>>>`
              found type `std::option::Option<&std::boxed::Box<Node<T>>>`

While I understand the reasoning behind the error, I am not able to work around this.

I need to add an element at the last of the list. For this, I take the approach where I repeatedly loop over the next element of the list until it is not a None and set the new value there.

I am aware that this is an imperative approach which we do in C or Java. I am not sure how to do this in Rust.

Does [How to implement an addition method of linked list?](https://stackoverflow.com/q/30441456/155423) answer your question? Maybe [Adding an append method to a singly linked list](https://stackoverflow.com/q/43976787/155423)? There's also [Learning Rust With Entirely Too Many Linked Lists](http://cglab.ca/~abeinges/blah/too-many-lists/book/README.html) — Shepmaster, Jan 23 '18 at 16:12
`Option>>` This type makes no sense. It's optionally a dynamically allocated reference to a node. But why would you ever dynamically allocate the reference? If your iteration loop contains `Box::new` (as it does), then you know you've done something wrong. — Sebastian Redl, Jan 23 '18 at 16:14
See also [Obtaining a mutable reference by iterating a recursive structure](https://stackoverflow.com/q/37986640/155423). — Shepmaster, Jan 23 '18 at 16:18

score 1 · Answer 1 · answered Feb 25 '18 at 22:56

I would implement the add method as follows.

fn add(&mut self, element: T) {
    let node = Node { element, next: None };
    match self.head {
        None => {
            self.head = Some(node);
        }
        Some(ref mut head) => {
            let mut cur = head;
            while cur.next.is_some() {
                cur = {cur}.next.as_mut().unwrap();
            }
            cur.next = Some(Box::new(node));
        }
    }
}

To test the implementation:

fn main() {
    let mut list = List::new();
    println!("{:?}", list);

    list.add(5);
    println!("{:?}", list);

    list.add(4);
    println!("{:?}", list);

    list.add(3);
    println!("{:?}", list);
}

The output is:

List { head: None }
List { head: Some(Node { element: 5, next: None }) }
List { head: Some(Node { element: 5, next: Some(Node { element: 4, next: None }) }) }
List { head: Some(Node { element: 5, next: Some(Node { element: 4, next: Some(Node { element: 3, next: None }) }) }) }

Mutation of a variable inside while loop

1 Answers1