impl<T> LinkedList<T>

const fn new() -> Self

Creates an empty LinkedList.

Examples

use std::collections::LinkedList;

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

fn append(self: &mut Self, other: &mut Self)

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

impl<T, A: Allocator> LinkedList<T, A>

const fn new_in(alloc: A) -> Self

Constructs an empty LinkedList<T, A>.

Examples

#![feature(allocator_api)]

use std::alloc::System;
use std::collections::LinkedList;

let list: LinkedList<u32, _> = LinkedList::new_in(System);

fn iter(self: &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);

fn iter_mut(self: &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);

fn cursor_front(self: &Self) -> Cursor<'_, T, A>

Provides a cursor at the front element.

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

fn cursor_front_mut(self: &mut Self) -> CursorMut<'_, T, A>

Provides a cursor with editing operations at the front element.

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

fn cursor_back(self: &Self) -> Cursor<'_, T, A>

Provides a cursor at the back element.

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

fn cursor_back_mut(self: &mut Self) -> CursorMut<'_, T, A>

Provides a cursor with editing operations at the back element.

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

fn is_empty(self: &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());

fn len(self: &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);

fn clear(self: &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);

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

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

This operation should compute linearly in O(n) time.

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);

fn front(self: &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 std::collections::LinkedList;

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

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

fn front_mut(self: &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 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));

fn back(self: &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 std::collections::LinkedList;

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

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

fn back_mut(self: &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 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));

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

Adds an element to the front of 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);

fn push_front_mut(self: &mut Self, elt: T) -> &mut T

Adds an element to the front of the list, returning a reference to it.

This operation should compute in O(1) time.

Examples

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

let mut dl = LinkedList::from([1, 2, 3]);

let ptr = dl.push_front_mut(2);
*ptr += 4;
assert_eq!(dl.front().unwrap(), &6);

fn pop_front(self: &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);

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

Adds an element to the back of the 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());

fn push_back_mut(self: &mut Self, elt: T) -> &mut T

Adds an element to the back of the list, returning a reference to it.

This operation should compute in O(1) time.

Examples

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

let mut dl = LinkedList::from([1, 2, 3]);

let ptr = dl.push_back_mut(2);
*ptr += 4;
assert_eq!(dl.back().unwrap(), &6);

fn pop_back(self: &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));

fn split_off(self: &mut Self, at: usize) -> LinkedList<T, A>
where
    A: Clone

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);

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

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);

fn retain<F>(self: &mut Self, f: F)
where
    F: FnMut(&mut T) -> bool

Retains only the elements specified by the predicate.

In other words, remove all elements e for which f(&mut e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Examples

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

let mut d = LinkedList::new();

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

d.retain(|&mut x| x % 2 == 0);

assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);

Because the elements are visited exactly once in the original order, external state may be used to decide which elements to keep.

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

let mut d = LinkedList::new();

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

let keep = [false, true, false];
let mut iter = keep.iter();
d.retain(|_| *iter.next().unwrap());
assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);

fn extract_if<F>(self: &mut Self, filter: F) -> ExtractIf<'_, T, F, A>
where
    F: FnMut(&mut T) -> bool

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

If the closure returns true, the element is removed from the list and yielded. If the closure returns false, or panics, the element remains in the list and will not be yielded.

If the returned ExtractIf is not exhausted, e.g. because it is dropped without iterating or the iteration short-circuits, then the remaining elements will be retained. Use extract_if().for_each(drop) if you do not need the returned iterator.

The iterator also lets you mutate the value of each element in the closure, regardless of whether you choose to keep or remove it.

Examples

Splitting a list into even and odd values, reusing the original list:

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.extract_if(|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]);

impl<'a, T: 'a + Copy, A: Allocator> Extend for LinkedList<T, A>

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

fn extend_one(self: &mut Self, elem: &'a T)

impl<T> Any for LinkedList<T, A>

fn type_id(self: &Self) -> TypeId

impl<T> Borrow for LinkedList<T, A>

fn borrow(self: &Self) -> &T

impl<T> BorrowMut for LinkedList<T, A>

fn borrow_mut(self: &mut Self) -> &mut T

impl<T> CloneToUninit for LinkedList<T, A>

unsafe fn clone_to_uninit(self: &Self, dest: *mut u8)

impl<T> Default for LinkedList<T>

fn default() -> Self

Creates an empty LinkedList<T>.

impl<T> From for LinkedList<T, A>

fn from(t: T) -> T

Returns the argument unchanged.

impl<T> FromIterator for LinkedList<T>

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

impl<T> ToOwned for LinkedList<T, A>

fn to_owned(self: &Self) -> T

fn clone_into(self: &Self, target: &mut T)

impl<T, A> Freeze for LinkedList<T, A>

impl<T, A> RefUnwindSafe for LinkedList<T, A>

impl<T, A> Unpin for LinkedList<T, A>

impl<T, A> UnwindSafe for LinkedList<T, A>

impl<T, A: Allocator> Drop for LinkedList<T, A>

fn drop(self: &mut Self)

impl<T, A: Allocator> Extend for LinkedList<T, A>

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

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

impl<T, A: Allocator> IntoIterator for LinkedList<T, A>

fn into_iter(self: Self) -> IntoIter<T, A>

Consumes the list into an iterator yielding elements by value.

impl<T, N: usize> From for LinkedList<T>

fn from(arr: [T; N]) -> Self

Converts a [T; N] into a LinkedList<T>.

use std::collections::LinkedList;

let list1 = LinkedList::from([1, 2, 3, 4]);
let list2: LinkedList<_> = [1, 2, 3, 4].into();
assert_eq!(list1, list2);

impl<T, U> Into for LinkedList<T, A>

fn into(self: Self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of [From]<T> for U chooses to do.

impl<T, U> TryFrom for LinkedList<T, A>

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

impl<T, U> TryInto for LinkedList<T, A>

fn try_into(self: Self) -> Result<U, <U as TryFrom<T>>::Error>

impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A>

fn clone(self: &Self) -> Self

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

Overwrites the contents of self with a clone of the contents of source.

This method is preferred over simply assigning source.clone() to self, as it avoids reallocation of the nodes of the linked list. Additionally, if the element type T overrides clone_from(), this will reuse the resources of self's elements as well.

impl<T: Eq, A: Allocator> Eq for LinkedList<T, A>

impl<T: Hash, A: Allocator> Hash for LinkedList<T, A>

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

impl<T: Ord, A: Allocator> Ord for LinkedList<T, A>

fn cmp(self: &Self, other: &Self) -> Ordering

impl<T: PartialEq, A: Allocator> PartialEq for LinkedList<T, A>

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

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

impl<T: PartialOrd, A: Allocator> PartialOrd for LinkedList<T, A>

fn partial_cmp(self: &Self, other: &Self) -> Option<Ordering>

impl<T: Send, A: Allocator + Send> Send for LinkedList<T, A>

impl<T: Sync, A: Allocator + Sync> Sync for LinkedList<T, A>

impl<T: fmt::Debug, A: Allocator> Debug for LinkedList<T, A>

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