Struct std::collections::LinkedList

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>

fn new() -> LinkedList<T>

Creates an empty LinkedList.

Examples

use std::collections::LinkedList;

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

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

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 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.

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.

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.

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.

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.

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

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)

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

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

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.

Panics

Panics if at > len.

This operation should compute in O(n) time.

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

fn front_place(&mut self) -> FrontPlace<T>

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

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

fn back_place(&mut self) -> BackPlace<T>

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

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

Trait Implementations

impl<T> Send for LinkedList<T> where T: Send

impl<T> Default for LinkedList<T>

fn default() -> LinkedList<T>

Creates an empty LinkedList<T>.

impl<T> Hash for LinkedList<T> where T: Hash

fn hash<H>(&self, state: &mut H) where H: Hasher

Feeds this value into the state given, updating the hasher as necessary.

fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher

Feeds a slice of this type into the state provided.

impl<T> PartialEq<LinkedList<T>> for LinkedList<T> where T: PartialEq<T>

fn eq(&self, other: &LinkedList<T>) -> bool

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

fn ne(&self, other: &LinkedList<T>) -> bool

This method tests for !=.

impl<T> PartialOrd<LinkedList<T>> for LinkedList<T> where T: PartialOrd<T>

fn partial_cmp(&self, other: &LinkedList<T>) -> Option<Ordering>

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

fn lt(&self, other: &Rhs) -> bool

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

fn le(&self, other: &Rhs) -> bool

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

fn gt(&self, other: &Rhs) -> bool

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

fn ge(&self, other: &Rhs) -> bool

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

impl<T> Clone for LinkedList<T> where T: Clone

fn clone(&self) -> LinkedList<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Drop for LinkedList<T>

fn drop(&mut self)

A method called when the value goes out of scope.

impl<T> Eq for LinkedList<T> where T: Eq

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?

fn into_iter(self) -> IntoIter<T>

Consumes the list into an iterator yielding elements by value.

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?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

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?

fn into_iter(self) -> IterMut<'a, T>

Creates an iterator from a value.

impl<T> Debug for LinkedList<T> where T: Debug

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

Formats the value using the given formatter.

impl<T> Ord for LinkedList<T> where T: Ord

fn cmp(&self, other: &LinkedList<T>) -> Ordering

This method returns an Ordering between self and other.

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

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

Creates a value from an iterator.

impl<T> Sync for LinkedList<T> where T: Sync

impl<T> Extend<T> for LinkedList<T>

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

Extends a collection with the contents of an iterator.

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>

Extends a collection with the contents of an iterator.