初始实现

​ 我们实现的目标是要将整个链表，除了指向链表的指针，其他部分全部放在堆上。我们使用Enum来实现链表结构。

pub struct List {
    head: Link,
} 

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

​ 这样我们只需要申请一个List，之后所有的内容都可以放在堆上，每个Link都可以是空或者一个具体节点的指针。

​ 接下需要为List定义一系列的操作：

impl List {
    pub fn new() -> Self {
        List { head: Link::Empty }
    }
    
    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: std::mem::replace(&mut self.head, Link::Empty),
        });
        
        self.head = Link::More(new_node);
    }
    
    pub fn pop(&mut self) -> Option<i32> {
        match std::mem::replace(&mut self, Link::Empty) {
            Link::Empty => {
                None
            }
            Link::More(node) => {
                self.head = node.next;
                Some(node.elem)
            }
        }
    }
}

​ 这里实现了初始化，压入，弹出三个操作：

• 对于初始化操作，直接申请一个Link::Empty，并将其所有权传出。
• 对于压入操作，需要跟换头节点，并将当前节点设置为下一个节点。这里的replace操作，用将self.head中的值替换为Empty，并将其原本的值取出。这样只需将新申请的节点作为头节点即可。
• pop操作用于将一个头节点取出

​ 最后实现Drop用将申请的空间释放，本来编译器会自己实现Drop方法，不过由于这里作为一个链表，如果直接递归调用，会有爆栈的可能。

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = std::mem::replace(&mut self.HEAD, Link::Empty);
        
        while let Link::More(mut boxed_node) = cur_link {
            cur_link = std::mem::replace(&mut boxed_node.next, Link::Empty);
        }
    }
}

​ 我们使用顺序遍历方式替代递归解决爆栈的问题。

使用Option

pub struct List {
    head: Link,
}

type Link = Option<Box<Node>>;

struct Node {
    elem: i32,
    next: Link,
}

​ 这里定义了类型Link，Option<Box<Node>>和之前的结构实现了一样的结构。

impl List {
    pub fn new() -> Self {
        List { head: None }
    }
    
    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });
        
        self.head = Some(new_node);
    }
    
    pub fn pop(&mut self) -> Option<i32> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.elem
        })
}

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

​ 这里有了Option之后我们不用再使用replace，而是使用take，take可以直接将Option中的内容取出并替换为None。

​ 同时对于

match option {
    None => None, 
    Some(x) => Some(y)
}

​ 可以直接使用map替代，可以将Some替换为Some(y)。

​ 最后再实现泛型，支持更多的类型而不仅仅是i32。以pop为例子：

impl<T> List<T> {
    pub fn pop(&mut self) -> Option<T> {
        self.head = node.next;
        node.elem
    }
}