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

/// 單鏈表節(jié)點(diǎn)
#[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 }
? ? }

? ? /// 在鏈表頭部插入節(jié)點(diǎn)(頭插法push front)
? ? fn prepend(&mut self, data: T) -> &mut Self {
? ? ? ? // 從傳入數(shù)據(jù)構(gòu)建要插入的節(jié)點(diǎn)
? ? ? ? let mut new_node = Box::new(Node::new(data));
? ? ? ? match self.head {
? ? ? ? ? ? // 當(dāng)前鏈表為空時(shí), 插入的節(jié)點(diǎn)直接作為頭節(jié)點(diǎn)
? ? ? ? ? ? None => self.head = Some(new_node),
? ? ? ? ? ? // 當(dāng)前鏈表非空時(shí), 插入的節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)插入到原來(lái)的頭結(jié)點(diǎn)前面
? ? ? ? ? ? Some(_) => {
? ? ? ? ? ? ? ? // 調(diào)用Option的take方法取出Option中的頭結(jié)點(diǎn)(take的內(nèi)部實(shí)現(xiàn)是mem::replace可避免內(nèi)存拷貝), 作為新插入節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ? ? new_node.next = self.head.take();
? ? ? ? ? ? ? ? // 將新插入的節(jié)點(diǎn)作為鏈表的頭節(jié)點(diǎn)
? ? ? ? ? ? ? ? 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 {
? ? ? ? ? ? // 下面將遍歷鏈表, 因?yàn)橹皇谴蛴? 能獲取鏈表各個(gè)節(jié)點(diǎn)的數(shù)據(jù)就行, 所以不需要獲取所有權(quán)
? ? ? ? ? ? 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> {
? ? ......

? ? /// 翻轉(zhuǎn)鏈表
? ? fn reverse(&mut self) {
? ? ? ? let mut prev = None; // 記錄遍歷鏈表時(shí)的前一個(gè)節(jié)點(diǎn)
? ? ? ? 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;