从单链列表中删除节点的错误是“无法移出借用的内容". [英] Deleting a node from singly linked list has the error "cannot move out of borrowed content"
问题描述
我正在制作一个单链接列表.删除节点时，前一个节点的 next 应该成为当前节点的 next ( prev-> next = curr-> next; )，如果索引匹配，则返回 data .否则，前一个节点将成为当前节点，而当前节点将成为下一个节点( prev = curr; curr = curr-> next; ):
I am making a singly-linked list. When you delete a node, the previous node's next should become the current node's next (prev->next = curr->next;) and return data if the index matches. Otherwise, the previous node becomes the current node and the current node becomes the next node (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
游乐场链接有关更多信息.
我该怎么做?我的方法不对吗?
How can I do this? Is my approach wrong?
推荐答案
在开始之前，请先阅读使用过多的链表学习 Rust.人们认为链表很简单，因为他们所学的语言要么不在乎是否引入了内存不安全性，要么完全从程序员手中夺走了这种代理权.
Before you start, go read Learning Rust With Entirely Too Many Linked Lists. People think that linked lists are easy because they've been taught them in languages that either don't care if you introduce memory unsafety or completely take away that agency from the programmer.
Rust都不做，这意味着您必须考虑以前可能从未想到的事情.
Rust does neither, which means that you have to think about things you might never have thought of before.
您的代码存在许多问题.您所问的无法移出借用的内容"这个问题已经被许多其他问题很好地涵盖了，因此没有理由重申所有这些好的答案:
There are a number of issues with your code. The one that you ask about, "cannot move out of borrowed content" is already well-covered by numerous other questions, so there's no reason to restate all those good answers:
TL; DR:您正试图将 next 的所有权从引用中移出；你不能.
TL;DR: You are attempting to move ownership of next from out of a reference; you cannot.
p.next = c.next;
您正在尝试修改不可变的引用:
You are attempting to modify an immutable reference:
let mut head = &self.head;
您允许人们删除过去的结尾，这对我来说没有意义:
You allow for people to remove one past the end, which doesn't make sense to me:
if index >= self.len()
在遍历整个树一次，但两次遍历，然后再次遍历以执行删除操作:
You iterate the entire tree not once, but twice before iterating it again to perform the removal:
if self.len() == 0
if index >= self.len()
与您的算法在Rust眼中存在缺陷(因为您尝试引入可变别名)相比，所有这些都相形见pale.如果您的代码能够编译，则可以对 previous 进行可变引用，而对 current 进行可变引用.但是，您可以从 previous 获取对 current 的可变引用.这将使您违反Rust的内存安全保证！
All of that pales in comparison to the fact that your algorithm is flawed in the eyes of Rust because you attempt to introduce mutable aliasing. If your code were able to compile, you'd have a mutable reference to previous as well as a mutable reference to current. However, you can get a mutable reference to current from previous. This would allow you to break Rust's memory safety guarantees!
相反，您只能跟踪 current ，并且当找到正确的索引时，请将其拆开并移动:
Instead, you can only keep track of current and, when the right index is found, break it apart and move the pieces:
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,
}
}
另请参阅:
游乐场链接有关更多信息.
您的其余代码有很多问题，例如您的 insert 方法的结果不同于我以前见过的任何事实.
There are numerous problems with the rest of your code, such as the fact that the result of your insert method is unlike any I've ever seen before.
我怎么写.
这篇关于从单链列表中删除节点的错误是“无法移出借用的内容".的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
