从单链表中删除节点时出现错误“无法移出借用的内容”

Question

我正在制作一个单链表。删除节点时，上一个节点的next应成为当前节点的next（prev-

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

操场链接了解更多信息。

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




Answer 1

在你开始学习之前，先去读一读链表太多的书。人们认为链表很容易，因为他们所学的语言要么不在乎是否会导致内存不安全，要么完全剥夺了程序员的代理权。

生锈两者都没有，这意味着你必须考虑一些你以前可能从未想过的事情。

您的代码有许多问题。你问的那个“不能搬出借来的内容”已经被许多其他问题很好地涵盖了，所以没有理由重申所有这些好答案：

• 无法移出借用的内容
• 尝试转移所有权时无法移出借用的内容
• 错误[E0507]：无法移出借用的内容

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

p.next = c.next;

您正试图修改不可变引用：

let mut head = &self.head;

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

if index >= self.len()

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

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

所有这一切与你的算法在锈迹斑斑的人眼中是有缺陷的这一事实相比都相形见绌，因为你试图引入可变的别名。如果您的代码能够编译，您将有一个对previous的可变引用以及对current的可变引用。但是，您可以从previous中获得对当前的可变引用。这将允许您打破Rust的内存安全保证！

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

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,
    }
}

另见：

• 迭代递归结构时无法获得可变引用：不能一次多次借用可变引用
• 如何从Box中获得自有价值？

操场链接了解更多信息。

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

我会怎么写。