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: toml [dependencies] cyclic_list = "0.1"

Then enjoy it in your project.

Examples

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

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

let mut cursor = list.cursorstartmut();

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

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

cursor.pushfront(5); // pushing front to the list is also allowed asserteq!(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: text ┌─────────────────────────────────────────────────────────────────────┐ ↓ (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

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

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

list.itermut().foreach(|item| *item *= 2); asserteq!(Vec::fromiter(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

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

let list = List::fromiter([1, 2, 3]); // Create a cursor iterator let mut cursoriter = list.cursorstart().intoiter(); asserteq!(cursoriter.next(), Some(&1)); asserteq!(cursoriter.next(), Some(&2)); asserteq!(cursoriter.next(), Some(&3)); asserteq!(cursoriter.next(), None); asserteq!(cursoriter.next(), Some(&1)); // Not fused and cyclic

// Create a cursor back iterator which reverses the moving direction // of the cursor let mut cursoriter = cursoriter.rev(); asserteq!(cursoriter.next(), Some(&1)); // Iterate in reversed direction asserteq!(cursoriter.next(), None); // Pass through the ghost node boundary asserteq!(cursoriter.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

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

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

let mut cursor = list.cursorstartmut();

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

assert!(cursor.seekforward(2).isok()); asserteq!(cursor.remove(), Some(3)); // becomes [5, 1, 2, 4], points to 4 asserteq!(cursor.current(), Some(&4));

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

asserteq!(Vec::fromiter(list), vec![5, 1, 4]); ```

Develop Plans

Here is the develop plan of this project.