为一个基础数据结构开一个新篇？链表这么有牌面么？
今天在Leetcode随机到了跳表，于是我准备学习下Rust链表先。
乍一看链表应该不难啊，值得放进难点？
看一下course.rs:
人家开了一整章，好吧，我们知道Rust不允许悬垂指针，那我们的链表可咋整，且听我慢慢来学
1 实现链表
从简单的定义开始
pub enum List {
Empty,
Elem(i32, List),
}当尝试build这个的时候，会出现
当前这个类型并不是定长的，Rust编译器认为栈上类型必须有固定长度，因此，我们按照提示，把List通过Box封装到堆上，栈上只留下一个定长的指针。
更改为box封装后，我们的链表过编了，但是这还有点问题，一点都不优雅
[] = Stack
() = Heap
[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)链表头并不是一个指针，而是一个栈上元素，而后面的尾节点却在堆上，而我们期望的（显然，你应该已经了解C的链表了）
[head] -> (val A, ptr) -> (val B, null)是这样的链表
这是有意义的，前者在分割、合并链表的时候，都会有Copy到栈上、Copy到堆里的操作，但是后者只需要动动指针，也和我们最初的期望保持一致。
由此，我们的定义改版为如下：
struct Node {
elem: i32,
next: List,
}
pub enum List {
Empty,
More(Box<Node>),
}在叙述中，这种enum会遵循Rust的编译器优化，More中包含了一个非0指针，而Empty是无数据的（More、Empty都是自定义的，叫啥都行），在这种情况下不会产生enum_tag的开销，即Rust不需要记住具体是哪种tag，非0就是More，为0就是Empty
还有一点小问题，封装的可见性。材料里报的是error，我本地报的warning，但是不管哪种，我们都希望尽可能符合最小暴露原则，所以定义改为如下：
pub struct List {
head: Link,
}
enum Link {
Empty,
More(Box<Node>),
}
struct Node {
elem: i32,
next: Link,
}接下来，我们为这个链表加上操作
impl List {
pub fn new() -> Self {
List { head: Link::Empty }
}
pub fn push(&mut self, elem: i32) {
// 在链表头插入数据
}
}push会改变链表，所以需要一个可变借用，我们新建一个Node，然后把她的next指向旧head，把head指向他
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: self.head,
});
self.head = Link::More(new_node);
}看起来很美好，但是估计没有这么简单
Link没有实现Copy，我们也不能简单粗暴的实现一个Clone，如果直接赋值，会导致Link的所有权被移走，head悬垂了
我们用一个不太优雅的小trick：mem::replace，在从head中偷出值的同时塞回去一个新值
变成这样：
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);
}好吧，看着奇奇怪怪，在逻辑中引入了一些不逻辑的东西，但是我们没有什么办法了
接着实现Pop，在弹出的同时返回一个Option
pub fn pop(&mut self) -> Option<i32> {
match &self.head {
Link::Empty => {
None;
}
Link::More(node) => {
self.head = node.next;
Some(node.elem)
}
}
}不需要编译，都能猜到肯定 self.head = node.next;有点问题，这里又产生move了
我本来想说，那就不给大家演示了，结果一编译发现还有个问题
两个愿望，一次满足：
pub fn pop(&mut self) -> Option<i32> {
match std::mem::replace(&mut self.head, Link::Empty) {
Link::Empty => None,
Link::More(node) => {
self.head = node.next;
Some(node.elem)
}
}
}把head变成empty，同时换到node里，但是和push一样使用了一点trick
链表的释放
rust为绝大多数类型实现了drop，并且如果结构的每个字段都有drop，也会自动为结构实现drop
但是材料给了一种问题情况：
#[test]
fn long_list() {
let mut list = List::new();
for i in 0..100000 {
list.push(i);
}
drop(list);
}虽然这看上去是一个尾递归（递归发生在尾部，应当复用栈帧），但是在rust实现里并非如此
impl Drop for List {
fn drop(&mut self) {
// NOTE: 在 Rust 代码中，我们不能显式的调用 `drop` 方法，只能调用 std::mem::drop 函数
// 这里只是在模拟编译器!
self.head.drop(); // 尾递归 - good!
}
}
impl Drop for Link {
fn drop(&mut self) {
match *self {
Link::Empty => {} // Done!
Link::More(ref mut boxed_node) => {
boxed_node.drop(); // 尾递归 - good!
}
}
}
}
impl Drop for Box<Node> {
fn drop(&mut self) {
self.ptr.drop(); // 糟糕，这里不是尾递归!
deallocate(self.ptr); // 不是尾递归的原因是在 `drop` 后，还有额外的操作
}
}
impl Drop for Node {
fn drop(&mut self) {
self.next.drop();
}
}
对于Box\<Node>来说，编译器的行为并不是尾递归，会爆栈
材料给出一种方法
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = mem::replace(&mut self.head, Link::Empty);
while let Link::More(mut boxed_node) = cur_link {
cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
}
}
}
手动的换出每个节点，然后在while结束的时候就drop了
优化类型定义和代码复杂度
刚刚的代码中，除了replace很怪，还有一大坨的类型声明也很怪，毕竟我们C的链表声明一个结构体就够了
有一个很显然的优化是enum Link和Option十分的类似
pub struct List {
head: Link,
}
type Link = Option<Box<Node>>;
struct Node {
elem: i32,
next: Link,
}
Option提供了一个take函数，让我们不需要那个冗长的replace
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}Option让我们的match可以变为map
pub fn pop(&mut self) -> Option<i32> {
self.head.take().map(|node| {
self.head = node.next;
node.elem
})
}加入泛型
我们会在签名处加入 <T\>，这样这个链表即时就支持泛型了
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
node.elem
})
}
}
impl<T> Drop for List<T> {
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();
}
}
}
评论 (0)