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
struct Node<T> {
element: T,
next: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct List<'a, T> {
head: Link<T>,
tail: Option<&'a mut Node<T>>,
}
impl<'a, T> List<'a, T> {
pub fn new() -> Self {
List {
head: None,
tail: None,
}
}
pub fn push(&'a mut self, element: T) {
let new_tail = Box::new(Node {
element,
next: None,
});
let new_tail = match self.tail.take() {
Some(old_tail) => {
old_tail.next = Some(new_tail);
old_tail.next.as_deref_mut()
}
None => {
self.head = Some(new_tail);
self.head.as_deref_mut()
}
};
self.tail = new_tail;
}
pub fn pop(&'a mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
if self.head.is_none() {
self.tail = None;
}
node.element
})
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
pub fn basics() {
let mut list: List<i32> = List::new();
assert_eq!(list.pop(), None);
// 因为‘a指的是list的创建到销毁期，所以从签名上看，pop获取的‘a mut self并未被释放，所以后续push方法不能通过编译
// list.push(1);
// list.push(2);
// list.push(3);
// assert_eq!(list.pop(),Some(1));
// list.push(4);
// list.push(5);
// assert_eq!(list.pop(),Some(2));
// assert_eq!(list.pop(),Some(3));
// assert_eq!(list.pop(),Some(4));
// assert_eq!(list.pop(),Some(5));
// // assert_eq!(list.pop(),None);
}
}