Struct scale_info::prelude::collections::linked_list::LinkedList

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

A doubly-linked list with owned nodes.

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

NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache.

Implementations

impl<T> LinkedList<T>

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

Creates an empty LinkedList.

Examples

use std::collections::LinkedList;

let list: LinkedList<u32> = LinkedList::new();

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

Moves all elements from other to the end of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation should compute in O(1) time and O(1) memory.

Examples

use std::collections::LinkedList;

let mut list1 = LinkedList::new();
list1.push_back('a');

let mut list2 = LinkedList::new();
list2.push_back('b');
list2.push_back('c');

list1.append(&mut list2);

let mut iter = list1.iter();
assert_eq!(iter.next(), Some(&'a'));
assert_eq!(iter.next(), Some(&'b'));
assert_eq!(iter.next(), Some(&'c'));
assert!(iter.next().is_none());

assert!(list2.is_empty());

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

🔬 This is a nightly-only experimental API. (linked_list_prepend)

Moves all elements from other to the begin of the list.

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

Provides a forward iterator.

Examples

use std::collections::LinkedList;

let mut list: LinkedList<u32> = LinkedList::new();

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

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(), None);

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

Provides a forward iterator with mutable references.

Examples

use std::collections::LinkedList;

let mut list: LinkedList<u32> = LinkedList::new();

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

for element in list.iter_mut() {
    *element += 10;
}

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), Some(&11));
assert_eq!(iter.next(), Some(&12));
assert_eq!(iter.next(), None);

pub fn cursor_front(&self) -> Cursor<'_, T>

🔬 This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor at the front element.

The cursor is pointing to the "ghost" non-element if the list is empty.

pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T>

🔬 This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor with editing operations at the front element.

The cursor is pointing to the "ghost" non-element if the list is empty.

pub fn cursor_back(&self) -> Cursor<'_, T>

🔬 This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor at the back element.

The cursor is pointing to the "ghost" non-element if the list is empty.

pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T>

🔬 This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor with editing operations at the back element.

The cursor is pointing to the "ghost" non-element if the list is empty.

pub fn is_empty(&self) -> bool

Returns true if the LinkedList is empty.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

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

dl.push_front("foo");
assert!(!dl.is_empty());

pub fn len(&self) -> usize

Returns the length of the LinkedList.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();

dl.push_front(2);
assert_eq!(dl.len(), 1);

dl.push_front(1);
assert_eq!(dl.len(), 2);

dl.push_back(3);
assert_eq!(dl.len(), 3);

pub fn clear(&mut self)

Removes all elements from the LinkedList.

This operation should compute in O(n) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();

dl.push_front(2);
dl.push_front(1);
assert_eq!(dl.len(), 2);
assert_eq!(dl.front(), Some(&1));

dl.clear();
assert_eq!(dl.len(), 0);
assert_eq!(dl.front(), None);

pub fn contains(&self, x: &T) -> bool where
    T: PartialEq<T>, 

Returns true if the LinkedList contains an element equal to the given value.

Examples

use std::collections::LinkedList;

let mut list: LinkedList<u32> = LinkedList::new();

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

assert_eq!(list.contains(&0), true);
assert_eq!(list.contains(&10), false);

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

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

Examples

use std::collections::LinkedList;

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

dl.push_front(1);
assert_eq!(dl.front(), Some(&1));

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

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

Examples

use std::collections::LinkedList;

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

dl.push_front(1);
assert_eq!(dl.front(), Some(&1));

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

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

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

Examples

use std::collections::LinkedList;

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

dl.push_back(1);
assert_eq!(dl.back(), Some(&1));

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

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

Examples

use std::collections::LinkedList;

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

dl.push_back(1);
assert_eq!(dl.back(), Some(&1));

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

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

Adds an element first in the list.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();

dl.push_front(2);
assert_eq!(dl.front().unwrap(), &2);

dl.push_front(1);
assert_eq!(dl.front().unwrap(), &1);

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

Removes the first element and returns it, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut d = LinkedList::new();
assert_eq!(d.pop_front(), None);

d.push_front(1);
d.push_front(3);
assert_eq!(d.pop_front(), Some(3));
assert_eq!(d.pop_front(), Some(1));
assert_eq!(d.pop_front(), None);

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

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples

use std::collections::LinkedList;

let mut d = LinkedList::new();
d.push_back(1);
d.push_back(3);
assert_eq!(3, *d.back().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 std::collections::LinkedList;

let mut d = LinkedList::new();
assert_eq!(d.pop_back(), None);
d.push_back(1);
d.push_back(3);
assert_eq!(d.pop_back(), Some(3));

pub fn split_off(&mut self, at: usize) -> LinkedList<T>

Splits the list into two at the given index. Returns everything after the given index, including the index.

This operation should compute in O(n) time.

Panics

Panics if at > len.

Examples

use std::collections::LinkedList;

let mut d = LinkedList::new();

d.push_front(1);
d.push_front(2);
d.push_front(3);

let mut split = d.split_off(2);

assert_eq!(split.pop_front(), Some(1));
assert_eq!(split.pop_front(), None);

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

🔬 This is a nightly-only experimental API. (linked_list_remove)

Removes the element at the given index and returns it.

This operation should compute in O(n) time.

Panics

Panics if at >= len

Examples

#![feature(linked_list_remove)]
use std::collections::LinkedList;

let mut d = LinkedList::new();

d.push_front(1);
d.push_front(2);
d.push_front(3);

assert_eq!(d.remove(1), 2);
assert_eq!(d.remove(0), 3);
assert_eq!(d.remove(0), 1);

pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F> where
    F: FnMut(&mut T) -> bool, 

🔬 This is a nightly-only experimental API. (drain_filter)

recently added

Creates an iterator which uses a closure to determine if an element should be removed.

If the closure returns true, then the element is removed and yielded. If the closure returns false, the element will remain in the list and will not be yielded by the iterator.

Note that drain_filter lets you mutate every element in the filter closure, regardless of whether you choose to keep or remove it.

Examples

Splitting a list into evens and odds, reusing the original list:

#![feature(drain_filter)]
use std::collections::LinkedList;

let mut numbers: LinkedList<u32> = LinkedList::new();
numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);

let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>();
let odds = numbers;

assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<T> Decode for LinkedList<T> where
    T: Decode, 

pub fn decode<I>(input: &mut I) -> Result<LinkedList<T>, Error> where
    I: Input, 

Attempt to deserialise the value from input.

pub fn skip<I>(input: &mut I) -> Result<(), Error> where
    I: Input, 

Attempt to skip the encoded value from input.

pub fn encoded_fixed_size() -> Option<usize>

Returns the fixed encoded size of the type.

impl<T> DecodeLength for LinkedList<T>

pub fn len(self_encoded: &[u8]) -> Result<usize, Error>

Return the number of elements in self_encoded.

impl<T> Default for LinkedList<T>

pub fn default() -> LinkedList<T>

Creates an empty LinkedList<T>.

impl<'de, T> Deserialize<'de> for LinkedList<T> where
    T: Deserialize<'de>, 

pub fn deserialize<D>(
    deserializer: D
) -> Result<LinkedList<T>, <D as Deserializer<'de>>::Error> where
    D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

pub fn deserialize_in_place<D>(
    deserializer: D,
    place: &mut LinkedList<T>
) -> Result<(), <D as Deserializer<'de>>::Error> where
    D: Deserializer<'de>, 

impl<T> Drop for LinkedList<T>

pub fn drop(&mut self)

Executes the destructor for this type.

impl<T> Encode for LinkedList<T> where
    T: Encode, 

pub fn size_hint(&self) -> usize

If possible give a hint of expected size of the encoding.

pub fn encode_to<W>(&self, dest: &mut W) where
    W: Output + ?Sized, 

Convert self to a slice and append it to the destination.

pub fn encode(&self) -> Vec<u8, Global>

Convert self to an owned vector.

pub fn using_encoded<R, F>(&self, f: F) -> R where
    F: FnOnce(&[u8]) -> R, 

Convert self to a slice and then invoke the given closure with it.

pub fn encoded_size(&self) -> usize

Calculates the encoded size.

impl<'_, T, LikeT> EncodeLike<&'_ [(LikeT,)]> for LinkedList<T> where
    T: EncodeLike<LikeT>,
    LikeT: Encode, 

impl<'_, T, LikeT> EncodeLike<LinkedList<LikeT>> for &'_ [(T,)] where
    T: EncodeLike<LikeT>,
    LikeT: Encode, 

impl<T, LikeT> EncodeLike<LinkedList<LikeT>> for LinkedList<T> where
    T: EncodeLike<LikeT>,
    LikeT: Encode, 

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

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

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

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, &'a T)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub 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<T> Extend<T> for LinkedList<T>

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

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, elem: T)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub 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<T> FromIterator<T> for LinkedList<T>

pub fn from_iter<I>(iter: I) -> LinkedList<T> where
    I: IntoIterator<Item = T>, 

Creates a value from an iterator.

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

pub fn hash<H>(&self, state: &mut H) where
    H: Hasher, 

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

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?

pub fn into_iter(self) -> IntoIter<T>

Consumes the list into an iterator yielding elements by value.

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?

pub fn into_iter(self) -> Iter<'a, T>

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?

pub fn into_iter(self) -> IterMut<'a, T>

Creates an iterator from a value.

impl<T> Ord for LinkedList<T> where
    T: Ord, 

pub fn cmp(&self, other: &LinkedList<T>) -> Ordering

This method returns an Ordering between self and other.

#[must_use]pub fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]pub fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]pub fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

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

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

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

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

This method tests for !=.

impl<T> PartialOrd<LinkedList<T>> for LinkedList<T> where
    T: PartialOrd<T>, 

pub fn partial_cmp(&self, other: &LinkedList<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use]pub fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use]pub fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use]pub fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]pub fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> Send for LinkedList<T> where
    T: Send, 

impl<T> Serialize for LinkedList<T> where
    T: Serialize, 

pub fn serialize<S>(
    &self,
    serializer: S
) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error> where
    S: Serializer, 

Serialize this value into the given Serde serializer.

impl<T> Sync for LinkedList<T> where
    T: Sync,