cdl-list-rs

这个crate使用 Rc<T> 和 RefCell<T> 在 Rust 中实现了循环双链表。

如果你非常喜欢内部可变性或不喜欢其他实现中使用的许多不安全块，请使用这个crate！当然，内部可变性会引入其自身的潜在运行时恐慌，但目前不应该存在。

用法

使用 cdl_list::CdlList::new() 创建一个列表

let mut list : CdlList<u32> = CdlList::new();

列表必须是可变的才能添加任何元素到其中。可以使用 cdl_list::CdlList::push_front() 或 cdl_list::CdlList::push_back() 在列表的头部或尾部添加元素。

// Where A <══> B = A ⇄ B
list.push_front(1); // list = ╔══> 1 <══╗
                    //        ╚═════════╝

list.push_back(2);  // list = ╔══> 1 <══> 2 <══╗
                    //        ╚════════════════╝

list.push_front(3); // list = ╔══> 3 <══> 1 <══> 2 <══╗
                    //        ╚═══════════════════════╝

此外，您还可以使用 cdl_list::CdlList::insert_at() 在列表的特定索引处插入一个元素。

list.insert_at(2, 4); // list = ╔══> 3 <══> 1 <══> 4 <══> 2 <══╗
                      //        ╚══════════════════════════════╝

assert_eq!(list.size(), 4);
assert_eq!(list.pop_back(), Some(2));
assert_eq!(list.pop_back(), Some(4));
assert_eq!(list.pop_back(), Some(1));
assert_eq!(list.pop_back(), Some(3));

要查看列表的头部或尾部是哪个项目，请使用 cdl_list::CdlList::peek_front() 或 cdl_list::CdlList::peek_back()。这可以返回一个 Ref<T>，可以使用 * 或 clone() 来解引用。这会创建值的副本，但不能修改列表的内容！

list.push_front(1);
list.push_back(2);
list.push_front(3);
let head_val = *list.peek_front().unwrap();        // head_val = 3
let tail_val = list.peek_back().unwrap().clone();  // tail_val = 2

要从列表中删除一个项目，您目前可以使用 cdl_list::CdlList::pop_front() 或 cdl_list::CdlList::pop_back()。这分别让您拥有列表头部或尾部的值，并从列表中移除它，适当地调整列表的指针。像 peek 一样，如果列表为空，则返回 None。

let head = list.pop_front(); // head = Some(3)
                             // list = ╔══> 1 <══> 2 <══╗
                             //        ╚════════════════╝

let tail = list.pop_back();  // tail = Some(2)
                             // list = ╔══> 1 <══╗
                             //        ╚═════════╝

let last = list.pop_front(); // last = Some(1)
                             // list is empty

let empty = list.pop_back(); // empty = None

此外，您还可以使用 cdl_list::CdlList::remove_at() 从列表的特定索引处删除元素。

list.push_front(1);
list.push_back(2);
list.push_front(3);

// List:  3, 1, 2
// Index: 0, 1, 2

assert_eq!(list.remove_at(1), Some(1));

参考

一些作者对在 Rust 中实现链表有一些选择性的话语。特别是，用大量链表学习 Rust 警告 不要 使用 Rc<T> 和 RefCell<T> 来实现双向链表！尽管如此，我从他们的实现中学到了很多东西，所以即使我在阅读关于我亲爱的链表的诽谤时把手指塞进耳朵，我仍然感谢他们的辛勤工作，这对任何感兴趣的人来说都是一篇很好的读物。

(免责声明：我实际上从未全部阅读过。我现在不能借用他们的所有代码，对吧？)