让我们从 abandon 开始--用 rust 写链表

节点

/// 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>,
}

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

type Link<T> = Option<Rc<RefCell<Box<Node<T>>>>>;

节点构造

/// 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

/// 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

/// 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()
}

/// 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)))))
}

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,
}

链表构造函数

/// Creates an empty LinkedList.
pub fn new() -> LinkedList<T> {
    LinkedList {
        head: None,
        tail: None,
        len: 0,
    }
}

push 方法

/// 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;
}

/// 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 方法

/// 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)
}

/// 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

/// Returns the number of items contained in the LinkedList.
pub fn len(&self) -> usize {
self.len
}

/// Checks if the LinkedList is empty.
pub fn is_empty(&self) -> bool {
self.len == 0
}

测试

#[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

• Rustcc论坛: 支持rss
• 微信公众号：Rust语言中文社区