Rust 中的堆链表

通过实现简单的数据结构来学习 Rust。目前仅支持 i32。

安装

cargo添加 mini-linked-list

用法

向右推送

将元素添加到列表的右侧

此方法使用 O(N) 操作，因为它需要在将新值附加到列表末尾之前遍历整个列表。

use mini_linked_list::LinkedList;
let mut list: LinkedList<i32> = LinkedList::<i32>::new();
list.push_right(1);
list.push_right(2);
assert_eq!(list.collect(), vec![1,2]);

向左推送

将元素添加到列表的左侧

此方法在 O(1) 操作中工作，因为它用新节点替换列表头部，无需遍历。

该方法返回列表的新内存地址，调用者必须处理它（通常重新分配变量）。

use mini_linked_list::LinkedList;
let mut list: LinkedList<i32> = LinkedList::<i32>::new();
list = list.push_left(1);
list = list.push_left(2);
list = list.push_left(3);
list = list.push_left(4);
assert_eq!(list.collect(), vec![4,3,2,1]);

从左侧弹出

从左侧弹出的列表头部，返回 PopLeftResult

此操作在 O(1) 中工作，因为它只需弹出头部，无需遍历。

其使用方法并不直接，因为它要求调用者将列表头部的引用替换为该方法返回的地址，在 PopLeftResult.list

建议不要直接在 unwrap 中使用 PopLeftResult.list``，而应依赖更安全的 Option` 方法。

use mini_linked_list::{LinkedList, PopLeftResult};
let mut list: LinkedList<i32> = LinkedList::<i32>::new();
list.push_right(1);
list.push_right(2);

let result: PopLeftResult<i32> = list.pop_left();
let list = result.list.unwrap();

assert_eq!(list.collect(), vec![2]);
assert_eq!(result.val.unwrap(), 1);

let result: PopLeftResult<i32> = list.pop_left();
let list = result.list;

assert_eq!(list.is_none(), true);
assert_eq!(result.val.unwrap(), 2);

use mini_linked_list::LinkedList;
let mut list: LinkedList<i32> = LinkedList::<i32>::new();
list.push_right(1);
list.push_right(2);
assert_eq!(list.pop_right().unwrap(), 2);
assert_eq!(list.pop_right().unwrap(), 1);
assert_eq!(list.pop_right().is_none(), true);