双重单链表
我们在处理双链表时很纠结,因为它们有纠结的所有权语义:没有一个节点严格地拥有任 何其他节点。然而,我们对此感到挣扎,因为我们带来了我们对什么是链表的先入为主 的概念。也就是说,我们假设所有的链接都在同一个方向。
相反,我们可以把我们的列表分成两半:一个向左走,一个向右走:
// lib.rs
// ...
pub mod silly1; // NEW!
// silly1.rs
use second::List as Stack;
struct List<T> {
left: Stack<T>,
right: Stack<T>,
}
现在,我们不再有一个单纯的安全堆栈,而是有一个通用的列表。我们可以通过推送到任何 一个堆栈来向左或向右增长这个列表。我们还可以通过从一端弹出数值到另一端来沿着列表 “行走”。为了避免不必要的分配,我们将复制我们的安全堆栈的源码,以获得它的私有细节:
pub struct Stack<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> Stack<T> {
pub fn new() -> Self {
Stack { 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| {
let node = *node;
self.head = node.next;
node.elem
})
}
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
&node.elem
})
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| {
&mut node.elem
})
}
}
impl<T> Drop for Stack<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();
}
}
}
然后只是重新设计一下push
和pop
:
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node {
elem: elem,
next: None,
});
self.push_node(new_node);
}
fn push_node(&mut self, mut node: Box<Node<T>>) {
node.next = self.head.take();
self.head = Some(node);
}
pub fn pop(&mut self) -> Option<T> {
self.pop_node().map(|node| {
node.elem
})
}
fn pop_node(&mut self) -> Option<Box<Node<T>>> {
self.head.take().map(|mut node| {
self.head = node.next.take();
node
})
}
现在我们可以做我们自己的链表:
pub struct List<T> {
left: Stack<T>,
right: Stack<T>,
}
impl<T> List<T> {
fn new() -> Self {
List { left: Stack::new(), right: Stack::new() }
}
}
我们还可以做一些常规的事情:
pub fn push_left(&mut self, elem: T) { self.left.push(elem) }
pub fn push_right(&mut self, elem: T) { self.right.push(elem) }
pub fn pop_left(&mut self) -> Option<T> { self.left.pop() }
pub fn pop_right(&mut self) -> Option<T> { self.right.pop() }
pub fn peek_left(&self) -> Option<&T> { self.left.peek() }
pub fn peek_right(&self) -> Option<&T> { self.right.peek() }
pub fn peek_left_mut(&mut self) -> Option<&mut T> { self.left.peek_mut() }
pub fn peek_right_mut(&mut self) -> Option<&mut T> { self.right.peek_mut() }
但最有趣的是,我们可以走来走去!
pub fn go_left(&mut self) -> bool {
self.left.pop_node().map(|node| {
self.right.push_node(node);
}).is_some()
}
pub fn go_right(&mut self) -> bool {
self.right.pop_node().map(|node| {
self.left.push_node(node);
}).is_some()
}
我们在这里返回布尔值,只是为了方便表明我们是否真的成功移动了。现在让我们测试一下 这个宝贝:
#[cfg(test)]
mod test {
use super::List;
#[test]
fn walk_aboot() {
let mut list = List::new(); // [_]
list.push_left(0); // [0,_]
list.push_right(1); // [0, _, 1]
assert_eq!(list.peek_left(), Some(&0));
assert_eq!(list.peek_right(), Some(&1));
list.push_left(2); // [0, 2, _, 1]
list.push_left(3); // [0, 2, 3, _, 1]
list.push_right(4); // [0, 2, 3, _, 4, 1]
while list.go_left() {} // [_, 0, 2, 3, 4, 1]
assert_eq!(list.pop_left(), None);
assert_eq!(list.pop_right(), Some(0)); // [_, 2, 3, 4, 1]
assert_eq!(list.pop_right(), Some(2)); // [_, 3, 4, 1]
list.push_left(5); // [5, _, 3, 4, 1]
assert_eq!(list.pop_right(), Some(3)); // [5, _, 4, 1]
assert_eq!(list.pop_left(), Some(5)); // [_, 4, 1]
assert_eq!(list.pop_right(), Some(4)); // [_, 1]
assert_eq!(list.pop_right(), Some(1)); // [_]
assert_eq!(list.pop_right(), None);
assert_eq!(list.pop_left(), None);
}
}
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 16 tests
test fifth::test::into_iter ... ok
test fifth::test::basics ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fourth::test::into_iter ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test second::test::peek ... ok
test silly1::test::walk_aboot ... ok
test result: ok. 16 passed; 0 failed; 0 ignored; 0 measured
这是一个手指数据结构的极端例子,我们将某种手指维护到结构中,结果是可以支持对位 置的操作,时间与手指的距离成正比。
我们可以对手指周围的列表进行非常快速的修改,但是如果我们想在离手指很远的地方进行修
改,我们就必须一直走到那里。我们可以通过将元素从一个堆栈转移到另一个堆栈来永久地走
过去,或者我们可以用一个&mut
临时沿着链接走过去做改变。然而,&mut
永远不能回到
列表中去,而我们的手指却可以!