Struct orx_linked_list::LinkedList

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

The LinkedList allows pushing and popping elements at either end in constant time.

Implementations

impl<'a, T> LinkedList<'a, T>

pub fn new() -> Self

Creates a new empty linked list.

pub fn with_memory_utilization( self, memory_utilization: MemoryUtilization ) -> Self

Converts the linked list into one with the given memory_utilization.

pub fn memory_utilization(&self) -> MemoryUtilization

Returns the memory utilization settings of the list.

pub fn as_slice(&self) -> LinkedListSlice<'_, 'a, T>

Returns a reference to the entire list as an immutable slice.

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

Provides a mutable reference to the back element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();
assert_eq!(list.back(), None);

list.push_back(42);
assert_eq!(list.back(), Some(&42));

match list.back_mut() {
    None => {},
    Some(x) => *x = 7,
}
assert_eq!(list.back(), Some(&7));

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

Provides a mutable reference to the front element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();
assert_eq!(list.front(), None);

list.push_front(42);
assert_eq!(list.front(), Some(&42));

match list.front_mut() {
    None => {},
    Some(x) => *x = 7,
}
assert_eq!(list.front(), Some(&7));

pub fn get_at_mut(&mut self, at: usize) -> Option<&mut T>

Returns a mutable reference to element at the at position starting from the front; None when at is out of bounds.

This operation requires O(n) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

// build linked list: a <-> b <-> c
list.push_back('b');
list.push_front('a');
list.push_back('c');

*list.get_at_mut(0).unwrap() = 'x';
*list.get_at_mut(1).unwrap() = 'y';
*list.get_at_mut(2).unwrap() = 'z';
assert_eq!(None, list.get_at_mut(3));

assert_eq!(Some(&'x'), list.get_at(0));
assert_eq!(Some(&'y'), list.get_at(1));
assert_eq!(Some(&'z'), list.get_at(2));

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

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

list.push_back('a');
assert_eq!('a', *list.back().unwrap());

list.push_back('b');
assert_eq!('b', *list.back().unwrap());

list.push_front('x');
assert_eq!('b', *list.back().unwrap());

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

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

list.push_front('a');
assert_eq!('a', *list.front().unwrap());

list.push_front('b');
assert_eq!('b', *list.front().unwrap());

list.push_back('x');
assert_eq!('b', *list.front().unwrap());

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

Removes the last element from a list and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

// build linked list: x <-> a <-> b <-> c
list.push_back('a');
list.push_back('b');
list.push_front('x');
list.push_back('c');

assert_eq!(Some('c'), list.pop_back());
assert_eq!(Some('b'), list.pop_back());
assert_eq!(Some('a'), list.pop_back());
assert_eq!(Some('x'), list.pop_back());
assert_eq!(None, list.pop_back());
assert_eq!(None, list.pop_front());

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

Removes the last element from a list and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

// build linked list: c <-> b <-> a <-> x
list.push_front('a');
list.push_front('b');
list.push_back('x');
list.push_front('c');

assert_eq!(Some('c'), list.pop_front());
assert_eq!(Some('b'), list.pop_front());
assert_eq!(Some('a'), list.pop_front());
assert_eq!(Some('x'), list.pop_front());
assert_eq!(None, list.pop_front());
assert_eq!(None, list.pop_back());

pub fn clear(&mut self)

Removes all elements from the LinkedList.

This operation should compute in O(n) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

// build linked list: x <-> a <-> b <-> c
list.push_front('a');
list.push_front('b');
list.push_back('x');
list.push_front('c');

assert_eq!(4, list.len());
assert_eq!(Some(&'c'), list.front());
assert_eq!(Some(&'x'), list.back());

list.clear();

assert!(list.is_empty());
assert_eq!(None, list.front());
assert_eq!(None, list.back());

pub fn remove_at(&mut self, at: usize) -> Option<T>

Removes the element at the given index and returns it; returns None if at is out of bounds.

This operation requires O(n) time to access the at-th element and constant time to remove.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

// build linked list: x <-> a <-> b <-> c
list.push_back('a');
list.push_back('b');
list.push_front('x');
list.push_back('c');

assert_eq!(list.remove_at(1), Some('a'));
assert_eq!(list.remove_at(0), Some('x'));
assert_eq!(list.remove_at(1), Some('c'));
assert_eq!(list.remove_at(0), Some('b'));

pub fn insert_at(&mut self, at: usize, value: T)

Inserts the element at the given position.

This operation requires O(n) time to access the at-th element and constant time to insert.

Panics

Panics if at > len

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

// build linked list: a <-> b <-> c
list.push_back('a');
list.push_back('b');
list.push_back('c');

list.insert_at(1, 'w');
assert_eq!(vec!['a', 'w', 'b', 'c'], list.iter().copied().collect::<Vec<_>>());

pub fn memory_status(&self) -> MemoryStatus

Returns the memory utilization status of the linked list’s underlying storage.

pub fn reclaim_memory(&mut self)

This method reclaims the gaps which are opened due to lazy pops and removals, and brings back memory_status to 100% in O(n) time complexity.

Memory can be reclaimed by calling this method manually. On the other hand, memory_utilization settings of the list automatically calls this method with different frequencies:

• MemoryUtilization::WithThreshold(x) => calls whenever the utilization falls lower than x => recommended setting with x ~= 0.7.
• MemoryUtilization::Lazy => never calls => memory utilization might be low if there are many pops & removals.
• MemoryUtilization::Eager => calls after every pop & removal => keeps utilization at 100% but leads to linear time pops & removals which significantly slows down the process.

pub fn split( &self, at: usize ) -> Option<(LinkedListSlice<'_, 'a, T>, LinkedListSlice<'_, 'a, T>)>

Splits the linked list into two slices from the element at the given index. Returns None if at > self.len().

This operation should compute in O(n) time to locate the at-th element.

Slices being only views on the linked list are cheap.

Note that this method does not mutate the list; it rather returns two immutable views on two different parts of the list.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

assert_eq!(list, &['a', 'b', 'c', 'd']);

let (left, right) = list.split(1).unwrap();
assert_eq!(left, &['a']);
assert_eq!(right, &['b', 'c', 'd']);

let (left, right) = list.split(0).unwrap();
assert!(left.is_empty());
assert_eq!(right, &['a', 'b', 'c', 'd']);

let (left, right) = list.split(4).unwrap();
assert_eq!(left, &['a', 'b', 'c', 'd']);
assert!(right.is_empty());

assert!(list.split(5).is_none());

pub fn split_front(&self) -> Option<(&T, LinkedListSlice<'_, 'a, T>)>

Splits the linked list into the front and the remaining elements. Returns None if self.is_empty().

Note that this method does not mutate the list; it rather returns two immutable views on two different parts of the list.

Example

use orx_linked_list::*;

let mut list = LinkedList::new();
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

assert_eq!(list, &['a', 'b', 'c', 'd']);

let (front, rest) = list.split_front().unwrap();

assert_eq!(front, &'a');
assert_eq!(rest, &['b', 'c', 'd']);

pub fn split_back(&self) -> Option<(LinkedListSlice<'_, 'a, T>, &T)>

Splits the linked list into elements until back and back. Returns None if self.is_empty().

Note that this method does not mutate the list; it rather returns two immutable views on two different parts of the list.

Example

use orx_linked_list::*;

let mut list = LinkedList::new();
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

assert_eq!(list, &['a', 'b', 'c', 'd']);

let (rest, back) = list.split_back().unwrap();

assert_eq!(back, &'d');
assert_eq!(rest, &['a', 'b', 'c']);

impl<'a, T: PartialEq> LinkedList<'a, T>

pub fn split_before( &self, value: &T ) -> Option<(LinkedListSlice<'_, 'a, T>, LinkedListSlice<'_, 'a, T>)>

Splits the linked list into two slices using the first from front element with the given value as the pivot:

• left slice contains elements before the first appearance of the value,
• right slice contains elements containing the value and all elements afterwards.

Returns None if the value does not exist in the list.

This operation should compute in O(n) time to locate the element with the given value.

Slices being only views on the linked list are cheap.

Note that this method does not mutate the list; it rather returns two immutable views on two different parts of the list.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

assert_eq!(list, &['a', 'b', 'c', 'd']);

let (left, right) = list.split_before(&'a').unwrap();
assert!(left.is_empty());
assert_eq!(right, &['a', 'b', 'c', 'd']);

let (left, right) = list.split_before(&'b').unwrap();
assert_eq!(left, &['a']);
assert_eq!(right, &['b', 'c', 'd']);

let (left, right) = list.split_before(&'d').unwrap();
assert_eq!(left, &['a', 'b', 'c']);
assert_eq!(right, &['d']);

assert!(list.split_before(&'x').is_none());

pub fn split_after( &self, value: &T ) -> Option<(LinkedListSlice<'_, 'a, T>, LinkedListSlice<'_, 'a, T>)>

Splits the linked list into two slices using the first from front element with the given value as the pivot:

• left slice contains elements before the first appearance of the value,
• right slice contains elements containing the value and all elements afterwards.

Returns None if the value does not exist in the list.

This operation should compute in O(n) time to locate the element with the given value.

Slices being only views on the linked list are cheap.

Note that this method does not mutate the list; it rather returns two immutable views on two different parts of the list.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

assert_eq!(list, &['a', 'b', 'c', 'd']);

let (left, right) = list.split_after(&'a').unwrap();
assert_eq!(left, &['a']);
assert_eq!(right, &['b', 'c', 'd']);

let (left, right) = list.split_after(&'b').unwrap();
assert_eq!(left, &['a', 'b']);
assert_eq!(right, &['c', 'd']);

let (left, right) = list.split_after(&'d').unwrap();
assert_eq!(left, &['a', 'b', 'c', 'd']);
assert!(right.is_empty());

assert!(list.split_after(&'x').is_none());

Methods from Deref<Target = LinkedListView<'a, T>>

pub fn len(&self) -> usize

Returns the length of the linked list.

Examples

use orx_linked_list::*;

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

list.push_back('a');
list.push_front('b');
assert_eq!(2, list.len());

_ = list.pop_back();
assert_eq!(1, list.len());

pub fn is_empty(&self) -> bool

Returns true if the LinkedList is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

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

list.push_front('a');
list.push_front('b');
assert!(!list.is_empty());

_ = list.pop_back();
assert!(!list.is_empty());

list.clear();
assert!(list.is_empty());

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

Provides a reference to the back element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();
assert_eq!(list.back(), None);

list.push_back(42);
assert_eq!(list.back(), Some(&42));

list.push_front(1);
assert_eq!(list.back(), Some(&42));

list.push_back(7);
assert_eq!(list.back(), Some(&7));

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

Provides a reference to the front element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();
assert_eq!(list.front(), None);

list.push_front(42);
assert_eq!(list.front(), Some(&42));

list.push_back(1);
assert_eq!(list.front(), Some(&42));

list.push_front(7);
assert_eq!(list.front(), Some(&7));

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

Provides a forward iterator; which starts from the front-most element to the back.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

list.push_back(1);
list.push_back(2);
list.push_front(0);
list.push_back(3);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);

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

Provides a backward iterator; which starts from the back-most element to the front.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

list.push_back(1);
list.push_back(2);
list.push_front(0);
list.push_back(3);

let mut iter = list.iter_from_back();
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), None);

pub fn get_at(&self, at: usize) -> Option<&T>

Returns a reference to element at the at position starting from the front; None when at is out of bounds.

This operation requires O(n) time.

Examples

use orx_linked_list::*;

let mut list = LinkedList::new();

// build linked list: a <-> b <-> c
list.push_back('b');
list.push_front('a');
list.push_back('c');

assert_eq!(Some(&'a'), list.get_at(0));
assert_eq!(Some(&'b'), list.get_at(1));
assert_eq!(Some(&'c'), list.get_at(2));
assert_eq!(None, list.get_at(3));

pub fn collect(&self) -> LinkedList<'a, T>

where T: Clone,

Collects the LinkedListSlice into a new LinkedList.

Example

use orx_linked_list::*;

let list: LinkedList<_> = (0..6).collect();
assert_eq!(list, &[0, 1, 2, 3, 4, 5]);

let (_, b) = list.split_after(&1).unwrap();
assert_eq!(b, &[2, 3, 4, 5]); // b: LinkedListSlice is a view of the original list

let mut new_list = b.collect(); // new_list: LinkedList is a new list built from b
assert_eq!(new_list, &[2, 3, 4, 5]);

new_list.pop_back();
assert_eq!(new_list, &[2, 3, 4]);

assert_eq!(list, &[0, 1, 2, 3, 4, 5]);
assert_eq!(b, &[2, 3, 4, 5]);

pub fn contains(&self, value: &T) -> bool

Returns whether or not the given value is in the list.

Example

use orx_linked_list::*;

let mut list = LinkedList::new();

assert!(!list.contains(&'a'));

list.push_back('a');
assert!(list.contains(&'a'));

pub fn index_of(&self, value: &T) -> Option<usize>

Returns the index of the given value from the front of the list if it exists; None otherwise.

Example

use orx_linked_list::*;

let mut list = LinkedList::new();

assert!(list.index_of(&'a').is_none());

list.push_back('a');
list.push_back('b');
list.push_front('c');
list.push_front('d');
assert_eq!(Some(2), list.index_of(&'a'));

pub fn from_back_index_of(&self, value: &T) -> Option<usize>

Returns the index of the given value from the back of the list if it exists; None otherwise.

Example

use orx_linked_list::*;

let mut list = LinkedList::new();

assert!(list.from_back_index_of(&'a').is_none());

list.push_back('a');
list.push_back('b');
list.push_front('c');
list.push_front('d');
assert_eq!(Some(1), list.from_back_index_of(&'a'));

Trait Implementations

impl<'a, T: Clone> Clone for LinkedList<'a, T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, T: Debug> Debug for LinkedList<'a, T>

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

Formats the value using the given formatter.

impl<'a, T> Default for LinkedList<'a, T>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T> Deref for LinkedList<'a, T>

type Target = LinkedListView<'a, T>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<'a, 'b, T: Copy> Extend<&'b T> for LinkedList<'a, T>

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

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> Extend<T> for LinkedList<'a, T>

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

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 LinkedList<'a, T>

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

Creates a value from an iterator.

impl<'a, T: PartialEq> PartialEq<LinkedList<'a, T>> for [T]

fn eq(&self, other: &LinkedList<'a, T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T: PartialEq> PartialEq<LinkedList<'a, T>> for LinkedListView<'a, T>

fn eq(&self, other: &LinkedList<'a, T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T: PartialEq> PartialEq<LinkedListView<'a, T>> for LinkedList<'a, T>

fn eq(&self, other: &LinkedListView<'a, T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T: PartialEq, S: AsRef<[T]>> PartialEq<S> for LinkedList<'a, T>

fn eq(&self, other: &S) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, T: PartialEq> PartialEq for LinkedList<'a, T>

fn eq(&self, other: &LinkedList<'a, T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.