上次实现的链表（链栈）无疑是十分简陋的，所以这次我们要实现一个更好更现代化的链表。
首先是项目的结构。上次项目的所有代码是写在 chain_table 这个 crate 的 main.rs 文件里，所以这次我们所有的代码都将放在一个新的 crate 里。
在 rust 里创建库是很简单的，只要在使用 cargo 时额外添加上 --lib 选项即可。
好的，我们现在移步到我们名为 stack 的 lib crate 里。
首先还是来看下我们要定义的的结构体。
1
2
3
4
5
6
7
8
9
10
11
| mod stack {
pub struct Node<T> {
elem: T,
after: Option<Box<T>>
}
pub struct List<T> {
head: Option<Box<Node<T>>>
}
}
|
引入泛型后又多了一重尖括号，这实在太难看了。。。
还好 rust 支持类型别名，所以我们可以稍微简化一下代码。
1
2
3
4
5
6
7
8
9
10
11
12
| mod stack {
type Next<T> = Option<Box<Node<T>>> ;
pub struct Node<T> {
elem: T,
after: Next<T>
}
pub struct List<T> {
head: Next<T>
}
}
|
这样看起来就相对好些了。
因为我们实现的结构体的字段都是拥有所有权的类型，所以转换成泛型版本也是轻松无比，只要把原先的具体类型全部替换成泛型参数就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| impl<T> Node<T> {
pub fn new(elem: T) -> Self {
Node {
elem: elem,
after: None,
}
}
}
impl<T> List<T> {
pub fn new(elem: T) -> Self {
List {
head: Some(Box::new(Node {
elem: elem,
after: None,
})),
}
}
pub fn push(&mut self, elem: T) {
let mut new_node = Box::new(Node::new(elem));
new_node.after = std::mem::replace(&mut self.head, None);
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<T> {
match std::mem::replace(&mut self.head, None) {
Some(x) => {
self.head = x.after;
Some(x.elem)
}
None => None,
}
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut a = std::mem::replace(&mut self.head, None);
loop {
match a {
None => return,
Some(mut x) => a = std::mem::replace(&mut x.after, None),
}
}
}
}
|
另外就是，在标准库里，已经有很多 Option 预先实现好的方法了，利用这些方法可以更进一步简化代码，比如 take() ，这是对 mem::replace() 的一个封装，下面是 take() 方法的函数签名。
1
| pub fn take(&mut self) -> Option<T>
|
此外就是我们原先的代码中有模式匹配的部分只在匹配 Some(_) 时执行，而忽略了其他模式，此时我们可以用 if let 语法糖进一步简化我们的代码。
修改完成后完整代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #![allow(unused)]
#[cfg(test)]
mod tests {
#[test]
fn it_works() {
let result = 2 + 2;
assert_eq!(result, 4);
}
}
mod stack {
type Next<T> = Option<Box<Node<T>>>;
pub struct Node<T> {
elem: T,
after: Next<T>,
}
pub struct List<T> {
head: Next<T>,
}
impl<T> Node<T> {
pub fn new(elem: T) -> Self {
Node {
elem: elem,
after: None,
}
}
}
impl<T> List<T> {
pub fn new(elem: T) -> Self {
List {
head: Some(Box::new(Node {
elem: elem,
after: None,
})),
}
}
pub fn push(&mut self, elem: T) {
let mut new_node = Box::new(Node::new(elem));
new_node.after = self.head.take();
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<T> {
if let Some(x) = self.head.take() {
self.head = x.after;
Some(x.elem)
} else {
None
}
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut a = self.head.take();
loop {
match a {
None => break,
Some(mut x) => a = x.after.take(),
}
}
}
}
}
|
OK， 我们的二进制库的大部分工作都完成了，现在来做写个单元测试来测试下我们的单向链表（链栈）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| mod tests {
use crate::stack;
#[test]
fn push_num() {
let mut my_stack = stack::List::new(1);
my_stack.push(2);
my_stack.push(3);
assert_eq!(my_stack.pop(), Some(3));
assert_eq!(my_stack.pop(), Some(2));
assert_eq!(my_stack.pop(), Some(1));
assert_eq!(my_stack.pop(), None);
}
#[test]
fn many_str() {
let mut my_stack = stack::List::new(String::from("hello"));
for i in 1..10000 {
my_stack.push(String::from(format!("{}", &i)));
}
}
#[test]
fn many_nums() {
let mut my_stack = stack::List::new(0);
for i in 1..10000000 {
my_stack.push(i);
}
}
}
|
调用 cargo 来 test 下看看。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| cargo test
Finished test [unoptimized + debuginfo] target(s) in 0.00s
Running unittests (target/debug/deps/stack-25350f587195d617)
running 3 tests
test tests::push_num ... ok
test tests::many_str ... ok
test tests::many_nums ... ok
test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 1.80s
Doc-tests stack
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
|