Struct LinkedList

pub struct LinkedList<T = ()> {
    pub head: Option<LinkedListIndex>,
    pub tail: Option<LinkedListIndex>,
    /* private fields */
}

A doubly linked list using SlotMap for better cache performance than a linked list using pointers, and which also solves the ABA problem.

Fields

head: Option<LinkedListIndex>

The index of the first item in the list.

tail: Option<LinkedListIndex>

The index of the last item in the list.

Implementations

impl<T> LinkedList<T>

pub fn new() -> Self

Create a new empty list.

pub fn contains_key(&self, index: LinkedListIndex) -> bool

Checks if the list contains the given index.

pub fn head(&self) -> Option<&LinkedListItem<T>>

Get the first item in the list. Can be None if the list is empty.

pub fn head_mut(&mut self) -> Option<&mut LinkedListItem<T>>

Get a mutable reference to the first item in the list. Can be None if the list is empty.

pub fn tail(&self) -> Option<&LinkedListItem<T>>

Get the last item in the list. Can be None if the list is empty.

pub fn tail_mut(&mut self) -> Option<&mut LinkedListItem<T>>

Get a mutable reference to the last item in the list. Can be None if the list is empty.

pub fn new_data<V>(&self) -> SecondaryMap<LinkedListIndex, V>

Convenience method to return a slotmap::SecondaryMap of type V

pub fn new_data_sparse<V>(&self) -> SparseSecondaryMap<LinkedListIndex, V>

Convenience method to return a slotmap::SparseSecondaryMap of type V

pub fn get(&self, index: LinkedListIndex) -> Option<&LinkedListItem<T>>

Get an item in the list.

pub fn get_mut( &mut self, index: LinkedListIndex, ) -> Option<&mut LinkedListItem<T>>

Get a mutable reference to an item in the list.

pub fn next_of(&self, index: LinkedListIndex) -> Option<&LinkedListItem<T>>

Get the item after the item with the given index if it exists.

pub fn prev_of(&self, index: LinkedListIndex) -> Option<&LinkedListItem<T>>

Get the item before the item with the given index if it exists.

pub fn next_of_mut( &mut self, index: LinkedListIndex, ) -> Option<&mut LinkedListItem<T>>

Get a mutable reference to the item after the item with the given index if it exists.

pub fn prev_of_mut( &mut self, index: LinkedListIndex, ) -> Option<&mut LinkedListItem<T>>

Get a mutable reference to the item before the item with the given index if it exists.

pub fn insert_after( &mut self, index: LinkedListIndex, value: T, ) -> LinkedListIndex

Insert an item after the given index and return the index of the new item.

pub fn insert_before( &mut self, index: LinkedListIndex, value: T, ) -> LinkedListIndex

Insert an item before the given index.

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

Add an item to the back of the list and return its index.

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

Push an item to the front of the list.

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

Remove the last item in the list and return it (if it exists)

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

Remove the first item in the list and return it (if it exists)

pub fn iter(&self) -> impl Iterator<Item = &LinkedListItem<T>>

Convenience method for list.iter_next(list.head.unwrap())

Example

use fast_list::LinkedList;
let mut list = LinkedList::new();
list.extend(0..100);

assert_eq!(list.iter_next(list.head.unwrap()).count(), 100);
assert_eq!(list.iter().count(), 100);
assert_eq!(
    list.iter().next().unwrap().value,
    list.iter_next(list.head.unwrap()).next().unwrap().value
);

pub fn iter_unordered(&self) -> impl Iterator<Item = &LinkedListItem<T>>

Returns an iterator that iterates over the items of the list in no particular order.

pub fn iter_next( &self, start: LinkedListIndex, ) -> impl Iterator<Item = &LinkedListItem<T>>

Returns an iterator that iterates over the items of the list.

pub fn iter_prev( &self, start: LinkedListIndex, ) -> impl Iterator<Item = &LinkedListItem<T>>

Returns an iterator that iterates over the items of the list in reverse order.

pub fn cursor_next(&self, item: LinkedListIndex) -> Option<LinkedListIndex>

Returns the next index of the item with the given index.

pub fn cursor_prev(&self, item: LinkedListIndex) -> Option<LinkedListIndex>

Returns the previous index of the item with the given index.

pub fn cursor_iter_next( &self, start: LinkedListIndex, ) -> impl Iterator<Item = LinkedListIndex> + '_

Returns an iterator that iterates over the indexes of the list.

pub fn cursor_iter_prev( &self, start: LinkedListIndex, ) -> impl Iterator<Item = LinkedListIndex> + '_

Returns an iterator that iterates over the indexes of the list in reverse order.

pub fn split_off(&mut self, index: LinkedListIndex) -> Self

Splits the list into two at the given index. Returns a new list containing everything after the given index, including the index. This operation should compute in O(n) time.

T needs to implement Clone only to be able to insert the index, but not for the following items.

The old indexes will become invalid after this operation and new indexes can be retrieved by iterating from the head & tail of the new list.

pub fn nth(&self, n: usize) -> Option<LinkedListIndex>

Returns the nth index by iterating from the head or tail, whichever is closer.

pub fn extend<I>(&mut self, values: I) -> Vec<LinkedListIndex>

where I: IntoIterator<Item = T>,

Push many items to the back of the list.

Returns the indexes of the new items

pub fn extend_front<I>(&mut self, values: I) -> Vec<LinkedListIndex>

where I: IntoIterator<Item = T>,

Push many items to the front of the list.

Returns the indexes of the new items

pub fn len(&self) -> usize

Get the number of items in the list.

pub fn remove(&mut self, index: LinkedListIndex) -> Option<LinkedListItem<T>>

Remove an item from the list, returning the value at the key if the key was not previously removed.

pub fn retain_mut<F>(&mut self, f: F)

where F: FnMut(&T) -> bool,

Retain only the elements specified by the predicate. This operation should compute in O(n) time. Modifies the list in place.

pub fn retain<F>(&self, f: F) -> Self

where F: FnMut(&T) -> bool, T: Clone, LinkedListItem<T>: Clone,

Returns a cloned list retaining only the elements specified by the predicate.

Trait Implementations

impl<T: Debug> Debug for LinkedList<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.