如何使用rust实现简单的单链表

struct node<T> {
    data: T,
    next: Option<Node<T>>, // recursive type `Node` has infinite size
}

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

/// 单链表节点
#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

/// 单链表
#[derive(Debug)]
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(data: T) -> Self {
        Self { data: data, next: None }
    }
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    /// 在链表头部插入节点(头插法push front)
    fn prepend(&mut self, data: T) -> &mut Self {
        // 从传入数据构建要插入的节点
        let mut new_node = Box::new(Node::new(data));
        match self.head {
            // 当前链表为空时, 插入的节点直接作为头节点
            None => self.head = Some(new_node),
            // 当前链表非空时, 插入的节点作为新的头节点插入到原来的头结点前面
            Some(_) => {
                // 调用Option的take方法取出Option中的头结点(take的内部实现是mem::replace可避免内存拷贝), 作为新插入节点的下一个节点
                new_node.next = self.head.take();
                // 将新插入的节点作为链表的头节点
                self.head = Some(new_node);
            }
        }
        self
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    print!("{ll:?}"); // LinkedList { head: Some(Node { data: 1, next: Some(Node { data: 2, next: Some(Node { data: 3, next: Some(Node { data: 4, next: Some(Node { data: 5, next: None }) }) }) }) }) }
}

use std::fmt::Display;

......

impl<T: Display> Display for LinkedList<T> {
    fn fmt(&self, f: &mut std::fmt::FORMatter<'_>) -> std::fmt::Result {
        if self.head.is_none() {
            // 如果链表为空, 只打印None
            write!(f, "None\n")?;
        } else {
            // 下面将遍历链表, 因为只是打印, 能获取链表各个节点的数据就行, 所以不需要获取所有权
            let mut next = self.head.as_ref();
            while let Some(node) = next {
                write!(f, "{} -> ", node.data)?;
                next = node.next.as_ref();
            }
            write!(f, "None\n")?;
        }
        Ok(())
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    print!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
}

impl<T> LinkedList<T> {
    ......

    /// 翻转链表
    fn reverse(&mut self) {
        let mut prev = None; // 记录遍历链表时的前一个节点
        while let Some(mut node) = self.head.take() {
            self.head = node.next;
            node.next = prev;
            prev = Some(node);
        }
        self.head = prev;
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    println!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
    ll.reverse(); // 5 -> 4 -> 3 -> 2 -> 1 -> None
    println!("{ll}");
}

Node* new_node = create_new_node(v);
new_node->next = head;
head = new_node;