Struct LinkedList 

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

Implementations

impl<T> LinkedList<T>

pub fn new() -> Self

Create an empty linked list.

let mut list = LinkedList::new();
assert_eq!(list.len(), 0);

list.push_tail(0);
assert_eq!(list.tail(), Some(&0));
assert_eq!(list.len(), 1);

pub fn get(&self, idx: Index) -> Option<&T>

Get an aliasable reference to the element of the list associated with the given index.

let mut list = LinkedList::new();
let a = list.push_head('a');
let b = list.push_head('b');
assert_eq!(list.get(a), Some(&'a'));
assert_eq!(list.get(b), Some(&'b'));

pub fn get_mut(&mut self, idx: Index) -> Option<&mut T>

Get unique reference to the element of the list associated with the given index.

let mut list = LinkedList::new();
let a = list.push_head('a');
let b = list.push_head('b');

*list.get_mut(a).unwrap() = 'A';
*list.get_mut(b).unwrap() = 'B';

assert_eq!(list.get(a), Some(&'A'));
assert_eq!(list.get(b), Some(&'B'));

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

Get an aliasable reference to the head of the list. Note that the head of the list will come first in an ordered iteration.

let mut list = LinkedList::new();
list.push_tail(0);
assert_eq!(list.head(), Some(&0));

list.push_head(1);
list.push_tail(2);
assert_eq!(list.head(), Some(&1));

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

Get an unique reference to the head of the list.

let mut list = LinkedList::new();
list.push_head('a');
*list.head_mut().unwrap() = 'b';
assert_eq!(list.head(), Some(&'b'));

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

Get an aliasable reference to the tail of the list. Note that the tail of the list will come last in an ordered iteration.

let mut list = LinkedList::new();
list.push_head(0);
assert_eq!(list.tail(), Some(&0));

list.push_tail(1);
list.push_head(2);
assert_eq!(list.tail(), Some(&1));

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

Get an unique reference to the tail of the list.

let mut list = LinkedList::new();
list.push_tail('a');
*list.tail_mut().unwrap() = 'b';
assert_eq!(list.tail(), Some(&'b'));

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

Remove the element at the head of the list, if it exists, and return it.

let mut list = LinkedList::new();
list.push_head(0);
list.push_head(1);
assert_eq!(list.pop_head(), Some(1));
assert_eq!(list.pop_head(), Some(0));

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

Remove the element at the tail of the list, if it exists, and return it.

let mut list = LinkedList::new();
list.push_tail(0);
list.push_tail(1);
assert_eq!(list.pop_tail(), Some(1));
assert_eq!(list.pop_tail(), Some(0));

pub fn push_head(&mut self, data: T) -> Index

let mut list = LinkedList::new();
list.push_head(0);
list.push_head(1);
list.push_head(2);
let mut iter = list.iter_links();
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&0));

pub fn push_tail(&mut self, data: T) -> Index

let mut list = LinkedList::new();
list.push_tail(0);
list.push_tail(1);
list.push_tail(2);
let mut iter = list.iter_links();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));

pub fn remove(&mut self, idx: Index) -> Option<T>

Remove an arbitrary element from the list, given its Index.

let mut list = LinkedList::new();

let a = list.push_tail(0);  // list: 0
list.push_head(1);          // list: 1, 0
list.push_tail(1);          // list: 1, 0, 1
let a = list.remove(a).unwrap();

assert_eq!(a, 0);
assert!(!list.iter_fast().any(|&el| el == a));

pub fn len(&self) -> usize

Get the number of elements currently in the list.

let mut list = LinkedList::new();
assert_eq!(list.len(), 0);

list.push_tail(0);
assert_eq!(list.len(), 1);

list.push_tail(0);
assert_eq!(list.len(), 2);

list.pop_head();
assert_eq!(list.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if and only if the list has no elements.

let mut list = LinkedList::new();
assert!(list.is_empty());

list.push_tail(1);
assert!(!list.is_empty());

pub fn iter_links(&self) -> IterLinks<'_, T>

Create an iterator that will follow the order defined by the links in the LinkedList.

Note that iter_fast may be faster than this implementation because it eschews the order of the linked list and just reads the underlying vector from front to back contiguously. You should prefer iter_fast if you don’t need the linked list ordering.

let mut list = LinkedList::new();
list.push_tail(0); // 0
list.push_head(1); // 1, 0
list.push_tail(2); // 1, 0, 2

let mut links = list.iter_links();
assert_eq!(links.next(), Some(&1));
assert_eq!(links.next(), Some(&0));
assert_eq!(links.next(), Some(&2));

IterLinks also implements DoubleEndedIterator, so you can reverse the iteration order.

let mut list = LinkedList::new();
list.push_tail(0); // 0
list.push_head(1); // 1, 0
list.push_tail(2); // 1, 0, 2

let mut links = list.iter_links().rev();
assert_eq!(links.next(), Some(&2));
assert_eq!(links.next(), Some(&0));
assert_eq!(links.next(), Some(&1));

pub fn into_vec(self) -> Vec<T>

Consume the list and create a vector that holds the same elements in the order defined by the links between them, which is the same as the order followed by iter_links.

Note: this function allocates a new vector and frees the original.

let mut list = LinkedList::new();
list.push_tail(0); // 0
list.push_head(1); // 1, 0
list.push_tail(2); // 1, 0, 2
assert_eq!(list.into_vec(), vec![1, 0, 2]);

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

Iterate over the nodes in the order defined by the underlying arena allocator implementation. This method should be faster than iter_links because it won’t jump back and forth across the unlying vector holding the memory for our elements. In practice, especially for smaller lists, the difference in speed will likely be negligible.

This method does not follow the order of the linked list. Use iter_links if that’s the behavior you need.

let mut list = LinkedList::new();
list.push_tail(1);
list.push_head(2);
list.push_tail(3);

// The iterator will eventually emit each of the listed elements.
// That's the only guarantee we have. The order is subject to change.
assert!(list.iter_fast().any(|&el| el == 1));
assert!(list.iter_fast().any(|&el| el == 2));
assert!(list.iter_fast().any(|&el| el == 3));

pub fn iter_fast_mut(&mut self) -> impl Iterator<Item = &mut T>

Iterate mutably over the nodes in the order defined by the underlying arena allocator implementation. See the docs for iter_links for more information.

let mut list = LinkedList::new();
list.push_tail(1u8);
list.push_head(2);
list.push_tail(3);

for element in list.iter_fast_mut() {
    *element = element.pow(2);
}

assert!(list.iter_fast().any(|&el| el == 1));
assert!(list.iter_fast().any(|&el| el == 4));
assert!(list.iter_fast().any(|&el| el == 9));

Trait Implementations

impl<T: Clone> Clone for LinkedList<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<T> Default for LinkedList<T>

fn default() -> Self

Returns the “default value” for a type.