Crate tsil_cev

Implementation of the linked list on Vec. Has an O(1) amortized insertion and removal time due to linear placement in memory. It is added in the same way as in Vec, but at deletion the element moves to the end and something like pop is called, and if the length equals capacity / 4 then the Vec is reallocated and the capacity == 2 * length invariant is always executed.

tsil and cev

TsilCev has 2 types of iterators Tsil and Cev. Tsil - iterating as in LinkedList. Cev - iterating as in Vec (a bit faster because memory access is sequential).

Examples

use tsil_cev::TsilCev;

let mut tc = TsilCev::from(vec![5, 6, 7, 8, 9, 10]);
tc.push_front(4);

let mut cursor = tc.cursor_front_mut();
assert_eq!(cursor.current(), Some(&4));

cursor.move_next();
assert_eq!(cursor.current(), Some(&5));

cursor.remove();
assert_eq!(cursor.current(), Some(&6));

cursor.remove().remove().move_next_length(2);
assert_eq!(cursor.current(), Some(&10));

cursor.move_prev();
assert_eq!(cursor.current(), Some(&9));

let _ = tc.drain_filter_tsil(|x| *x % 2 == 0).collect::<Vec<_>>();
assert_eq!(tc.to_vec(), &[9]);

Current Implementation

The allocator for the elements is Vec and each element has two indexes (next and previous element). Also if the number of elements is less than capacity / 4 then it is reallocated to size capacity / 2. The time of addition and removal is amortized to O(1).

Optional features

serde

When this optional dependency is enabled, TsilCev implements the serde::Serialize and serde::Deserialize traits.

Structs

CevIter
CevIterMut
Cursor
CursorMut
DrainFilterCev
DrainFilterTsil
TsilCev
TsilIntoIter
TsilIter
TsilIterMut