Struct List 

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

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.

Implementations

impl<T> List<T>

pub fn new() -> Self

Create a new List.

pub fn with_capacity(cap: usize) -> Self

Create a new List with specified capacity.

pub fn len(&self) -> usize

Return the number of elements in the List.

pub fn iter(&self) -> Iter<'_, T>

Return an iterator.

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Return an iterator.

pub fn cursor(&mut self) -> Cursor<'_, T>

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

pub fn push_front(&mut self, value: T)

Insert an element at the beginning of the List.

pub fn push_back(&mut self, value: T)

Insert an element at the end of the List.

pub 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.

pub 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.

pub 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 duplicate 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, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

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.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

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.