实现一个链表

fn main() {
    fn basic() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);
        // 打印 List { size: 3, head: Some(Node { element: 3, next: Some(Node { element: 2, next: Some(Node { element: 1, next: None }) }) }) }
        // 也就是：3 -> 2 -> 1
        println!("{:?}", list);

        list.pop();
        // 打印 List { size: 2, head: Some(Node { element: 2, next: Some(Node { element: 1, next: None }) }) }
        // 2 -> 1，3 被移除了
        println!("{:?}", list);

        // 看看链表头的值
        // 返回 Some(2)
        println!("{:?}", list.peek());

        // 修改链表头的值，* 为解引用，直接指向引用地址的值，然后修改
        list.peek_mut().map(|node| *node = 222);
        // 看看链表头的值是否被修改了
        // 返回 Some(222)
        println!("{:?}", list.peek());

        // 离开作用域，自动执行 drop，打印两次 drop node
    }

    fn into_iter() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.into_iter();

        // 返回 Vec 数组: [3, 2, 1]
        println!("{:?}", iter.collect::<Vec<i32>>());
    }

    fn iter() {}

    fn iter_mut() {}

    basic();
    // into_iter();
    // iter();
    // iter_mut();
}

/// 节点定义
#[derive(Debug)]
struct Node<T> {
    element: T,    // 存放数据
    next: Link<T>, // 指向下一个节点
}

// 节点之间连接使用 Box，确定大小才能分配内存，节点存在堆中
type Link<T> = Option<Box<Node<T>>>;

/// 链表定义
#[derive(Debug)]
struct List<T> {
    /// 链表长度
    size: usize,
    /// 头节点
    head: Link<T>,
}

impl<T> List<T> {
    fn new() -> List<T> {
        List {
            size: 0,
            head: None,
        }
    }

    fn is_empty(&self) -> bool {
        self.size == 0
    }

    fn size(&self) -> usize {
        self.size
    }

    /// 新节点总是添加到链表的头部，左侧为头部
    fn push(&mut self, element: T) {
        let node = Box::new(Node {
            element,
            // take 会把一个 Option 里的值取出来，留下一个 None 在原来的地方
            next: self.head.take(),
        });

        self.head = Some(node);
        self.size += 1;
    }

    /// 从链表头部移除一个元素并返回
    fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.size -= 1;
            node.element
        })
    }

    /// 返回链表头部元素的不可变引用
    fn peek(&self) -> Option<&T> {
        self.head.as_deref().map(|node| &node.element)
    }

    /// 返回链表头部元素的可变引用
    fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_deref_mut().map(|node| &mut node.element)
    }

    /// 实现链表的迭代功能，链表改变，变成迭代器
    fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    /// 链表不变，返回不可变迭代器
    fn iter(&self) -> Iter<T> {
        Iter {
            next: self.head.as_deref(),
        }
    }

    fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            next: self.head.as_deref_mut(),
        }
    }
}

/// 为链表实现迭代器，链表改变 ，成为迭代器
#[derive(Debug)]
struct IntoIter<T>(List<T>);
impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

/// 实现迭代器，链表不变，得到不可变迭代器
#[derive(Debug)]
struct Iter<'a, T: 'a> {
    next: Option<&'a Node<T>>,
}
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_deref();
            &node.element
        })
    }
}

/// 实现迭代器，链表不变，得到可变迭代器
#[derive(Debug)]
struct IterMut<'a, T: 'a> {
    next: Option<&'a mut Node<T>>,
}
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_deref_mut();
            &mut node.element
        })
    }
}

/// 为链表实现自定义 Drop，用来回收节点
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut link = self.head.take();

        while let Some(mut node) = link {
            println!("drop node");
            // 一直向后取值，取到最后的一个就为 None 了
            link = node.next.take();
        }
    }
}