< 返回版块

EAHITechnology 发表于 2023-07-06 18:38

Tags:rust, 日报

让我们从 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

社区学习交流平台订阅:

评论区

写评论

还没有评论

1 共 0 条评论, 1 页