[数据结构与算法]006 通过链表学Rust之使用Option

介绍

视频地址：https://www.bilibili.com/video/av78062009/
相关源码：https://github.com/anonymousGiga/Rust-link-list
微信公众号：令狐一冲

详细内容

在之前的章节中，我们实现了一个最小的可运行的单链表，然而这仅仅只是一个最小的可运行的链表。从本节开始，我们将创建一个更加完善的链表，这个链表能处理任何类型的元素，并且支持迭代器。

使用Option

在之前的章节中，我们定义Link如下：

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

实际上，我们这是定义了一个Option类似的类型，所以我们可以直接使用Option。下面我们就在我们之前的代码基础上修改为Option。

pub struct List {
	head: Link,
}

type Link = Option<Box<Node>>;

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

impl List {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, elem: i32) {
        let node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(node);
    }

    pub fn pop(&mut self) -> Option<i32> {
        match self.head.take() {
            None => None,
            Some(node) => {
                self.head = node.next;
                Some(node.elem)
            }
        }
    }
}

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

#[cfg(test)]
mod tests {
	use super::List;
	
    #[test]
	fn basics() {
        let mut list = List::new();

        assert_eq!(list.pop(), None);

        list.push(1);
        list.push(2);
        list.push(3);

        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(2));

        list.push(4);
        list.push(5);

        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), Some(4));

        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), None);
    }
}

实际上，我们还可以对pop函数进行改造，如下：

	pub fn pop(&mut self) -> Option<i32> {
    	self.head.take().map(|node| {
    	    self.head = node.next;
    	    node.elem
    	})
	}