logo

Struct wplot::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]);

NOTE: 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

Creates an empty LinkedList.

Examples
use std::collections::LinkedList;

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

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

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

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);
🔬 This is a nightly-only experimental API. (linked_list_cursors)

Provides a cursor at the front element.

The cursor is pointing to the “ghost” non-element if the list is empty.

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

Provides a cursor with editing operations at the front element.

The cursor is pointing to the “ghost” non-element if the list is empty.

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

Provides a cursor at the back element.

The cursor is pointing to the “ghost” non-element if the list is empty.

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

Provides a cursor with editing operations at the back element.

The cursor is pointing to the “ghost” non-element if the list is empty.

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

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

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

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

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

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

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

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

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

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

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples
use std::collections::LinkedList;

let mut d = LinkedList::new();
d.push_back(1);
d.push_back(3);
assert_eq!(3, *d.back().unwrap());

Removes the last element from a list and returns it, or None if it is empty.

This operation should compute in O(1) time.

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

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);
🔬 This is a nightly-only experimental API. (linked_list_remove)

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);
🔬 This is a nightly-only experimental API. (drain_filter)

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

Trait Implementations

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Creates an empty LinkedList<T>.

Executes the destructor for this type. Read more

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

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

Extends a collection with exactly one element.

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

Reserves capacity in a collection for the given number of additional elements. Read more

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

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

Extends a collection with exactly one element.

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

Reserves capacity in a collection for the given number of additional elements. Read more

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

Creates a value from an iterator. Read more

Collects items from a parallel iterator into a freshly allocated linked list.

Creates an instance of the collection from the parallel iterator par_iter. Read more

Feeds this value into the given Hasher. Read more

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

Consumes the list into an iterator yielding elements by value.

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

The type of item that the parallel iterator will produce.

The parallel iterator type that will be created.

Converts self into a parallel iterator. Read more

The type of item that the parallel iterator will produce.

The parallel iterator type that will be created.

Converts self into a parallel iterator. Read more

The type of item that the parallel iterator will produce.

The parallel iterator type that will be created.

Converts self into a parallel iterator. Read more

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

Restrict a value to a certain interval. Read more

Extends a linked list with copied items from a parallel iterator.

Extends an instance of the collection with the elements drawn from the parallel iterator par_iter. Read more

Extends a linked list with items from a parallel iterator.

Extends an instance of the collection with the elements drawn from the parallel iterator par_iter. Read more

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

This method tests for !=.

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

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Performs the conversion.

The type of the parallel iterator that will be returned.

The type of item that the parallel iterator will produce. This will typically be an &'data T reference type. Read more

Converts self into a parallel iterator. Read more

The type of iterator that will be created.

The type of item that will be produced; this is typically an &'data mut T reference. Read more

Creates the parallel iterator from self. Read more

The alignment of pointer.

The type for initializers.

Initializes a with the given initializer. Read more

Dereferences the given pointer. Read more

Mutably dereferences the given pointer. Read more

Drops the object pointed to by the given pointer. Read more

Read this value from the supplied reader. Same as ReadEndian::read_from_little_endian().

Read this value from the supplied reader. Same as ReadEndian::read_from_big_endian().

Read this value from the supplied reader. Same as ReadEndian::read_from_native_endian().

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

Uses borrowed data to replace owned data, usually by cloning. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.

Performs the conversion.