How to implement prepend for a linked list without needing to assign to a new variable?

Question

Something told me how to implement a linked list:

enum List {
    Cons(u32, Box<List>),
    Nil,
}

impl List {
    fn prepend(self, elem: u32) -> List {
        Cons(elem, Box::new(self))
    }
}

When I want to use prepend, I need to do the following:

list = list.prepend(1);

However, I want to create a function that does not need to create a new variable every time prepend returns. I just want to change the list variable itself using prepend:

list.prepend(1);

Here is one implementation that I come up with, but it's not right:

fn my_prepend(&mut self, elem: u32) {
    *self = Cons(elem, Box::new(*self));
}

The error is:

error[E0507]: cannot move out of borrowed content

Possible duplicate of [Cannot move out of borrowed content](https://stackoverflow.com/questions/28158738/cannot-move-out-of-borrowed-content) — Boiethios, Aug 14 '18 at 08:29
Note that a linked list is a chain of nodes, and usually a wrapper referencing the first node. Here, the `List` enumeration only represents a single node, so if you want to have a mutable list, you need a wrapper referencing the chain of `List`s. — SirDarius, Aug 14 '18 at 08:32

Peter Hall · Accepted Answer · 2018-08-14T12:13:05.547

List::prepend must move self because that is literally what is happening. The new head of the list is a new object and the old head is moved onto the heap, making the old variable invalid.

Inside my_prepend you have a mutable reference to self, but then you move its value so that the self reference becomes invalid. Even though it's only invalid temporarily, this is what the message "cannot move out of borrowed content" is complaining about.

One way to get around this is to move self out into a variable and simultaneously replace it with Nil, so that the self reference is never invalid. You can do that with mem::replace:

use std::mem;

fn my_prepend(&mut self, elem: u32) {
    // Move the value of self into head, and leave self as Nil so it isn't invalid
    let head = mem::replace(self, List::Nil);
    // Reassign to self with the prepended value
    *self = head.prepend(elem);
}

How to implement prepend for a linked list without needing to assign to a new variable?

1 Answers1

Linked

Related