10. 智能指针篇¶

use std::mem;

// 链表节点：要么是空（Nil），要么是"值 + 指向下一个节点的 Box"
// Box 是堆分配：Node 大小不定，用 Box 固定大小可递归定义
enum Node {
    Nil,
    Cons(i32, Box<Node>),   // Box 持有一个 Node（唯一所有权）
}

struct LinkedList {
    head: Node,
}

impl LinkedList {
    fn new() -> LinkedList {
        LinkedList { head: Node::Nil }
    }

    // 从头部插入：mem::replace 取出旧头，换成新头
    fn push_front(&mut self, value: i32) {
        // mem::replace 把 self.head 替换成 Nil，并返回旧值
        // 绕过"不能从借用中 move 出值"的限制
        let old_head = mem::replace(&mut self.head, Node::Nil);
        self.head = Node::Cons(value, Box::new(old_head));   // 旧头变成新头的 next
    }

    // 从尾部插入：while let 走到最后一个节点
    fn push_back(&mut self, value: i32) {
        let mut current = &mut self.head;
        // while let：只要 current 是 Cons 就继续往前走
        // next 是 &mut Box<Node>，可以再次模式匹配（NLL 允许）
        while let Node::Cons(_, next) = current {
            current = next;   // 走到下一个节点
        }
        // 现在 current 指向 Nil，把它替换成新节点
        *current = Node::Cons(value, Box::new(Node::Nil));
    }

    fn len(&self) -> usize {
        let mut count = 0;
        let mut current = &self.head;
        while let Node::Cons(_, next) = current {
            count += 1;
            current = next;
        }
        count
    }

    fn print(&self) {
        let mut current = &self.head;
        while let Node::Cons(v, next) = current {
            print!("{} ", v);
            current = next;
        }
        println!();
    }
}

fn main() {
    let mut list = LinkedList::new();
    list.push_front(1);
    list.push_front(2);
    list.push_back(3);
    list.print();          // 2 1 3
    println!("长度：{}", list.len());   // 3
}

use std::rc::Rc;

// 用 Rc 代替 Box：允许多个节点共享同一个尾部
// Rc = Reference Counting：每多一个持有者计数 +1，计数归零才释放
enum SharedNode {
    Nil,
    Cons(i32, Rc<SharedNode>),
}

fn main() {
    // tail 被两个链表共享
    let tail = Rc::new(SharedNode::Cons(3, Rc::new(SharedNode::Nil)));

    // Rc::clone 不是深拷贝！只是计数 +1，数据只有一份
    let list1 = SharedNode::Cons(1, Rc::clone(&tail));
    let list2 = SharedNode::Cons(2, Rc::clone(&tail));

    // tail 被 list1 和 list2 各持有一份引用 → 计数为 2
    println!("tail 强引用计数：{}", Rc::strong_count(&tail));  // 2

    // 如果换成 Box：tail 被移进 list1 后 list2 就无法再用了
    // （Box 是单所有权，不能有第二个持有者）
}

use std::cell::RefCell;
use std::rc::{Rc, Weak};

struct Node {
    value: i32,
    // 前→后：强引用（计数）。Rc 让多个节点能共享指向同一个后续节点
    next: Option<Rc<RefCell<Node>>>,
    // 后→前：弱引用（不计数）。Weak 不增加计数，防止循环引用
    prev: Option<Weak<RefCell<Node>>>,
}

impl Node {
    fn new(value: i32) -> Rc<RefCell<Self>> {
        // Rc 提供共享，RefCell 提供内部可变性（borrow_mut 修改字段）
        Rc::new(RefCell::new(Self {
            value,
            next: None,
            prev: None,
        }))
    }
}

struct DoublyList {
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>,
}

impl DoublyList {
    fn new() -> Self {
        Self {
            head: None,
            tail: None,
        }
    }

    fn push_front(&mut self, value: i32) {
        let new_node = Node::new(value);
        match &self.head {
            Some(old_head) => {
                // 新节点的 next 指向旧头（强引用）
                new_node.borrow_mut().next = Some(Rc::clone(old_head));
                // 旧头的 prev 指向新节点（弱引用，不计数）
                old_head.borrow_mut().prev = Some(Rc::downgrade(&new_node));
                self.head = Some(new_node);
            }
            None => {
                // 空链表：head 和 tail 都指向新节点
                self.head = Some(Rc::clone(&new_node));
                self.tail = Some(new_node);
            }
        }
    }

    fn pop_front(&mut self) -> Option<i32> {
        // take() 拿走 head 留 None；? 在 Option 上遇到 None 直接返回
        let head = self.head.take()?;
        match head.borrow_mut().next.take() {
            Some(next) => {
                // 新头不再指旧头（旧头即将释放）
                next.borrow_mut().prev = None;
                self.head = Some(next);
            }
            None => {
                // 删完链表空了
                self.head = None;
                self.tail = None;
            }
        }
        Some(head.borrow_mut().value)   // borrow 只读访问 value
    }

    fn print(&self) {
        let mut cur = self.head.clone();
        while let Some(node) = cur {
            print!("{}", node.borrow().value);
            cur = node.borrow().next.clone();   // clone Rc 推进循环
        }
        println!();
    }
}

fn main() {
    let mut list = DoublyList::new();
    list.push_front(1);
    list.push_front(2);
    list.push_front(3);
    list.print();                                  // 321
    println!("{:?}", list.pop_front().unwrap());   // 3
    list.print();                                  // 21

    // Weak 悬垂演示：弱引用不阻止数据被释放
    let a = Rc::new(10);
    let weak = Rc::downgrade(&a);
    println!("{:?}", weak.upgrade());   // Some(10)：强引用还活着

    drop(a);   // 手动释放最后一个强引用
    println!("{:?}", weak.upgrade());   // None：upgrade 不会复活已释放的数据
}