How to implement setting value of a specific element in linked list?

Question

I'm learning Rust by implementing a single linked list. I've followed the 2nd chapter in Learning Rust With Entirely Too Many Linked Lists. I want to implement a function to set value of a specific element in the list by its index. Here's my code so far:

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

impl List {
    /// Replaces the element at the specified position in this list with the specified element.
    pub fn set(&mut self, index: usize, elem: i32) -> Result<(), &str> {
        // Start from the first node where index is 0
        let mut id: usize = 0;
        let mut curr_node: &Link = &self.head;
        while let Link::More(mut node) = curr_node {
            curr_node = &node.next;
            id += 1;
            if id == index {
                node.elem = elem;
                break;
            }
        }
        if id < index {
            return Err("Invalid index");
        }
        Ok(())
    }
}

The compiler emits 2 compile errors:

error[E0507]: cannot move out of `curr_node.0` which is behind a shared reference
  --> src/lib.rs:21:42
   |
21 |         while let Link::More(mut node) = curr_node {
   |                              --------    ^^^^^^^^^
   |                              |
   |                              data moved here
   |                              move occurs because `node` has type `Box<Node>`, which does not implement the `Copy` trait

error[E0597]: `node.next` does not live long enough
  --> src/lib.rs:22:25
   |
21 |         while let Link::More(mut node) = curr_node {
   |                                          --------- borrow later used here
22 |             curr_node = &node.next;
   |                         ^^^^^^^^^^ borrowed value does not live long enough
...
28 |         }
   |         - `node.next` dropped here while still borrowed

Playground link

How should I implement this correctly?

cadolphs · Accepted Answer · 2021-10-07 15:33:08Z

When I saw the title of your question I immediately wanted to post a link to that "Learning Rust via too many linked lists" book, but I see you're already on to that :)

Ah, it's all so very messy, isn't it? Well in your case the solution is quite simple.

First, the type of curr_node should be &mut Link and thus needs to also be initialized with &mut self.head because we need a mutable reference.

Next, in your while loop you are using pattern matching to bind the value of the node to your variable node. However, pattern matching by default moves the matched value into the variable, and that's why the compiler complains: You can't just up and move elements out of a struct.

Instead of moving, we just want to grab a reference to the node, so we say while let Link::More(ref mut node) = curr.node { ... }

and then finally curr_node = &mut node.next because again we need a mutable reference.

Playground Link

Collectives™ on Stack Overflow

How to implement setting value of a specific element in linked list?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related