Struct std::collections::LinkedList [] [src]

pub struct LinkedList<T> {
    length: usize,
    list_head: Option<Box<Node<T>>>,
    list_tail: Rawlink<Node<T>>,
}

A doubly-linked list.

Fields

length
list_head
list_tail

Methods

impl<T> LinkedList<T>

impl<T> LinkedList<T>

fn new() -> LinkedList<T>

Creates an empty LinkedList.

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 a = LinkedList::new();
let mut b = LinkedList::new();
a.push_back(1);
a.push_back(2);
b.push_back(3);
b.push_back(4);

a.append(&mut b);

for e in &a {
    println!("{}", e); // prints 1, then 2, then 3, then 4
}
println!("{}", b.len()); // prints 0

fn iter(&self) -> Iter<T>

Provides a forward iterator.

fn iter_mut(&mut self) -> IterMut<T>

Provides a forward iterator with mutable references.

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

Trait Implementations

impl<T> Default for LinkedList<T>

fn default() -> LinkedList<T>

impl<T> Drop for LinkedList<T>

fn drop(&mut self)

impl<A> FromIterator<A> for LinkedList<A>

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

impl<T> IntoIterator for LinkedList<T>

type Item = T

type IntoIter = IntoIter<T>

fn into_iter(self) -> IntoIter<T>

impl<'a, T> IntoIterator for &'a LinkedList<T>

type Item = &'a T

type IntoIter = Iter<'a, T>

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

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

type Item = &'a mut T

type IntoIter = IterMut<'a, T>

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

impl<A> Extend<A> for LinkedList<A>

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

impl<'a, T> Extend<&'a T> for LinkedList<T> where T: Copy + 'a

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

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

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

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

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

fn assert_receiver_is_total_eq(&self)

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

fn partial_cmp(&self, other: &LinkedList<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<A> Ord for LinkedList<A> where A: Ord

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

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

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

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

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

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

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

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

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