Struct ixlist::List

pub struct List<T> { /* fields omitted */ }

List is a doubly linked list stored in one contiguous allocation.

Features

• O(1) insert and remove both at front and back.
• O(1) insert anywhere if you have a cursor to that position.
• Only use of unsafe is an unavoidable use for IterMut.

Implementation

It is similar to a linked list in a language like C, except instead of pointers we use indices into a backing vector.

The list is just a vector, and indices to the head and tail:

struct List<T> {
    /// Head, Tail
    link: [usize; 2],
    nodes: Vec<Node<T>>,
}

The list node is represented like this:

struct Node<T> {
    /// Prev, Next.
    link: [usize; 2],
    value: T,
}

The link arrays contain the vector indices of the previous and next node. We use an array so that symmetries in front/back or prev/next can be used easily in the code — it's nice if we can write just one push and one pop method instead of two.

There is a constant to denote a “null” index, and that's usize's max value. We don't always have to check for this case, we can just access the nodes vector using .get() or .get_mut(); a “null” link is the None case.

To do

List could be generic over the index type, so that internal prev/node links can use less space than a regular pointer (can be u16 or u32 index).

With some cleanup we can use unchecked indexing — but it's not guaranteed to make any difference.

Methods

impl<T> List<T>

fn new() -> Self

Create a new List.

fn with_capacity(cap: usize) -> Self

Create a new List with specified capacity.

fn len(&self) -> usize

Return the number of elements in the List.

fn iter(&self) -> Iter<T>

Return an iterator.

fn iter_mut(&mut self) -> IterMut<T>

Return an iterator.

fn cursor(&mut self) -> Cursor<T>

Return a new cursor, focused before the head of the List.

fn push_front(&mut self, value: T)

Insert an element at the beginning of the List.

fn push_back(&mut self, value: T)

Insert an element at the end of the List.

fn pop_front(&mut self) -> Option<T>

Remove the element at the beginning of the List and return it, or return None if the List is empty.

fn pop_back(&mut self) -> Option<T>

Remove the element at the end of the List and return it, or return None if the List is empty.

fn linearize(&mut self)

Reorder internal datastructure into traversal order.

Trait Implementations

impl<T: Clone> Clone for List<T>

fn clone(&self) -> List<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for List<T>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<'a, T> FromIterator<T> for List<T>

fn from_iter<I>(iter: I) -> Self where
    I: IntoIterator<Item = T>, 

Creates a value from an iterator.

impl<'a, T> Extend<T> for List<T>

fn extend<I>(&mut self, iter: I) where
    I: IntoIterator<Item = T>, 

Extends a collection with the contents of an iterator.