Struct std::collections::linked_list::LinkedList 1.0.0[−][src]
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.
Almost always it is better to use Vec
or VecDeque
instead of
LinkedList
. In general, array-based containers are faster,
more memory efficient and make better use of CPU cache.
Methods
impl<T> LinkedList<T>
[src]
impl<T> LinkedList<T>
pub fn new() -> LinkedList<T>
[src]
pub fn new() -> LinkedList<T>
Creates an empty LinkedList
.
Examples
use std::collections::LinkedList; let list: LinkedList<u32> = LinkedList::new();Run
pub fn append(&mut self, other: &mut LinkedList<T>)
[src]
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());Run
ⓘImportant traits for Iter<'a, T>pub fn iter(&self) -> Iter<T>
[src]
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);Run
ⓘImportant traits for IterMut<'a, T>pub fn iter_mut(&mut self) -> IterMut<T>
[src]
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);Run
pub fn is_empty(&self) -> bool
[src]
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());Run
pub fn len(&self) -> usize
[src]
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);Run
pub fn clear(&mut self)
[src]
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);Run
pub fn contains(&self, x: &T) -> bool where
T: PartialEq<T>,
1.12.0[src]
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);Run
pub fn front(&self) -> Option<&T>
[src]
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));Run
pub fn front_mut(&mut self) -> Option<&mut T>
[src]
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));Run
pub fn back(&self) -> Option<&T>
[src]
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));Run
pub fn back_mut(&mut self) -> Option<&mut T>
[src]
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));Run
pub fn push_front(&mut self, elt: T)
[src]
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);Run
pub fn pop_front(&mut self) -> Option<T>
[src]
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);Run
pub fn push_back(&mut self, elt: T)
[src]
pub fn push_back(&mut self, elt: T)
Appends an element to the back of a list
Examples
use std::collections::LinkedList; let mut d = LinkedList::new(); d.push_back(1); d.push_back(3); assert_eq!(3, *d.back().unwrap());Run
pub fn pop_back(&mut self) -> Option<T>
[src]
pub fn pop_back(&mut self) -> Option<T>
Removes the last element from a list and returns it, or None
if
it is empty.
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));Run
pub fn split_off(&mut self, at: usize) -> LinkedList<T>
[src]
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 splitted = d.split_off(2); assert_eq!(splitted.pop_front(), Some(1)); assert_eq!(splitted.pop_front(), None);Run
ⓘImportant traits for DrainFilter<'a, T, F>pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<T, F> where
F: FnMut(&mut T) -> bool,
[src]
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
#43244)
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]);Run
Trait Implementations
impl<T> Drop for LinkedList<T>
[src]
impl<T> Drop for LinkedList<T>
impl<T> Eq for LinkedList<T> where
T: Eq,
[src]
impl<T> Eq for LinkedList<T> where
T: Eq,
impl<T> Ord for LinkedList<T> where
T: Ord,
[src]
impl<T> Ord for LinkedList<T> where
T: Ord,
fn cmp(&self, other: &LinkedList<T>) -> Ordering
[src]
fn cmp(&self, other: &LinkedList<T>) -> Ordering
This method returns an Ordering
between self
and other
. Read more
fn max(self, other: Self) -> Self
1.21.0[src]
fn max(self, other: Self) -> Self
Compares and returns the maximum of two values. Read more
fn min(self, other: Self) -> Self
1.21.0[src]
fn min(self, other: Self) -> Self
Compares and returns the minimum of two values. Read more
impl<T> Hash for LinkedList<T> where
T: Hash,
[src]
impl<T> Hash for LinkedList<T> where
T: Hash,
fn hash<H>(&self, state: &mut H) where
H: Hasher,
[src]
fn hash<H>(&self, state: &mut H) where
H: Hasher,
Feeds this value into the given [Hasher
]. Read more
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
Feeds a slice of this type into the given [Hasher
]. Read more
impl<T> Sync for LinkedList<T> where
T: Sync,
[src]
impl<T> Sync for LinkedList<T> where
T: Sync,
impl<T> FromIterator<T> for LinkedList<T>
[src]
impl<T> FromIterator<T> for LinkedList<T>
fn from_iter<I>(iter: I) -> LinkedList<T> where
I: IntoIterator<Item = T>,
[src]
fn from_iter<I>(iter: I) -> LinkedList<T> where
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more
impl<T> Clone for LinkedList<T> where
T: Clone,
[src]
impl<T> Clone for LinkedList<T> where
T: Clone,
fn clone(&self) -> LinkedList<T>
[src]
fn clone(&self) -> LinkedList<T>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
[src]
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
impl<T> Debug for LinkedList<T> where
T: Debug,
[src]
impl<T> Debug for LinkedList<T> where
T: Debug,
fn fmt(&self, f: &mut Formatter) -> Result<(), Error>
[src]
fn fmt(&self, f: &mut Formatter) -> Result<(), Error>
Formats the value using the given formatter. Read more
impl<'a, T> IntoIterator for &'a LinkedList<T>
[src]
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?
ⓘImportant traits for Iter<'a, T>fn into_iter(self) -> Iter<'a, T>
[src]
fn into_iter(self) -> Iter<'a, T>
Creates an iterator from a value. Read more
impl<T> IntoIterator for LinkedList<T>
[src]
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?
ⓘImportant traits for IntoIter<T>fn into_iter(self) -> IntoIter<T>
[src]
fn into_iter(self) -> IntoIter<T>
Consumes the list into an iterator yielding elements by value.
impl<'a, T> IntoIterator for &'a mut LinkedList<T>
[src]
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?
ⓘImportant traits for IterMut<'a, T>fn into_iter(self) -> IterMut<'a, T>
[src]
fn into_iter(self) -> IterMut<'a, T>
Creates an iterator from a value. Read more
impl<'a, T> Extend<&'a T> for LinkedList<T> where
T: 'a + Copy,
1.2.0[src]
impl<'a, T> Extend<&'a T> for LinkedList<T> where
T: 'a + Copy,
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = &'a T>,
[src]
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = &'a T>,
Extends a collection with the contents of an iterator. Read more
impl<T> Extend<T> for LinkedList<T>
[src]
impl<T> Extend<T> for LinkedList<T>
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = T>,
[src]
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = T>,
Extends a collection with the contents of an iterator. Read more
impl<T> Default for LinkedList<T>
[src]
impl<T> Default for LinkedList<T>
fn default() -> LinkedList<T>
[src]
fn default() -> LinkedList<T>
Creates an empty LinkedList<T>
.
impl<T> Send for LinkedList<T> where
T: Send,
[src]
impl<T> Send for LinkedList<T> where
T: Send,
impl<T> PartialEq<LinkedList<T>> for LinkedList<T> where
T: PartialEq<T>,
[src]
impl<T> PartialEq<LinkedList<T>> for LinkedList<T> where
T: PartialEq<T>,
fn eq(&self, other: &LinkedList<T>) -> bool
[src]
fn eq(&self, other: &LinkedList<T>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &LinkedList<T>) -> bool
[src]
fn ne(&self, other: &LinkedList<T>) -> bool
This method tests for !=
.
impl<T> PartialOrd<LinkedList<T>> for LinkedList<T> where
T: PartialOrd<T>,
[src]
impl<T> PartialOrd<LinkedList<T>> for LinkedList<T> where
T: PartialOrd<T>,
fn partial_cmp(&self, other: &LinkedList<T>) -> Option<Ordering>
[src]
fn partial_cmp(&self, other: &LinkedList<T>) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, other: &Rhs) -> bool
[src]
fn lt(&self, other: &Rhs) -> bool
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, other: &Rhs) -> bool
[src]
fn le(&self, other: &Rhs) -> bool
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
fn gt(&self, other: &Rhs) -> bool
[src]
fn gt(&self, other: &Rhs) -> bool
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, other: &Rhs) -> bool
[src]
fn ge(&self, other: &Rhs) -> bool
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more