1 unstable release
0.1.0 | Aug 29, 2021 |
---|
#924 in Algorithms
135KB
2K
SLoC
Double-Linked List
This crate provides a doubly-linked list with owned nodes, implemented as a cyclic list.
Usage
First, add dependency in your Cargo.toml
:
[dependencies]
cyclic_list = "0.1"
Then enjoy it in your project.
Examples
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]));
Introduction
The List
allows inserting, removing elements at any given position in
constant time. In compromise, accessing or mutating elements at any position
take O(n) time.
Memory Layout
The memory layout is like the following graph:
┌─────────────────────────────────────────────────────────────────────┐
↓ (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
Iteration
Iterating over a list is by the Iter
and IterMut
iterators. These are
double-ended iterators and iterate the list like an array (fused and non-cyclic).
IterMut
provides mutability of the elements (but not the linked structure of
the list).
Examples
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 Views
Beside iteration, the cursors Cursor
and CursorMut
provide more
flexible ways of viewing a list.
As the names suggest, they are like cursors and can move forward or backward over the list. In a list with length n, there are n + 1 valid locations for the cursor, indexed by 0, 1, ..., n, where n is the ghost node of the list.
Cursors can also be used as iterators, but are cyclic and not fused.
Warning: Though cursor iterators have methods rev
, they DO NOT behave
as double-ended iterators. Instead, they create a new iterator that reverses
the moving direction of the cursor.
Examples
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
Cursor Mutations
CursorMut
provides many useful ways to mutate the list in any position.
insert
: insert a new item at the cursor;remove
: remove the item at the cursor;backspace
: remove the item before the cursor;split
: split the list into a new one, from the cursor position to the end;splice
: splice another list before the cursor position;
Examples
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]);
Develop Plans
Here is the develop plan of this project.
- Basic supports: push, pop, insert, remove;
- Cursor supports: move, seek, insert, remove, split, splice;
- Iterator supports: from/into iterators, immutable/mutable iterators, double-ended iterators, cursor-like iterators;
- Container operations:
- rotate
- reverse
- Algorithm supports:
- drain
- find
- sort
- sub-range view
- Advanced topics:
- dynamic-sized types
- concurrent support