Rust 中的单链表 [英] Singly-Linked List in Rust
问题描述
我最近一直在尝试自学一些 Rust,并想通过实现一个简单的链表来练习一下.我从 Rust 库的链表中获得了一些灵感,并尝试复制我已经理解的部分.此外,我决定暂时将其设为单链接.
I've been trying to teach myself some Rust lately and wanted to practice a bit by implementing a simple linked list. I took some inspiration from the Rust library's linked list and tried to replicate the parts I already understood. Also I decided to make it singly-linked for now.
struct Node<T> {
element: T,
next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
fn new(element: T) -> Self {
Node {
element: element,
next: None,
}
}
fn append(&mut self, element: Box<Node<T>>) {
self.next = Some(element);
}
}
pub struct LinkedList<T> {
head: Option<Box<Node<T>>>,
tail: Option<Box<Node<T>>>,
len: u32,
}
impl<T> LinkedList<T> {
pub fn new() -> Self {
head: None,
tail: None,
len: 0,
}
pub fn push(&mut self, element: T) {
let node: Box<Node<T>> = Box::new(Node::new(element));
match self.tail {
None => self.head = Some(node),
Some(mut ref tail) => tail.append(node),
}
self.tail = Some(node);
self.len += 1;
}
pub fn pop(&mut self) -> Option<T> {
//not implemented
}
pub fn get(&self, index: u32) -> Option<T> {
//not implemented
}
}
这是我到目前为止所得到的;据我了解,这段代码的问题在于 Box
不能有多个对它的引用,以保持内存安全.
This is what I've got so far; from what I understand, the problem with this code is that the Box
can not have more than one reference to it in order to preserve memory safety.
所以当我将列表头设置为节点时
So when I set the list head to node in
None => self.head = Some(node),
然后我不能继续设置
self.tail = Some(node);
后来,到目前为止,我的理解是否正确?这样做的正确方法是什么?我是否必须像在库中一样使用 Shared
或者是否有一种方法可以利用 Box
或其他类型?
later, am I correct so far in my understanding? What would be the correct way to do this? Do I have to use Shared
like in the library or is there a way in which the Box
or some other type can be utilized?
推荐答案
您的问题是您尝试在移动值 (node
) 后使用它;由于 Box
没有实现 Copy
,当你在 match
表达式中使用它时:
Your issue is that you are attempting to use a value (node
) after having moved it; since Box<Node<T>>
does not implement Copy
, when you use it in the match
expression:
match self.tail {
None => self.head = Some(node),
Some(ref mut tail) => tail.append(node),
}
node
被移动到 self.head
或 self.tail
并且以后不能再使用.除了阅读强制性的学习 Rust 与完全太多的链接列表 要了解在 Rust 中实现链表的不同方式,我建议您首先在 Rust 的基本概念领域多做一些研究,尤其是:
node
is moved either to self.head
or to self.tail
and can no longer be used later. Other than reading the obligatory Learning Rust With Entirely Too Many Linked Lists to see the different ways in which you can implement linked lists in Rust, I suggest that you first do some more research in the field of Rust's basic concepts, especially:
这篇关于Rust 中的单链表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!