Struct ixlist::List
[−]
[src]
pub struct List<T> {
// some 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.