Struct std::collections::LinkedList1.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]

Creates an empty LinkedList.

Examples

use std::collections::LinkedList;

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

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>

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>

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

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

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

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

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

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

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

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

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

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

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

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

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

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>

🔬 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

🔬 This is a nightly-only experimental API. (collection_placement #30172)

method name and placement protocol are subject to change

Returns a place for insertion at the front of the list.

Using this method with placement syntax is equivalent to push_front, but may be more efficient.

Examples

#![feature(collection_placement)]
#![feature(placement_in_syntax)]

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.front_place() <- 2;
list.front_place() <- 4;
assert!(list.iter().eq(&[4, 2]));Run

🔬 This is a nightly-only experimental API. (collection_placement #30172)

method name and placement protocol are subject to change

Returns a place for insertion at the back of the list.

Using this method with placement syntax is equivalent to push_back, but may be more efficient.

Examples

#![feature(collection_placement)]
#![feature(placement_in_syntax)]

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.back_place() <- 2;
list.back_place() <- 4;
assert!(list.iter().eq(&[2, 4]));Run

Trait Implementations

impl<T> FromIterator<T> for LinkedList<T>
[src]

Creates a value from an iterator. Read more

impl<T> Sync for LinkedList<T> where
    T: Sync
[src]

impl<T> Ord for LinkedList<T> where
    T: Ord
[src]

This method returns an Ordering between self and other. Read more

Compares and returns the maximum of two values. Read more

Compares and returns the minimum of two values. Read more

impl<T> Drop for LinkedList<T>
[src]

Executes the destructor for this type. Read more

impl<T> Send for LinkedList<T> where
    T: Send
[src]

impl<T> Eq for LinkedList<T> where
    T: Eq
[src]

impl<T> Hash for LinkedList<T> where
    T: Hash
[src]

Feeds this value into the given [Hasher]. Read more

Feeds a slice of this type into the given [Hasher]. Read more

impl<T> Clone for LinkedList<T> where
    T: Clone
[src]

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

impl<'a, T> IntoIterator for &'a LinkedList<T>
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Important traits for Iter<'a, T>

Creates an iterator from a value. Read more

impl<T> IntoIterator for LinkedList<T>
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Important traits for IntoIter<T>

Consumes the list into an iterator yielding elements by value.

impl<'a, T> IntoIterator for &'a mut LinkedList<T>
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Important traits for IterMut<'a, T>

Creates an iterator from a value. Read more

impl<T> Default for LinkedList<T>
[src]

Creates an empty LinkedList<T>.

impl<T> PartialEq<LinkedList<T>> for LinkedList<T> where
    T: PartialEq<T>, 
[src]

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

impl<T> Extend<T> for LinkedList<T>
[src]

Extends a collection with the contents of an iterator. Read more

impl<'a, T> Extend<&'a T> for LinkedList<T> where
    T: 'a + Copy
1.2.0
[src]

Extends a collection with the contents of an iterator. Read more

impl<T> PartialOrd<LinkedList<T>> for LinkedList<T> where
    T: PartialOrd<T>, 
[src]

This method returns an ordering between self and other values if one exists. Read more

This method tests less than (for self and other) and is used by the < operator. Read more

This method tests less than or equal to (for self and other) and is used by the <= operator. Read more

This method tests greater than (for self and other) and is used by the > operator. Read more

This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more

impl<T> Debug for LinkedList<T> where
    T: Debug
[src]

Formats the value using the given formatter. Read more