Struct LinkedList

pub struct LinkedList<T, A: Allocator = Global> { pub(in ::collections::linked_list) head: Option<NonNull<Node<T>>>, pub(in ::collections::linked_list) tail: Option<NonNull<Node<T>>>, pub(in ::collections::linked_list) len: usize, pub(in ::collections::linked_list) alloc: A, pub(in ::collections::linked_list) marker: PhantomData<Box<Node<T>, A>> }

A doubly-linked list with owned nodes.

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

A LinkedList with a known list of items can be initialized from an array:

use std::collections::LinkedList;

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

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.

Fields

head: Option<NonNull<Node<T>>>
tail: Option<NonNull<Node<T>>>
len: usize
alloc: A
marker: PhantomData<Box<Node<T>, A>>

Implementations

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(&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<i32, System> = LinkedList::new_in(System);

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

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

fn cursor_front(&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(&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) -> 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(&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) -> 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) -> 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(&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, 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) -> 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(&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) -> 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(&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(&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(&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

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(&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(&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(&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

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(&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(&mut self, at: usize) -> LinkedList<T, A>
where
    A: AllocatorClone,

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(&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>(&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>(&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<T, A: Allocator> LinkedList<T, A>

unsafe fn push_front_node(&mut self, node: NonNull<Node<T>>)

Adds the given node to the front of the list.

Safety

node must point to a valid node in the list's allocator. This method takes ownership of the node, so the pointer should not be used again.

fn pop_front_node(&mut self) -> Option<Box<Node<T>, &A>>

Removes and returns the node at the front of the list.

unsafe fn push_back_node(&mut self, node: NonNull<Node<T>>)

Adds the given node to the back of the list.

Safety

node must point to a valid node in the list's allocator. This method takes ownership of the node, so the pointer should not be used again.

fn pop_back_node(&mut self) -> Option<Box<Node<T>, &A>>

Removes and returns the node at the back of the list.

Unlinks the specified node from the current list.

Warning: this will not check that the provided node belongs to the current list.

This method takes care not to create mutable references to element, to maintain validity of aliasing pointers.

unsafe fn splice_nodes(&mut self, existing_prev: Option<NonNull<Node<T>>>, existing_next: Option<NonNull<Node<T>>>, splice_start: NonNull<Node<T>>, splice_end: NonNull<Node<T>>, splice_length: usize)

Splices a series of nodes between two existing nodes.

Warning: this will not check that the provided node belongs to the two existing lists.

fn detach_all_nodes(self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)>

Detaches all nodes from a linked list as a series of nodes.

unsafe fn split_off_before_node(&mut self, split_node: Option<NonNull<Node<T>>>, at: usize) -> Self
where
    A: AllocatorClone,
unsafe fn split_off_after_node(&mut self, split_node: Option<NonNull<Node<T>>>, at: usize) -> Self
where
    A: AllocatorClone,

Trait Implementations

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

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

impl<I: IntoIterator, A: Allocator> SpecExtend<I> for LinkedList<I::Item, A>

fn spec_extend(&mut self, iter: I)

impl<T> Default for LinkedList<T>

fn default() -> Self

Creates an empty LinkedList<T>.

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

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

impl<T> SpecExtend<LinkedList<T>> for LinkedList<T>

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

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

fn drop(&mut self)

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

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

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

type Item = T;
type IntoIter = IntoIter<T, A>;
fn into_iter(self) -> IntoIter<T, A>

Consumes the list into an iterator yielding elements by value.

impl<T, const N: usize> From<[T; N]> 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: Clone, A: Allocator + Clone> Clone for LinkedList<T, A>

fn clone(&self) -> Self
fn clone_from(&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: Debug, A: Allocator> Debug for LinkedList<T, A>

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

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, state: &mut H)

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

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

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

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

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

fn partial_cmp(&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>

Auto Trait Implementations

impl<T, A> Freeze for LinkedList<T, A> where Option<NonNull<Node<T>>>: Freeze + Freeze, A: Freeze, PhantomData<Box<Node<T>, A>>: Freeze,

impl<T, A> RefUnwindSafe for LinkedList<T, A> where Option<NonNull<Node<T>>>: RefUnwindSafe + RefUnwindSafe, A: RefUnwindSafe, PhantomData<Box<Node<T>, A>>: RefUnwindSafe,

impl<T, A> Unpin for LinkedList<T, A> where Option<NonNull<Node<T>>>: Unpin + Unpin, A: Unpin, PhantomData<Box<Node<T>, A>>: Unpin,

impl<T, A> UnsafeUnpin for LinkedList<T, A> where Option<NonNull<Node<T>>>: UnsafeUnpin + UnsafeUnpin, A: UnsafeUnpin, PhantomData<Box<Node<T>, A>>: UnsafeUnpin,

impl<T, A> UnwindSafe for LinkedList<T, A> where Option<NonNull<Node<T>>>: UnwindSafe + UnwindSafe, A: UnwindSafe, PhantomData<Box<Node<T>, A>>: UnwindSafe,

Blanket Implementations

impl<T> Any for LinkedList<T, A> where T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for LinkedList<T, A> where T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for LinkedList<T, A> where T: ?Sized,

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

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

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

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

fn from(t: T) -> T

Returns the argument unchanged.

impl<T> SizeHint for LinkedList<T, A> where T: ?Sized,

fn lower_bound(&self) -> usize
fn upper_bound(&self) -> Option<usize>

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

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

type Owned = T;
fn to_owned(&self) -> T
fn clone_into(&self, target: &mut T)

impl<T, U> Into<U> for LinkedList<T, A> where U: From<T>,

fn into(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<U> for LinkedList<T, A> where U: Into<T>,

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

impl<T, U> TryInto<U> for LinkedList<T, A> where U: TryFrom<T>,

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