单向链表删除节点报错"cannot move out of borrowed content"

Question

我正在做一个单链表。当你删除一个节点时，如果索引匹配，前一个节点的next应该成为当前节点的next（prev->next = curr->next;）和return data。否则，前一个节点成为当前节点，当前节点成为下一个节点（prev = curr; curr = curr->next;）：

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

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

impl LinkedList<i64> {
    fn remove(&mut self, index: usize) -> i64 {
        if self.len() == 0 {
            panic!("LinkedList is empty!");
        }
        if index >= self.len() {
            panic!("Index out of range: {}", index);
        }
        let mut count = 0;
        let mut head = &self.head;
        let mut prev: Option<Box<Node<i64>>> = None;
        loop {
            match head {
                None => {
                    panic!("LinkedList is empty!");
                }
                Some(c) => {
                    // I have borrowed here
                    if count == index {
                        match prev {
                            Some(ref p) => {
                                p.next = c.next;
                                //       ^ cannot move out of borrowed content
                            }
                            _ => continue,
                        }
                        return c.data;
                    } else {
                        count += 1;
                        head = &c.next;
                        prev = Some(*c);
                        //          ^^ cannot move out of borrowed content
                    }
                }
            }
        }
    }

    fn len(&self) -> usize {
        unimplemented!()
    }
}

fn main() {}

error[E0594]: cannot assign to field `p.next` of immutable binding
  --> src/main.rs:31:33
   |
30 |                             Some(ref p) => {
   |                                  ----- consider changing this to `ref mut p`
31 |                                 p.next = c.next;
   |                                 ^^^^^^^^^^^^^^^ cannot mutably borrow field of immutable binding

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:31:42
   |
31 |                                 p.next = c.next;
   |                                          ^ cannot move out of borrowed content

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:40:37
   |
40 |                         prev = Some(*c);
   |                                     ^^ cannot move out of borrowed content

Playground Link 了解更多信息。

我该怎么做？我的方法错了吗？

Answer 1

开始之前，请阅读 Learning Rust With Entirely Too Many Linked Lists。人们认为链表简单因为他们被教导的语言要么不关心你是否引入内存不安全，要么完全剥夺程序员的代理权。

Rust 两者都不做，这意味着您必须考虑以前可能从未想过的事情。

您的代码存在许多问题。你问的 "cannot move out of borrowed content" 已经被许多其他问题很好地涵盖了，所以没有理由重申所有这些好的答案：

TL;DR：您正试图将 next 的所有权从引用中移出；你不能。

p.next = c.next;

您正在尝试修改不可变引用：

let mut head = &self.head;

你允许人们删除一个过去，这对我来说没有意义：

if index >= self.len()

您迭代整棵树不是一次，而是两次，然后再次迭代以执行删除：

if self.len() == 0
if index >= self.len()

与你的算法在 Rust 眼中的缺陷相比，所有这些都显得苍白无力，因为你试图引入 可变别名 。如果您的代码能够编译，您将拥有对 previous 的可变引用以及对 current 的可变引用。但是，您可以从 previous 获得对 current 的可变引用。这会让你打破 Rust 的内存安全保证！

相反，您只能跟踪 current，当找到正确的索引时，将其分解并移动碎片：

fn remove(&mut self, index: usize) -> T {
    self.remove_x(index)
        .unwrap_or_else(|| panic!("index {} out of range", index))
}

fn remove_x(&mut self, mut index: usize) -> Option<T> {
    let mut head = &mut self.head;

    while index > 0 {
        head = match { head }.as_mut() {
            Some(n) => &mut n.next,
            None => return None,
        };
        index -= 1;
    }

    match head.take().map(|x| *x) {
        Some(Node { data, next }) => {
            *head = next;
            Some(data)
        }
        None => None,
    }
}

另请参阅：

Playground Link for more info.

您的其余代码存在许多问题，例如您的 insert 方法的结果与我以前见过的任何结果都不一样。

How I'd write it.

单向链表删除节点报错"cannot move out of borrowed content"

Deleting a node from singly linked list has the error "cannot move out of borrowed content"

linked-list

rust

singly-linked-list