LinkedList in std::collections - Rust (original) (raw)
Struct LinkedList
1.0.0 · Source
pub struct LinkedList<T, A = Global>
where
A: Allocator,
{ /* 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.
1.0.0 (const: 1.39.0) · Source
Creates an empty LinkedList.
§Examples
use std::collections::LinkedList;
let list: LinkedList<u32> = LinkedList::new();1.0.0 · Source
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());🔬This is a nightly-only experimental API. (allocator_api #32838)
Constructs an empty LinkedList<T, A>.
§Examples
#![feature(allocator_api)]
use std::alloc::System;
use std::collections::LinkedList;
let list: LinkedList<u32, _> = LinkedList::new_in(System);1.0.0 · Source
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);1.0.0 · Source
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 #58533)
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 #58533)
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 #58533)
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 #58533)
Provides a cursor with editing operations at the back element.
The cursor is pointing to the “ghost” non-element if the list is empty.
1.0.0 · Source
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());1.0.0 · Source
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);1.0.0 · Source
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);1.12.0 · Source
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);1.0.0 · Source
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));1.0.0 · Source
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));1.0.0 · Source
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));1.0.0 · Source
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));1.0.0 · Source
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);1.0.0 · Source
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);1.0.0 · Source
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());1.0.0 · Source
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));1.0.0 · Source
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 #69210)
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. (linked_list_retain #114135)
Retains only the elements specified by the predicate.
In other words, remove all elements e for which f(&e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.
§Examples
#![feature(linked_list_retain)]
use std::collections::LinkedList;
let mut d = LinkedList::new();
d.push_front(1);
d.push_front(2);
d.push_front(3);
d.retain(|&x| x % 2 == 0);
assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);Because the elements are visited exactly once in the original order, external state may be used to decide which elements to keep.
#![feature(linked_list_retain)]
use std::collections::LinkedList;
let mut d = LinkedList::new();
d.push_front(1);
d.push_front(2);
d.push_front(3);
let keep = [false, true, false];
let mut iter = keep.iter();
d.retain(|_| *iter.next().unwrap());
assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);🔬This is a nightly-only experimental API. (linked_list_retain #114135)
Retains only the elements specified by the predicate.
In other words, remove all elements e for which f(&mut e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.
§Examples
#![feature(linked_list_retain)]
use std::collections::LinkedList;
let mut d = LinkedList::new();
d.push_front(1);
d.push_front(2);
d.push_front(3);
d.retain_mut(|x| if *x % 2 == 0 {
*x += 1;
true
} else {
false
});
assert_eq!(d.pop_front(), Some(3));
assert_eq!(d.pop_front(), None);🔬This is a nightly-only experimental API. (extract_if #43244)
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.
If the returned ExtractIf is not exhausted, e.g. because it is dropped without iterating or the iteration short-circuits, then the remaining elements will be retained. Use extract_if().for_each(drop) if you do not need the returned iterator.
Note that extract_if 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(extract_if)]
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.extract_if(|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]);Overwrites the contents of self with a clone of the contents of source.
This method is preferred over simply assigning source.clone() to self, as it avoids reallocation of the nodes of the linked list. Additionally, if the element type T overrides clone_from(), this will reuse the resources of self’s elements as well.
Returns a copy of the value. Read more
Creates an empty LinkedList<T>.
Extends a collection with the contents of an iterator. Read more
🔬This is a nightly-only experimental API. (extend_one #72631)
Extends a collection with exactly one element.
🔬This is a nightly-only experimental API. (extend_one #72631)
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 #72631)
Extends a collection with exactly one element.
🔬This is a nightly-only experimental API. (extend_one #72631)
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);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
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?
Tests for self and other values to be equal, and is used by ==.
Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
This method returns an ordering between self and other values if one exists. Read more
Tests less than (for self and other) and is used by the < operator. Read more
Tests less than or equal to (for self and other) and is used by the<= operator. Read more
Tests greater than (for self and other) and is used by the >operator. Read more
Tests greater than or equal to (for self and other) and is used by the >= operator. Read more