让我们从 abandon 开始--用 rust 写链表
虽然 Rust 的标准库中已经有了一个LinkedList数据结构，但创建自己的数据结构是了解更多 Rust 的一种有趣的方式。
节点
让我们首先定义我们的 Node 结构来保存模版。我们的 Node 将包含一个数据项，以及 Node 可能存在或可能不存在的上一个和下一个数据项。
/// A node containing a data item and links to previous and next nodes.
struct Node<T> {
data: Rc<T>,
prev: Link<T>,
next: Link<T>,
}
通过将数据项存储在引用计数器指针 ( Rc) 中，在创建新节点时无需克隆或复制数据。 Rust 需要在编译时知道结构的大小，这会导致自引用数据类型出现一些问题。prev如果我们将和字段的类型设置next为Node，我们会收到如下所示的编译器错误消息：
error[E0072]: recursive type `Node` has infinite size
--> src/data_structures/linkedlist.rs:127:1
|
127 | struct Node<T> {
| ^^^^^^^^^^^^^^
128 | data: Rc<T>,
129 | prev: Node<T>,
| ------- recursive without indirection
编译器错误消息为我们提供了如何继续操作的提示。我们正在被推动使用间接，这是谈论指针的另一种方式。 为了处理这个编译器错误，我们需要提供某种指针来代替Node. 我们可以定义一个自定义类型Link作为我们的间接Node包装器：
type Link<T> = Option<Rc<RefCell<Box<Node<T>>>>>;
请注意，因为我们的Link类型使用Rc（引用计数器指针）而不是Arc（原子引用计数指针），所以我们的实现Node不是线程安全的。
节点构造
我们的每个Node方法都将包含在一个块中：impl Node { ... } 这允许我们的方法获取通用类型的数据项T，使我们Node非常灵活！
现在我们知道我们的意志如何Node链接到其他人，我们可以实现该new()方法。每个都Node将开始作为通用类型的数据项保存T，并且不连接到上一个或下一个Node。
/// Creates a new Node containing the given data item. The previous and next
/// node links are set to None.
fn new(data: T) -> Node<T> {
Node {
data: Rc::new(data),
prev: None,
next: None,
}
}
Node setters
我们更新前一个和下一个节点的方法将相当简单。使用我们的引用计数Link，我们只需要在使用我们的设置方法时克隆另一个链接。确保彼此相邻的两个节点正确指向彼此的逻辑将由我们的LinkedList.
/// Updates the previous node.
fn set_prev(&mut self, other: &Link<T>) {
self.prev = other.clone();
}
/// Updates the next node.
fn set_next(&mut self, other: &Link<T>) {
self.next = other.clone();
}
Node getters
与我们的 setter 方法类似Node，我们的 getter 方法只需要克隆下一个或上一个链接。
/// Gets the previous link from the Node via cloning.
fn get_prev(&self) -> Link<T> {
self.prev.clone()
}
/// Gets the next link from the Node via cloning.
fn get_next(&self) -> Link<T> {
self.next.clone()
}
为了获取我们存储的数据Node而不需要克隆或复制数据，我们可以返回引用计数指针的克隆。 为了方便我们的实现，我们将定义一个静态方法来从数据项LinkedList创建新的：LinkT
/// Creates a new Link containing the given data item.
fn new_link(data: T) -> Link<T> {
Some(Rc::new(RefCell::new(Box::new(Node::new(data)))))
}
实现了我们的Node结构及其方法后，我们可以继续我们的 LinkedList 实现。
LinkedList
我们 LinkedList 需要跟踪它的第一个和最后一个节点（头节点和尾节点）及其长度。
/// An implementation of a doubly linked-list. Not thread-safe. Note that the
/// data items contained within nodes cannot be changed after they have been
/// added to the linked-list.
pub struct LinkedList<T> {
head: Link<T>,
tail: Link<T>,
len: usize,
}
虽然我们可以动态计算 的长度LinkedList，但在推送和弹出数据项时跟踪其长度会更有效。
链表构造函数
我们的LinkedList方法将包含在一个块中：impl LinkedList { ... }。与我们的Node方法一样，此实现块将允许我们的LinkedList方法接受通用数据类型的数据项T，使我们的方法LinkedList像我们的方法一样灵活Node！
新的LinkedList开始是空的，没有头节点或尾节点，长度为 0。
/// Creates an empty LinkedList.
pub fn new() -> LinkedList<T> {
LinkedList {
head: None,
tail: None,
len: 0,
}
}
push 方法
我们的 LinkedList push 方法是这个项目开始变得真正有趣的地方！ 按照惯例，“push”本身意味着 push 到 LinkedList 的末尾，而“ push 到前面”正是这个意思。
要将新节点 push 到列表末尾，我们首先创建另一个包含新数据项的节点。 如果 LinkedList 为空，则新 Node 成为新的头和尾。 否则，新节点成为新尾部。 我们的 push() 方法的最后一部分确保旧尾部和新尾部彼此指向，并且 LinkedList 正在跟踪新尾部。
在 Link 实例上调用的 as_ref() 方法允许我们借用 Option 实例中持有的 Rc，而不是取得它的所有权。 借用 Rc 后，我们可以通过对嵌套在 Link 中的 RefCell 调用的borrow_mut() 方法动态借用 Link 中包含的 Node。
/// Pushes the data item to the end of the LinkedList.
pub fn push(&mut self, data: T) {
let new_node: Link<T> = Node::new_link(data);
// Increase the len counter
self.len += 1;
// Handle case for empty list
if self.head.is_none() && self.tail.is_none() {
self.head = new_node.clone();
self.tail = new_node;
return;
}
// Update the tail to point at the new node and connect to the old tail
self.tail.as_ref().unwrap().borrow_mut().set_next(&new_node);
new_node.as_ref().unwrap().borrow_mut().set_prev(&self.tail);
self.tail = new_node;
}
我们对称的最重要的部分LinkedList是我们的push_front()方法最终类似于push()，其中头/尾和上一个/下一个的引用被交换。
/// Pushes the data item to the front of the LinkedList.
pub fn push_front(&mut self, data: T) {
let new_node: Link<T> = Node::new_link(data);
// Increase the len counter
self.len += 1;
// Handle case for empty list
if self.head.is_none() && self.tail.is_none() {
self.head = new_node.clone();
self.tail = new_node;
return;
}
// Update the head to point at the new node and connect to the old head
self.head.as_ref().unwrap().borrow_mut().set_prev(&new_node);
new_node.as_ref().unwrap().borrow_mut().set_next(&self.head);
self.head = new_node;
}
pop 方法
我们从数据项中弹出的值LinkedList取决于它是否包含节点。与我们的推送方法一样，“pop”本身是指从末尾（尾部）删除一个值，LinkedList而“从前面弹出”就是它所说的意思。
如果我们LinkedList至少包含一个Node，我们的pop()方法将返回包含在已删除节点中的值，该值包装在 中的 aSome中Option。否则，它将返回一个None值，表明没有Node被删除。
/// Removes the last node from the LinkedList. Returns Some containing the value
/// from the removed node, otherwise None.
pub fn pop(&mut self) -> Option<Rc<T>> {
// Handle case for empty list
if self.head.is_none() && self.tail.is_none() {
return None;
}
// Update the tail to be the second-last node and return value contained in removed node
let old_tail = self.tail.clone();
self.tail = old_tail.as_ref().unwrap().borrow().get_prev();
self.tail.as_ref().unwrap().borrow_mut().set_next(&None);
let old_data = old_tail.as_ref().unwrap().borrow().get_data();
// Decrease the len counter
self.len -= 1;
Some(old_data)
}
与push 方法一样，pop 方法也是对称的。对于该pop_front()方法，与该方法相比，对 head/tail 和 prev/next 的引用被交换pop()。
/// Removes the first node from the LinkedList. Returns Some containing the
/// value from the removed node, otherwise None.
pub fn pop_front(&mut self) -> Option<Rc<T>> {
// Handle case for empty list
if self.head.is_none() && self.tail.is_none() {
return None;
}
// Update head to be second node and return value contained in removed node
let old_head = self.head.clone();
self.head = old_head.as_ref().unwrap().borrow().get_next();
self.head.as_ref().unwrap().borrow_mut().set_prev(&None);
let old_data = old_head.as_ref().unwrap().borrow().get_data();
// Decrease the len counter
self.len -= 1;
Some(old_data)
}
Checking length
现在检查我们的长度LinkedList非常简单，因为我们一直在推送和弹出节点时跟踪它们。
/// Returns the number of items contained in the LinkedList.
pub fn len(&self) -> usize {
self.len
}
为了完整起见，我们应该实现一个is_empty()方法，因为我们有一个len()方法。如果该字段等于 0，我们的LinkedList将为空。len
/// Checks if the LinkedList is empty.
pub fn is_empty(&self) -> bool {
self.len == 0
}
测试
为代码编写和使用测试用例是一个很好的做法。这样您就可以知道您的实现是否按预期运行，并在代码更改发生重大变化时保持警惕。
下面是一些示例测试方法，我们可以使用它们来检查LinkedList. 这些测试方法绝不是排他性的——您可以随意自己编写更多测试用例。您可以使用命令执行测试方法cargo test。
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_push_back_length() {
let mut new_list = LinkedList::<i32>::new();
let values = (0..10).collect::<Vec<i32>>();
for i in values {
new_list.push(i);
}
assert_eq!(new_list.len(), 10);
}
#[test]
fn test_push_front_length() {
let mut new_list = LinkedList::<i32>::new();
let values = (0..10).collect::<Vec<i32>>();
for i in values {
new_list.push_front(i)
}
assert_eq!(new_list.len(), 10);
}
}
- 源码
- https://cmooneycollett.github.io/2023/07/01/writing-a-linkedlist-in-rust
From 日报小组 Koalr
社区学习交流平台订阅：
评论区
写评论还没有评论