Struct LinkedList

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

A list with links in both directions. See also: Cursor for bi-directional iteration and traversal.

Time Complexity

For this analysis of time complexity, variables are defined as follows:

• n: The number of items in the LinkedList.
• i: The index of the item in question.

Method	Complexity
len	O(1)
front/back	O(1)
push_front/back	O(1)
pop_front/back	O(1)
get	O(min(i, n-i))
insert	O(min(i, n-i))
remove	O(min(i, n-i))
replace	O(min(i, n-i))
append	O(1)
contains	O(n)

As a general note, modern computer architecture isn’t kind to linked lists, (or more importantly, favours contiguous collections) because all O(i) or O(n) operations will consist primarily of cache misses. For this reason, Vector should be preferred for most applications unless LinkedList and the accompanying Cursor type’s O(1) methods are being heavily utilized.

Implementations

impl<T> LinkedList<T>

pub const fn new() -> LinkedList<T>

Creates a new LinkedList with no elements.

pub const fn len(&self) -> usize

Returns the length of the LinkedList.

pub const fn is_empty(&self) -> bool

Returns true if the LinkedList contains no elements.

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

Returns a reference to the first element in the list, if it exists.

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

Returns a mutable reference to the first element in the list, if it exists.

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

Returns a reference to the last element in the list, if it exists.

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

Returns a mutable reference to the last element in the list, if it exists.

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

Add the provided element to the front of the LinkedList.

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

Add the provided element to the back of the LinkedList.

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

Removes the first element from the list and returns it, if the list isn’t empty.

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

Removes the last element from the list and returns it, if the list isn’t empty.

pub fn get(&self, index: usize) -> &T

Returns a reference to the element at the provided index, panicking on a failure.

The same functionality can be achieved using the Index operator.

Panics

Panics if index is out of bounds of the LinkedList.

pub fn try_get(&self, index: usize) -> Result<&T, IndexOutOfBounds>

Returns a reference to the element at the provided index, returning an Err on a failure rather than panicking.

The same functionality can be achieved using the Index operator.

pub fn get_mut(&mut self, index: usize) -> &mut T

Returns a mutable reference to the element at the provided index, panicking on a failure.

The same functionality can be achieved using the IndexMut operator.

Panics

Panics if index is out of bounds of the LinkedList.

pub fn try_get_mut(&mut self, index: usize) -> Result<&mut T, IndexOutOfBounds>

Returns a mutable reference to the element at the provided index, returning an Err on a failure rather than panicking.

The same functionality can be achieved using the IndexMut operator.

pub fn insert(&mut self, index: usize, value: T)

pub fn try_insert( &mut self, index: usize, value: T, ) -> Result<(), IndexOutOfBounds>

pub fn remove(&mut self, index: usize) -> T

pub fn try_remove(&mut self, index: usize) -> Result<T, IndexOutOfBounds>

pub fn replace(&mut self, index: usize, new_value: T) -> T

pub fn try_replace( &mut self, index: usize, new_value: T, ) -> Result<T, IndexOutOfBounds>

pub fn append(&mut self, other: LinkedList<T>)

pub fn cursor_head(self) -> Cursor<T>

pub fn cursor_tail(self) -> Cursor<T>

pub fn cursor_front(self) -> Cursor<T>

pub fn cursor_back(self) -> Cursor<T>

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

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

impl<T: Eq> LinkedList<T>

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

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

Trait Implementations

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.

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

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

Formats the value using the given formatter.

impl<T> Drop for LinkedList<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> FromIterator<T> for LinkedList<T>

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

Creates a value from an iterator.

impl<T: Hash> Hash for LinkedList<T>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T> Index<usize> for LinkedList<T>

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for LinkedList<T>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'a, T> IntoIterator for &'a LinkedList<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut LinkedList<T>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for LinkedList<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for LinkedList<T>

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

Tests for self and other values to be equal, and is used by ==.

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

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

impl<T: Eq> Eq for LinkedList<T>

impl<T> StructuralPartialEq for LinkedList<T>