前言
昨天我们实现了一个面向生产环境的双向队列，今天我们不准备优化了，我们来了解一些骚方案。
另外最终代码放这里，因为内容到知乎上限了。。。
面向生产环境的双链队列最终代码
奇怪的技巧
其实还有比较时髦的方法，我们来试下：
- 一个双重单向链The Double Single
- 一个堆栈分配列表The Stack Allocated List
- 一个自引用链（TODO）
- 一个GhostCell列表（TODO）
Double Single
顾名思义，我们一个链表里存俩单向列表。
Stack<T>其实就是原来的安全单向链List<T>，只是我们又封装了一层：
然后稍微调整下pop和push两个代码：
抽离组装和拿取的逻辑，这样就可以方便实现左边装填右边，右边装填左边的逻辑了。
然后我们还可以轻易的实现左右遍历的逻辑
然后搞几个测试用例：
这是一个非常典型的手指型数据结构finger data structure，看起来也确实像一个手指在这拨正。
虽然这个写法很搞笑，但是写起来很舒服。比如IterMut的场景我们可以复用元素！
不过也有一定的缺点，如果要的元素离这里非常远，那么就需要走很远才能过去。
The Stack-Allocated Linked List
我们从头学到尾都是在基于堆空间实现的链表，一方面是写法上确实有局限，另一方面是动态内存分配它也要求我们去这么做。
不过如果我们的数据不是泛型，而是简单的类型比如i32这种，那么放在栈上也未尝不可。
解决了泛型，但是我们还有另一个问题，递归空间问题
其实也能解决（虽然比较蠢，但是学习嘛 + 来都来了）
首先回顾下我们为什么使用堆内存来实现，因为我们的类型是带有递归逻辑的，为了避开编译器的限制，我们采用了Box即保留一个指针，数据放到堆内存上的逻辑的方案。
那么如果我们每次都增加这个空间的容量呢？不可能！栈上已经固定了！
是的，但是如果我们想个法子，每次都获取一块更大一点的空间不就行了？
限于章节篇幅，这里我们使用一个简单的栈分配方法：调用一个函数，获取一个新的、拥有更多空间的栈帧。说实话，该解决方法要多愚蠢有多愚蠢，但是它确实相当实用，甚至...有用。
任何时候，当我们在做一些递归的任务时，都可以将当前步骤状态的指针传递给下一个步骤。如果指针本身就是状态的一部分，那恭喜你：你在创建一个栈上分配的链表！
那我们要怎么调用呢？自然是回调地狱
我们甚至可以给它实现一个迭代器
这个是可以的，不信你可以运行下下面的测试用例：
不过我们并不能做到修改元素的值：
原因是我们的结构是依赖于变体（variance）的,Variance是一个复杂的主题
简单的说：
每一个节点( Node )都包含一个引用，该引用指向另一个节点， 且这两个节点是同一个类型。如果从最里面的节点角度来看，那所有外部的节点都在使用和它一样的生命周期，但这个显然是不对的：链表中的每一个节点都会比它指向的节点活得更久，因为它们的作用域是嵌套存在的。
那之前的不可变引用版本为何可以正常工作呢？原因是在大多数时候，编译器都能自己判断：虽然某些东东活得太久了，但是这是安全的。当我们把一个 List 塞入另一个时，编译器会迅速将生命周期进行收缩以满足新的 List 的需求，这种生命周期收缩就是一种型变。
如果大家还是觉得不太理解，我们来考虑下其它拥有继承特性的编程语言。在该语言中，当你将一个
Cat传递给需要Animal的地方时(Animal是Cat的父类型)，型变就发生了。从字面来说，将一只猫传给需要动物的地方，也是合适的，毕竟猫确实是动物的一种。总之，可以看出无论是从大的生命周期收缩为小的生命周期，还是从
Cat到Animal，型变的典型特征就是：范围在减小，毕竟子类型的功能肯定是比父类型多的。
这块直接从这老哥这里copy过来的：栈上的链表 - Rust语言圣经(Rust Course)，翻译的很直白，很容易懂。
然后我们回归问题本身，为什么可变引用不行。
因为型变不一定是安全的，比如：
其实前面也说过了，&mut应该得是invariant的，所以在这里不行。
还是上面动物的例子：
这是可行的，因为生命周期从一个更长的转移到更短的是被允许的！
那如果我们就是要出狂战斧呢？
那可以用内部可变性啊！
注意cell只能用于Sized的类型。
总结
呃。。。。。。一开始只是刷算法的时候觉得链表很难搞，所以想看点文章巩固下相关知识，没想到里面包含了一些没见过的知识点。。。。。所以挺乱的，还是建议去看原文或者老哥的翻译，都很幽默风趣！