Rust实现链表day4——一个安全但是不好的双链队列

前言#

昨天我们完善了单链栈，今天我们开始实现一个双向链表的旅程！

一个不太好但是安全的双链队列（A Bad but Safe Doubly-Linked Deque）#

我们前面实现了一个不可变的持久性链表，现在我们来将它变成可变的，也就是使用内部可变的方式，另外我们还准备将它拓展成一个双链的队列（张emo: 是不是很大胆？.jpg）。

老规矩，src下搞一个fourth.rs的文件并在lib.rs中引入。

layout#

上来自然就是调整结构，因为当前是不可变的，不能满足要求。

这个时候就需要使用到RefCell，也就是内部可变，它的核心是下面俩方法：

正如它俩的名字一样，就是返回一个内部的引用&和可变引用&mut。

不过他俩是在runtime的，当然，还是得满足rust定义的借用规则，borrow_mut仅只能有一个，如果有问题，会直接panic终止程序。

pub struct List<T> {
    head: Option<Rc<RefCell<Node<T>>>>
}

现在我们支持可变了，然后我们来拓展下我们的类型,让它变双向

所谓双向，就是当前节点保有前一个节点的指针的同时，还保有后一个节点的指针。

use std::rc::Rc;
use std::cell::RefCell;

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>,
}

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
    prev: Link<T>,
}

这个代码编译是没问题的，但是有一个致命的问题，这里先不说，等会就会遇到了。

构造#

然后我们来补充下一些方法：

new还是那样，只是多一个tail

impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }
}

然后我们来实现push，因为我们现在有头尾两个入口♂，所以我们得写两个方法用来添加节点：

pub fn push_front(&mut self, elem: T) {
    // new node needs +2 links, everything else should be +0
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            // non-empty list, need to connect the old_head
            old_head.prev = Some(new_head.clone()); // +1 new_head
            new_head.next = Some(old_head);         // +1 old_head
            self.head = Some(new_head);             // +1 new_head, -1 old_head
            // total: +2 new_head, +0 old_head -- OK!
        }
        None => {
            // empty list, need to set the tail
            self.tail = Some(new_head.clone());     // +1 new_head
            self.head = Some(new_head);             // +1 new_head
            // total: +2 new_head -- OK!
        }
    }
}

如果是空的，那么需要同时初始化头尾两个指针，如果不是，那我们只需要维护头即可，将当前的头的prev指向新的节点，将新的节点的next指向头，然后将head指针指向这个新的节点，也就是更新头的指向。

不过这个代码报错了

cargo build

error[E0609]: no field `prev` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:39:26
   |
39 |                 old_head.prev = Some(new_head.clone()); // +1 new_head
   |                          ^^^^ unknown field

error[E0609]: no field `next` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:40:26
   |
40 |                 new_head.next = Some(old_head);         // +1 old_head
   |                          ^^^^ unknown field

因为new_head和old_head是一个Rc<RefCell<Node<T>>>的类型，并不能直接访问它内部的数据。

回看我们之前的代码，是可以直接访问的，但是现在因为RefCell的问题，我们失去了直接访问内部数据的资格！

貌似前面还没描述过RefCell，只是说了它可以内部可变。。

A mutable memory location with dynamically checked borrow rules

具有动态检查借用规则的可变内存位置。

有点难懂，但是关键字我们认得：动态，借用规则，可变，内存位置

（为什么搭配在一起就看不懂了）

动态意味着是runtime，编译器管不了（当然，管不了是管不了，该panic还是会panic）
借用规则意味着我们可以通过它拿到内部数据的借用，可变和不可变都可以（符合借用规则）
内存位置，也就是说这是个指针

我们可以更具体点：module-level documentation

简单地说就是一个共享的可变容器（shareable mutable containers）

其实RefCell<T>还有一个兄弟Cell<T>，他俩都是差不多，提供内部可变性，区别在于Cell<T>需要T实现Copy，而不能实现Copy的类型只能使用RefCell<T>。

换句话说，Cell<T>里的T实现了Copy,那么它实际上可以直接copy一份数据，所以它的俩方法非常直接，get和set。没有引用参与。

回到RefCell<T>，这货是使用生命周期的规则来实现动态借用（dynamic borrowing）。

那么什么时候需要使用到内部可变呢？一般有以下三种：

将继承的可变性根引入共享类型。（Introducing inherited mutability roots to shared types. ）
实现逻辑上不可变(logically-immutable)的方法细节时（？）
可变实现Clone

共享智能指针类型（包括 Rc 和 Arc）提供可在多方之间克隆和共享的容器。由于包含的值可能是多重别名的，因此它们只能作为共享引用借用，而不能作为可变引用借用。没有单元，就不可能在共享框内改变数据！

一般我们都是把一个可变引用放到RefCell<T>里面来重写它的可变性。

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    shared_map.borrow_mut().insert("africa", 92388);
    shared_map.borrow_mut().insert("kyoto", 11837);
    shared_map.borrow_mut().insert("piccadilly", 11826);
    shared_map.borrow_mut().insert("marbles", 38);
}

最后说一下，这货是单线程的，多线程是Mutex。

Rc和RefCell搭配，Arc和Mutex搭配。

ok，回到我们的代码

pub fn push_front(&mut self, elem: T) {
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            old_head.borrow_mut().prev = Some(new_head.clone());
            new_head.borrow_mut().next = Some(old_head);
            self.head = Some(new_head);
        }
        None => {
            self.tail = Some(new_head.clone());
            self.head = Some(new_head);
        }
    }
}

这回就没问题了。

分解(Breaking Down)#

有进就有出，有push_front自然就有pop_front。逻辑差不多

pub fn pop_front(&mut self) -> Option<T> {
    // need to take the old head, ensuring it's -2
    self.head.take().map(|old_head| {                         // -1 old
        match old_head.borrow_mut().next.take() {
            Some(new_head) => {                               // -1 new
                // not emptying list
                new_head.borrow_mut().prev.take();            // -1 old
                self.head = Some(new_head);                   // +1 new
                // total: -2 old, +0 new
            }
            None => {
                // emptying list
                self.tail.take();                             // -1 old
                // total: -2 old, (no new)
            }
        }
        old_head.elem
    })
}

但是这里有点问题，old_head没进入到数据里，还是之前RefCell的问题。

你的第一想法应该是如下：

old_head.elem => old_head.borrow_mut().elem

但是这里还有个问题，那就是这个数据的Copy，我们是返回Option<T>，泛型是不可能支持Copy的，所以这么改是没办法跑通的，喜提报错如下：

cargo build

error[E0507]: cannot move out of borrowed content
  --> src/fourth.rs:64:13
   |
64 |             old_head.borrow_mut().elem
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot move out of borrowed content

借给你的，结果你直接戴着跑了？？（阿三行为）

但是你这是废弃的节点啊，我拿你数据怎么了我？（理直气壮）

你说废弃就废弃啊，我不用其它人也不用？（别忘了Rc）

我不管，我就是要拿（突然掏出小镰刀：RefCell::into_inner，这个方法可以直接拿到内部的T，我已经受够繁文缛节了.jpg）

暗月骑士（编译器）出警！（太dark啦~）

> cargo build

error[E0507]: cannot move out of an `Rc`
  --> src/fourth.rs:64:13
   |
64 |             old_head.into_inner().elem
   |             ^^^^^^^^ cannot move out of an `Rc`

但说正经的，如果真的想要呢？

这个时候只能是尝试，如果拿不到只能是返回None（?）

Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem

还是try_unwrap，不过我们这里还多了个ok，这个方法简单地说就是将Result<T, E>变成Option<T>，否则为None。至于为什么不能直接unwrap Result<T, E>，因为我们的类型没有实现Debug，至于Result为什么要求要实现Debug，因为要支持错误输出。

然后我们从我们之前的代码中偷几个测试用例，然后微调下：

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop_front(), None);

        // Populate list
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_front(4);
        list.push_front(5);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);
    }
}

搞定（了吗）（Nailed it）

其实我们这里还是有问题的，存在两个引用计数以上，我们就拿不到pop_front出来的数据。

drop也是比较复杂的事情，因为可能会遇到循环引用的问题，目前我们先简单的实现一个

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

让节点的计数 - 1。

要珍惜编译的报错，因为接下来编译成功也不一定可以运行成功π_π。。

Peeking#

我们现在实现了pop_front和push_front，那么接下来自然轮到peek_front，应该还算是简单。

对...对吗？（戴佳伟.jpg）

回想一下，我们要的效果是获取头节点的数据引用

pub fn peek_front(&self) -> Option<&T> {
    self.head.as_ref().map(|node| {
        // BORROW!!!!
        &node.borrow().elem
    })
}

但是你会遇到一个奇怪的报错：

cargo build

error[E0515]: cannot return value referencing temporary value
  --> src/fourth.rs:66:13
   |
66 |             &node.borrow().elem
   |             ^   ----------^^^^^
   |             |   |
   |             |   temporary value created here
   |             |
   |             returns a value referencing data owned by the current function

returns a value referencing data owned by the current function

有点摸不着头脑，为了解决这个问题，我们得会看下borrow方法：

fn borrow<'a>(&'a self) -> Ref<'a, T>
fn borrow_mut<'a>(&'a self) -> RefMut<'a, T>

这里有两个类型Ref和RefMut，它俩大部分时候都和&、&mut差不多，但是不完全一样。

其实我们之前学过这俩，这里权当复习，Ref实现了Deref，而RefMut实现了DerefMut, 所以我们可以通过*的方式去进入数据内部，这和&以及&mut表现是一致的。

但是，这就导致生命周期不一致问题，我们通过borrow().elem拿到的数据的生命周期和Ref是一致的，而不是RefCell<T>。

所以会有上面这个问题，知道原因了，那我们咋整呢？

简单，让borrow的内容和node生命周期一致就行，我们直接把Ref抛出去

use std::cell::{Ref, RefCell};
pub fn peek_front(&self) -> Option<Ref<T>> {
    self.head.as_ref().map(|node| {
        node.borrow()
    })
}

当然，这是有问题的：

> cargo build

error[E0308]: mismatched types
  --> src/fourth.rs:64:9
   |
64 | /         self.head.as_ref().map(|node| {
65 | |             node.borrow()
66 | |         })
   | |__________^ expected type parameter, found struct `fourth::Node`
   |
   = note: expected type `std::option::Option<std::cell::Ref<'_, T>>`
              found type `std::option::Option<std::cell::Ref<'_, fourth::Node<T>>>`

类型不对，我们borrow()返回的类型是Ref<Node<T>>(&其实是ref，因为用了as_ref)。

这个也简单，和Option::map类似，Ref::map也是可以将T类型变成U：

map<U, F>(orig: Ref<'b, T>, f: F) -> Ref<'b, U>
    where F: FnOnce(&T) -> &U,
          U: ?Sized

正好可以用来将我们的Ref<Node<T>>变成Ref<T>。

pub fn peek_front(&self) -> Option<Ref<T>> {
    self.head.as_ref().map(|node| {
        Ref::map(node.borrow(), |node| &node.elem)
    })
}

搞个测试用例：

#[test]
fn peek() {
    let mut list = List::new();
    assert!(list.peek_front().is_none());
    list.push_front(1); list.push_front(2); list.push_front(3);

    assert_eq!(&*list.peek_front().unwrap(), &3);
}

跑的通！

对称垃圾（Symmetric Junk）#

既然front的都搞完了，我们接下来就来同步back的，逻辑基本上一样的

use std::cell::{Ref, RefCell, RefMut};

//..

pub fn push_back(&mut self, elem: T) {
    let new_tail = Node::new(elem);
    match self.tail.take() {
        Some(old_tail) => {
            old_tail.borrow_mut().next = Some(new_tail.clone());
            new_tail.borrow_mut().prev = Some(old_tail);
            self.tail = Some(new_tail);
        }
        None => {
            self.head = Some(new_tail.clone());
            self.tail = Some(new_tail);
        }
    }
}

pub fn pop_back(&mut self) -> Option<T> {
    self.tail.take().map(|old_tail| {
        match old_tail.borrow_mut().prev.take() {
            Some(new_tail) => {
                new_tail.borrow_mut().next.take();
                self.tail = Some(new_tail);
            }
            None => {
                self.head.take();
            }
        }
        Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
    })
}

pub fn peek_back(&self) -> Option<Ref<T>> {
    self.tail.as_ref().map(|node| {
        Ref::map(node.borrow(), |node| &node.elem)
    })
}

pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
    self.tail.as_ref().map(|node| {
        RefMut::map(node.borrow_mut(), |node| &mut node.elem)
    })
}

pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
    self.head.as_ref().map(|node| {
        RefMut::map(node.borrow_mut(), |node| &mut node.elem)
    })
}

以及测试用例

#[test]
fn basics() {
    let mut list = List::new();

    // Check empty list behaves right
    assert_eq!(list.pop_front(), None);

    // Populate list
    list.push_front(1);
    list.push_front(2);
    list.push_front(3);

    // Check normal removal
    assert_eq!(list.pop_front(), Some(3));
    assert_eq!(list.pop_front(), Some(2));

    // Push some more just to make sure nothing's corrupted
    list.push_front(4);
    list.push_front(5);

    // Check normal removal
    assert_eq!(list.pop_front(), Some(5));
    assert_eq!(list.pop_front(), Some(4));

    // Check exhaustion
    assert_eq!(list.pop_front(), Some(1));
    assert_eq!(list.pop_front(), None);

    // ---- back -----

    // Check empty list behaves right
    assert_eq!(list.pop_back(), None);

    // Populate list
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    // Check normal removal
    assert_eq!(list.pop_back(), Some(3));
    assert_eq!(list.pop_back(), Some(2));

    // Push some more just to make sure nothing's corrupted
    list.push_back(4);
    list.push_back(5);

    // Check normal removal
    assert_eq!(list.pop_back(), Some(5));
    assert_eq!(list.pop_back(), Some(4));

    // Check exhaustion
    assert_eq!(list.pop_back(), Some(1));
    assert_eq!(list.pop_back(), None);
}

#[test]
fn peek() {
    let mut list = List::new();
    assert!(list.peek_front().is_none());
    assert!(list.peek_back().is_none());
    assert!(list.peek_front_mut().is_none());
    assert!(list.peek_back_mut().is_none());

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

    assert_eq!(&*list.peek_front().unwrap(), &3);
    assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
    assert_eq!(&*list.peek_back().unwrap(), &1);
    assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
}

Iteration#

迭代这块在搞懂RefCell和Rc等一系列知识之后现在反而简单了一些

IntoIter#

这货简单，就是从头pop，直接调用内部的pop_front即可。

pub struct IntoIter<T>(List<T>);

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop_front()
    }
}

好像少了什么，诶，我们是双向队列诶，为什么只有从头next的。

因为我们是实现的Iterator，它只有一个next方法，当然也有双向的DoubleEndedIterator，它多一个next_back的方法。

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

测试用例：

#[test]
fn into_iter() {
    let mut list = List::new();
    list.push_front(1); list.push_front(2); list.push_front(3);

    let mut iter = list.into_iter();
    assert_eq!(iter.next(), Some(3));
    assert_eq!(iter.next_back(), Some(1));
    assert_eq!(iter.next(), Some(2));
    assert_eq!(iter.next_back(), None);
    assert_eq!(iter.next(), None);
}

然后轮到Iter

Iter#

这货还是非常麻烦。。。

我们的先来将引用类型变成Ref

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = Ref<'a, T>;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node_ref| {
            self.0 = node_ref.next.as_ref().map(|head| head.borrow());
            Ref::map(node_ref, |node| &node.elem)
        })
    }
}

然后毫无意外的遇到问题：

cargo build

error[E0521]: borrowed data escapes outside of closure
   --> src/fourth.rs:155:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` is declared here, outside of the closure body
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   -------- borrow is only valid in the closure body
    |             |
    |             reference to `node_ref` escapes the closure body here

error[E0505]: cannot move out of `node_ref` because it is borrowed
   --> src/fourth.rs:156:22
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- lifetime `'1` appears in the type of `self`
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ------   -------- borrow of `node_ref` occurs here
    |             |
    |             assignment requires that `node_ref` is borrowed for `'1`
156 |             Ref::map(node_ref, |node| &node.elem)
    |                      ^^^^^^^^ move out of `node_ref` occurs here

闭包中的Ref试图逃逸
所有权问题，试图引用失去资格的家伙

我们抛出的ref的生命周期和node_ref一样，但是这货活的不够长，等会可能被销毁，所以我们得想个办法把数据拆出来，而不是使用Ref包裹，因为Ref生命周期不够长。

那么我们就不能使用map，幸运的是这里还有个map_split的方法：

pub fn map_split<U, V, F>(orig: Ref<'b, T>, f: F) -> (Ref<'b, U>, Ref<'b, V>) where
    F: FnOnce(&T) -> (&U, &V),
    U: ?Sized,
    V: ?Sized,

居然可以拆分两个Ref。

我们来试下：

fn next(&mut self) -> Option<Self::Item> {
    self.0.take().map(|node_ref| {
        let (next, elem) = Ref::map_split(node_ref, |node| {
            (&node.next, &node.elem)
        });

        self.0 = next.as_ref().map(|head| head.borrow());

        elem
    })
}

ok，就剩下这货了

cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0521]: borrowed data escapes outside of closure
   --> src/fourth.rs:159:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` is declared here, outside of the closure body
...
159 |             self.0 = next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   ---- borrow is only valid in the closure body
    |             |
    |             reference to `next` escapes the closure body here

emmm，我们还需要重新借助Ref::Map来让我们的生命周期正常，但是Ref::Map又返回一个Ref，但是我们需要Option<Ref>，但是我们又需要通过Ref来map我们的Option.....

stares into distance for a long time

??????

fn next(&mut self) -> Option<Self::Item> {
    self.0.take().map(|node_ref| {
        let (next, elem) = Ref::map_split(node_ref, |node| {
            (&node.next, &node.elem)
        });

        self.0 = if next.is_some() {
            Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
        } else {
            None
        };

        elem
    })
}

然后又报错了，太好啦！

error[E0308]: mismatched types
   --> src/fourth.rs:162:22
    |
162 |                 Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
    |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `std::cell::RefCell`
    |
    = note: expected type `std::cell::Ref<'_, fourth::Node<_>>`
               found type `std::cell::Ref<'_, std::cell::RefCell<fourth::Node<_>>>`

拿到的是一个RefCell，然后当我们继续尝试borrow的时候，我们。。。进入了死循环。

太好啦！大快人心，喜大普奔，奔走相告，普天同庆

然后我们尝试拿走RefCell这个万恶之源，谁说我们需要用RefCell的，我们只是需要返回元素的引用，甚至引用都不用，Rc::clone天然返回指针。

pub struct Iter<T>(Option<Rc<Node<T>>>);

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter(self.head.as_ref().map(|head| head.clone()))
    }
}

impl<T> Iterator for Iter<T> {
    type Item =

写到这突然不知道咋写了，类型定义为&T还是Ref<T>?

都不行，因为我们生命周期莫得了，然后我们再花力气给它加回去？

然而就算我们把生命周期给它加回去，我们返回的都会引用到迭代器。。。

慢着！借用个毛，我们直接返回Rc<T>?!

然而不支持，即使支持了，我们还有一个大问题：Iter是不可变的，我们返回了个Rc, 那意味着别人并不会引用链表，这意味着人们可以在将指针伸入列表的同时开始调用推送并弹出列表！

我......我TM放弃！

正如前面我们peek只能尝试去“看“一样，这个方案基本可以宣告死亡，到处捉襟见肘不得不降低自己的预期。

失败了！

我们要尝试别的方案

代码整合#

#![allow(unused)]
fn main() {
use std::rc::Rc;
use std::cell::{Ref, RefMut, RefCell};

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>,
}

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
    prev: Link<T>,
}


impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push_front(&mut self, elem: T) {
        let new_head = Node::new(elem);
        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(new_head.clone());
                new_head.borrow_mut().next = Some(old_head);
                self.head = Some(new_head);
            }
            None => {
                self.tail = Some(new_head.clone());
                self.head = Some(new_head);
            }
        }
    }

    pub fn push_back(&mut self, elem: T) {
        let new_tail = Node::new(elem);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_tail.clone());
                new_tail.borrow_mut().prev = Some(old_tail);
                self.tail = Some(new_tail);
            }
            None => {
                self.head = Some(new_tail.clone());
                self.tail = Some(new_tail);
            }
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().prev.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next.take();
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head.take();
                }
            }
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
        })
    }

    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.borrow_mut().next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().prev.take();
                    self.head = Some(new_head);
                }
                None => {
                    self.tail.take();
                }
            }
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
        })
    }

    pub fn peek_front(&self) -> Option<Ref<T>> {
        self.head.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back(&self) -> Option<Ref<T>> {
        self.tail.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
        self.tail.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
        self.head.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop_front(), None);

        // Populate list
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_front(4);
        list.push_front(5);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

        // ---- back -----

        // Check empty list behaves right
        assert_eq!(list.pop_back(), None);

        // Populate list
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);

        // Check normal removal
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_back(4);
        list.push_back(5);

        // Check normal removal
        assert_eq!(list.pop_back(), Some(5));
        assert_eq!(list.pop_back(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn peek() {
        let mut list = List::new();
        assert!(list.peek_front().is_none());
        assert!(list.peek_back().is_none());
        assert!(list.peek_front_mut().is_none());
        assert!(list.peek_back_mut().is_none());

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

        assert_eq!(&*list.peek_front().unwrap(), &3);
        assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
        assert_eq!(&*list.peek_back().unwrap(), &1);
        assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push_front(1); list.push_front(2); list.push_front(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next_back(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }
}
}

Rc和RefCell可能太**“安全”**了，导致需要和各种限制互搏，也可能我们的步子迈的太开（怎么可能承认是自己的问题，笑）

我们可能需要尝试触碰那幽邃的unsafe，终究还是火灭了，进入深海时代...

总结#

难搞，开始有些复杂了，也是从这里开始，我的思维乱了。。。

接下来我们准备接触unsafe！

前言#