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<Node<T>>
不实现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:
- Ownership
- References and Borrowing
- What are move semantics?
这篇关于Rust中的单链接列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!