pub struct LinkedList<T, A = Global>where
A: Allocator,{ /* private fields */ }
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.
impl<T> LinkedList<T>
pub const fn new() -> LinkedList<T>
Creates an empty LinkedList.
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.
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> LinkedList<T, A>where
A: Allocator,pub const fn new_in(alloc: A) -> LinkedList<T, A>
allocator_api #32838)
Constructs an empty LinkedList<T, A>.
#![feature(allocator_api)] use std::alloc::System; use std::collections::LinkedList; let list: LinkedList<u32, _> = LinkedList::new_in(System);
pub fn iter(&self) -> Iter<'_, T> ⓘ
Provides a forward iterator.
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.
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, A>
linked_list_cursors #58533)
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, A>
linked_list_cursors #58533)
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, A>
linked_list_cursors #58533)
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, A>
linked_list_cursors #58533)
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.
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.
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.
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) -> boolwhere
T: PartialEq,Returns true if the LinkedList contains an element equal to the given value.
This operation should compute linearly in O(n) time.
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.
This operation should compute in O(1) time.
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.
This operation should compute in O(1) time.
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.
This operation should compute in O(1) time.
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.
This operation should compute in O(1) time.
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 to the front of the list.
This operation should compute in O(1) time.
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 push_front_mut(&mut self, elt: T) -> &mut T
push_mut #135974)
Adds an element to the front of the list, returning a reference to it.
This operation should compute in O(1) time.
#![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);
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.
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)
Adds an element to the back of the list.
This operation should compute in O(1) time.
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 push_back_mut(&mut self, elt: T) -> &mut T
push_mut #135974)
Adds an element to the back of the list, returning a reference to it.
This operation should compute in O(1) time.
#![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);
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.
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, 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 if at > len.
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
linked_list_remove #69210)
Removes the element at the given index and returns it.
This operation should compute in O(n) time.
Panics if at >= len
#![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 retain<F>(&mut self, f: F)where
F: FnMut(&mut T) -> bool,linked_list_retain #114135)
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.
#![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);
pub 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.
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> Clone for LinkedList<T, A>where
T: Clone,
A: Allocator + Clone,fn clone_from(&mut self, source: &LinkedList<T, A>)
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.
fn clone(&self) -> LinkedList<T, A>
impl<T, A> Debug for LinkedList<T, A>where
T: Debug,
A: Allocator,fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>
impl<T> Default for LinkedList<T>
fn default() -> LinkedList<T>
Creates an empty LinkedList<T>.
impl<T, A> Drop for LinkedList<T, A>where
A: Allocator,impl<'a, T, A> Extend<&'a T> for LinkedList<T, A>where
T: 'a + Copy,
A: Allocator,fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = &'a T>,fn extend_one(&mut self, _: &'a T)
extend_one #72631)
fn extend_reserve(&mut self, additional: usize)
extend_one #72631)
impl<T, A> Extend<T> for LinkedList<T, A>where
A: Allocator,fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = T>,fn extend_one(&mut self, elem: T)
extend_one #72631)
fn extend_reserve(&mut self, additional: usize)
extend_one #72631)
impl<T, const N: usize> From<[T; N]> for LinkedList<T>
fn from(arr: [T; N]) -> LinkedList<T>
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> FromIterator<T> for LinkedList<T>
fn from_iter<I>(iter: I) -> LinkedList<T>where
I: IntoIterator<Item = T>,impl<T, A> Hash for LinkedList<T, A>where
T: Hash,
A: Allocator,fn hash<H>(&self, state: &mut H)where
H: Hasher,fn hash_slice<H>(data: &[Self], state: &mut H)where
H: Hasher,
Self: Sized,impl<'a, T, A> IntoIterator for &'a LinkedList<T, A>where
A: Allocator,type Item = &'a T
type IntoIter = Iter<'a, T>
fn into_iter(self) -> Iter<'a, T> ⓘ
impl<'a, T, A> IntoIterator for &'a mut LinkedList<T, A>where
A: Allocator,type Item = &'a mut T
type IntoIter = IterMut<'a, T>
fn into_iter(self) -> IterMut<'a, T> ⓘ
impl<T, A> IntoIterator for LinkedList<T, A>where
A: Allocator,fn into_iter(self) -> IntoIter<T, A> ⓘ
Consumes the list into an iterator yielding elements by value.
type Item = T
type IntoIter = IntoIter<T, A>
impl<T, A> Ord for LinkedList<T, A>where
T: Ord,
A: Allocator,fn cmp(&self, other: &LinkedList<T, A>) -> Ordering
fn max(self, other: Self) -> Selfwhere
Self: Sized,fn min(self, other: Self) -> Selfwhere
Self: Sized,fn clamp(self, min: Self, max: Self) -> Selfwhere
Self: Sized,impl<T, A> PartialEq for LinkedList<T, A>where
T: PartialEq,
A: Allocator,fn eq(&self, other: &LinkedList<T, A>) -> bool
self and other values to be equal, and is used by ==.fn ne(&self, other: &LinkedList<T, A>) -> bool
!=. The default implementation is almost always sufficient, and should not be overridden without very good reason.impl<T, A> PartialOrd for LinkedList<T, A>where
T: PartialOrd,
A: Allocator,fn partial_cmp(&self, other: &LinkedList<T, A>) -> Option<Ordering>
fn lt(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
fn gt(&self, other: &Rhs) -> bool
fn ge(&self, other: &Rhs) -> bool
impl<T, A> Eq for LinkedList<T, A>where
T: Eq,
A: Allocator,impl<T, A> Send for LinkedList<T, A>where
T: Send,
A: Allocator + Send,impl<T, A> Sync for LinkedList<T, A>where
T: Sync,
A: Allocator + Sync,impl<T, A> Freeze for LinkedList<T, A>where
A: Freeze,impl<T, A> RefUnwindSafe for LinkedList<T, A>where
A: RefUnwindSafe,
T: RefUnwindSafe,impl<T, A> Unpin for LinkedList<T, A>where
A: Unpin,impl<T, A> UnwindSafe for LinkedList<T, A>where
A: UnwindSafe,
T: RefUnwindSafe + UnwindSafe,impl<T> Any for Twhere
T: 'static + ?Sized,impl<T> Borrow<T> for Twhere
T: ?Sized,impl<T> BorrowMut<T> for Twhere
T: ?Sized,impl<T> CloneToUninit for Twhere
T: Clone,unsafe fn clone_to_uninit(&self, dest: *mut u8)
clone_to_uninit #126799)
impl<T> From<T> for T
fn from(t: T) -> T
Returns the argument unchanged.
impl<T, U> Into<U> for Twhere
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> ToOwned for Twhere
T: Clone,type Owned = T
fn to_owned(&self) -> T
fn clone_into(&self, target: &mut T)
impl<T, U> TryFrom<U> for Twhere
U: Into<T>,type Error = Infallible
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
impl<T, U> TryInto<U> for Twhere
U: TryFrom<T>,
© 2010 The Rust Project Developers
Licensed under the Apache License, Version 2.0 or the MIT license, at your option.
https://doc.rust-lang.org/std/collections/linked_list/struct.LinkedList.html