双链表

这个包提供了一个具有拥有节点的双链表，实现为循环列表。

用法

首先，在您的 Cargo.toml 中添加依赖项

[dependencies]
cyclic_list = "0.1"

然后在您的项目中使用它。

示例

use cyclic_list::List;
use std::iter::FromIterator;

let mut list = List::from_iter([1, 2, 3, 4]);

let mut cursor = list.cursor_start_mut();

cursor.insert(0); // insert 0 at the beginning of the list
assert_eq!(cursor.current(), Some(&1));
assert_eq!(cursor.view(), &List::from_iter([0, 1, 2, 3, 4]));

cursor.seek_to(3); // move the cursor to position 3, and removes it.
assert_eq!(cursor.remove(), Some(3));
assert_eq!(cursor.view(), &List::from_iter([0, 1, 2, 4]));

cursor.push_front(5); // pushing front to the list is also allowed
assert_eq!(cursor.view(), &List::from_iter([5, 0, 1, 2, 4]));

简介

List 允许在常数时间内插入、移除任何给定位置上的元素。作为妥协，访问或修改任何位置上的元素需要 O(n) 时间。

内存布局

内存布局如下所示

         ┌─────────────────────────────────────────────────────────────────────┐
         ↓                                                     (Ghost) Node N  │
   ╔═══════════╗           ╔═══════════╗                        ┌───────────┐  │
   ║   next    ║ ────────→ ║   next    ║ ────────→ ┄┄ ────────→ │   next    │ ─┘
   ╟───────────╢           ╟───────────╢     Node 2, 3, ...     ├───────────┤
┌─ ║   prev    ║ ←──────── ║   prev    ║ ←──────── ┄┄ ←──────── │   prev    │
│  ╟───────────╢           ╟───────────╢                        ├───────────┤
│  ║ payload T ║           ║ payload T ║                        ┊No payload ┊
│  ╚═══════════╝           ╚═══════════╝                        └╌╌╌╌╌╌╌╌╌╌╌┘
│      Node 0                  Node 1                               ↑   ↑
└───────────────────────────────────────────────────────────────────┘   │
╔═══════════╗                                                           │
║   ghost   ║ ──────────────────────────────────────────────────────────┘
╟───────────╢
║   (len)   ║
╚═══════════╝
    List

迭代

通过 Iter 和 IterMut 迭代器遍历列表。这些是两端迭代器，像数组一样遍历列表（融合且非循环）。IterMut 提供了元素的可变性（但不包括列表的链接结构）。

示例

use cyclic_list::List;
use std::iter::FromIterator;

let mut list = List::from_iter([1, 2, 3]);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);
assert_eq!(iter.next(), None); // Fused and non-cyclic

list.iter_mut().for_each(|item| *item *= 2);
assert_eq!(Vec::from_iter(list), vec![2, 4, 6]);

游标视图

除了迭代之外，游标 Cursor 和 CursorMut 提供了更灵活地查看列表的方法。

正如其名所示，它们像游标一样可以向前或向后移动列表。在一个长度为 n 的列表中，游标有 n + 1 个有效位置，通过 0, 1, ..., n 进行索引，其中 n 是列表的幽灵节点。

游标也可以用作迭代器，但它们是循环的且不融合。

警告：尽管游标迭代器有 rev 方法，但它们 不 作为两端迭代器行为。相反，它们创建一个新的迭代器，该迭代器反转游标的运动方向。

示例

use cyclic_list::List;
use std::iter::FromIterator;

let list = List::from_iter([1, 2, 3]);
// Create a cursor iterator
let mut cursor_iter = list.cursor_start().into_iter();
assert_eq!(cursor_iter.next(), Some(&1));
assert_eq!(cursor_iter.next(), Some(&2));
assert_eq!(cursor_iter.next(), Some(&3));
assert_eq!(cursor_iter.next(), None);
assert_eq!(cursor_iter.next(), Some(&1)); // Not fused and cyclic

// Create a cursor back iterator which reverses the moving direction
// of the cursor
let mut cursor_iter = cursor_iter.rev();
assert_eq!(cursor_iter.next(), Some(&1)); // Iterate in reversed direction
assert_eq!(cursor_iter.next(), None); // Pass through the ghost node boundary
assert_eq!(cursor_iter.next(), Some(&3)); // Reaches the ghost node

游标变异

CursorMut 提供了许多在任意位置变异列表的有用方式。

• insert：在游标处插入新项目；
• remove：移除游标处的项目；
• backspace：移除游标前的项目；
• split：从游标位置分割列表到末尾；
• splice：在光标位置之前插入另一个列表；

示例

use cyclic_list::List;
use std::iter::FromIterator;

let mut list = List::from_iter([1, 2, 3, 4]);

let mut cursor = list.cursor_start_mut();

cursor.insert(5); // becomes [5, 1, 2, 3, 4], points to 1
assert_eq!(cursor.current(), Some(&1));

assert!(cursor.seek_forward(2).is_ok());
assert_eq!(cursor.remove(), Some(3)); // becomes [5, 1, 2, 4], points to 4
assert_eq!(cursor.current(), Some(&4));

assert_eq!(cursor.backspace(), Some(2)); // becomes [5, 1, 4], points to 4
assert_eq!(cursor.current(), Some(&4));

assert_eq!(Vec::from_iter(list), vec![5, 1, 4]);

开发计划

以下是本项目的开发计划。

• 基本支持：push、pop、insert、remove；
• 光标支持：移动、搜索、insert、remove、split、splice；
• 迭代器支持：从/到迭代器、不可变/可变迭代器、双端迭代器、类似光标的迭代器；
• 容器操作
  • rotate
  • reverse
• 算法支持
  • drain
  • find
  • sort
  • 子范围视图
• 高级主题
  • 动态大小类型
  • 并发支持