Struct std::collections::LinkedList
1.0.0 · source · [−]pub struct LinkedList<T> { /* private fields */ }
Expand description
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]);
RunNOTE: 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
sourceimpl<T> LinkedList<T>
impl<T> LinkedList<T>
const: 1.39.0 · sourcepub const fn new() -> LinkedList<T>
pub const fn new() -> LinkedList<T>
sourcepub fn append(&mut self, other: &mut LinkedList<T>)
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());
Runsourcepub fn iter(&self) -> Iter<'_, T>ⓘNotable traits for Iter<'a, T>impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;
pub fn iter(&self) -> Iter<'_, T>ⓘNotable traits for Iter<'a, T>impl<'a, T> Iterator for Iter<'a, T> type Item = &'a 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);
Runsourcepub fn iter_mut(&mut self) -> IterMut<'_, T>ⓘNotable traits for IterMut<'a, T>impl<'a, T> Iterator for IterMut<'a, T> type Item = &'a mut T;
pub fn iter_mut(&mut self) -> IterMut<'_, T>ⓘNotable traits for IterMut<'a, T>impl<'a, T> Iterator for IterMut<'a, T> type Item = &'a mut 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);
Runsourcepub fn cursor_front(&self) -> Cursor<'_, T>
🔬This is a nightly-only experimental API. (linked_list_cursors
#58533)
pub fn cursor_front(&self) -> Cursor<'_, T>
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.
sourcepub fn cursor_front_mut(&mut self) -> CursorMut<'_, T>
🔬This is a nightly-only experimental API. (linked_list_cursors
#58533)
pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T>
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.
sourcepub fn cursor_back(&self) -> Cursor<'_, T>
🔬This is a nightly-only experimental API. (linked_list_cursors
#58533)
pub fn cursor_back(&self) -> Cursor<'_, T>
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.
sourcepub fn cursor_back_mut(&mut self) -> CursorMut<'_, T>
🔬This is a nightly-only experimental API. (linked_list_cursors
#58533)
pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T>
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.
sourcepub fn clear(&mut self)
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);
Run1.12.0 · sourcepub fn contains(&self, x: &T) -> boolwhere
T: PartialEq<T>,
pub fn contains(&self, x: &T) -> boolwhere
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);
Runsourcepub fn front_mut(&mut self) -> Option<&mut T>
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.
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));
Runsourcepub fn back_mut(&mut self) -> Option<&mut T>
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.
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));
Runsourcepub fn push_front(&mut self, elt: T)
pub fn push_front(&mut self, elt: T)
sourcepub fn pop_front(&mut self) -> Option<T>
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);
Runsourcepub fn split_off(&mut self, at: usize) -> LinkedList<T>
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);
Runsourcepub fn remove(&mut self, at: usize) -> T
🔬This is a nightly-only experimental API. (linked_list_remove
#69210)
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
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);
Runsourcepub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>ⓘNotable traits for DrainFilter<'_, T, F>impl<T, F> Iterator for DrainFilter<'_, T, F>where
F: FnMut(&mut T) -> bool, type Item = T;
where
F: FnMut(&mut T) -> bool,
🔬This is a nightly-only experimental API. (drain_filter
#43244)
pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>ⓘNotable traits for DrainFilter<'_, T, F>impl<T, F> Iterator for DrainFilter<'_, T, F>where
F: FnMut(&mut T) -> bool, type Item = T;
where
F: FnMut(&mut T) -> bool,
F: FnMut(&mut T) -> bool, type Item = T;
drain_filter
#43244)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]);
RunTrait Implementations
sourceimpl<T> Clone for LinkedList<T>where
T: Clone,
impl<T> Clone for LinkedList<T>where
T: Clone,
sourcefn clone(&self) -> LinkedList<T>
fn clone(&self) -> LinkedList<T>
sourcefn clone_from(&mut self, other: &LinkedList<T>)
fn clone_from(&mut self, other: &LinkedList<T>)
source
. Read moresourceimpl<T> Debug for LinkedList<T>where
T: Debug,
impl<T> Debug for LinkedList<T>where
T: Debug,
sourceimpl<T> Default for LinkedList<T>
impl<T> Default for LinkedList<T>
sourcefn default() -> LinkedList<T>
fn default() -> LinkedList<T>
Creates an empty LinkedList<T>
.
sourceimpl<T> Drop for LinkedList<T>
impl<T> Drop for LinkedList<T>
1.2.0 · sourceimpl<'a, T> Extend<&'a T> for LinkedList<T>where
T: 'a + Copy,
impl<'a, T> Extend<&'a T> for LinkedList<T>where
T: 'a + Copy,
sourcefn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = &'a T>,
fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = &'a T>,
sourcefn extend_one(&mut self, &'a T)
fn extend_one(&mut self, &'a T)
extend_one
#72631)sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
#72631)sourceimpl<T> Extend<T> for LinkedList<T>
impl<T> Extend<T> for LinkedList<T>
sourcefn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = T>,
fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = T>,
sourcefn extend_one(&mut self, elem: T)
fn extend_one(&mut self, elem: T)
extend_one
#72631)sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
#72631)1.56.0 · sourceimpl<T, const N: usize> From<[T; N]> for LinkedList<T>
impl<T, const N: usize> From<[T; N]> for LinkedList<T>
sourcefn from(arr: [T; N]) -> 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);
Runsourceimpl<T> FromIterator<T> for LinkedList<T>
impl<T> FromIterator<T> for LinkedList<T>
sourcefn from_iter<I>(iter: I) -> LinkedList<T>where
I: IntoIterator<Item = T>,
fn from_iter<I>(iter: I) -> LinkedList<T>where
I: IntoIterator<Item = T>,
sourceimpl<T> Hash for LinkedList<T>where
T: Hash,
impl<T> Hash for LinkedList<T>where
T: Hash,
sourceimpl<'a, T> IntoIterator for &'a LinkedList<T>
impl<'a, T> IntoIterator for &'a LinkedList<T>
sourceimpl<'a, T> IntoIterator for &'a mut LinkedList<T>
impl<'a, T> IntoIterator for &'a mut LinkedList<T>
sourceimpl<T> IntoIterator for LinkedList<T>
impl<T> IntoIterator for LinkedList<T>
sourceimpl<T> Ord for LinkedList<T>where
T: Ord,
impl<T> Ord for LinkedList<T>where
T: Ord,
sourcefn cmp(&self, other: &LinkedList<T>) -> Ordering
fn cmp(&self, other: &LinkedList<T>) -> Ordering
1.21.0 · sourceconst fn max(self, other: Self) -> Self
const fn max(self, other: Self) -> Self
1.21.0 · sourceconst fn min(self, other: Self) -> Self
const fn min(self, other: Self) -> Self
1.50.0 · sourceconst fn clamp(self, min: Self, max: Self) -> Selfwhere
Self: PartialOrd<Self>,
const fn clamp(self, min: Self, max: Self) -> Selfwhere
Self: PartialOrd<Self>,
sourceimpl<T> PartialEq<LinkedList<T>> for LinkedList<T>where
T: PartialEq<T>,
impl<T> PartialEq<LinkedList<T>> for LinkedList<T>where
T: PartialEq<T>,
sourcefn eq(&self, other: &LinkedList<T>) -> bool
fn eq(&self, other: &LinkedList<T>) -> bool
sourcefn ne(&self, other: &LinkedList<T>) -> bool
fn ne(&self, other: &LinkedList<T>) -> bool
!=
. The default implementation is almost always
sufficient, and should not be overridden without very good reason. Read moresourceimpl<T> PartialOrd<LinkedList<T>> for LinkedList<T>where
T: PartialOrd<T>,
impl<T> PartialOrd<LinkedList<T>> for LinkedList<T>where
T: PartialOrd<T>,
sourcefn partial_cmp(&self, other: &LinkedList<T>) -> Option<Ordering>
fn partial_cmp(&self, other: &LinkedList<T>) -> Option<Ordering>
sourceconst fn le(&self, other: &Rhs) -> bool
const fn le(&self, other: &Rhs) -> bool
self
and other
) and is used by the <=
operator. Read more