Struct alloc::collections::linked_list::LinkedList

pub struct LinkedList<T, A: Allocator = Global> { /* private fields */ }

具有所属节点的双向链表。

LinkedList 允许在恒定时间内在任一端推送和弹出元素。

可以从数组初始化具有已知项列表的 LinkedList：

use std::collections::LinkedList;

let list = LinkedList::from([1, 2, 3]);

NOTE: 使用 Vec 或 VecDeque 几乎总是更好，因为基于数组的容器通常更快，内存效率更高，并且可以更好地利用 CPU 缓存。

Implementations

impl<T> LinkedList<T>

pub const fn new() -> Self

创建一个空的 LinkedList。

Examples

use std::collections::LinkedList;

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

pub fn append(&mut self, other: &mut Self)

将所有元素从 other 移动到列表的末尾。

这将重用 other 中的所有节点并将它们移到 self 中。 完成此操作后，other 变为空。

此操作应在 O(1) 时间和 O(1) 内存中进行计算。

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

impl<T, A: Allocator> LinkedList<T, A>

pub const fn new_in(alloc: A) -> Self

🔬This is a nightly-only experimental API. (allocator_api #32838)

创建一个空的 LinkedList<T, A>。

Examples

#![feature(allocator_api)]

use std::alloc::System;
use std::collections::LinkedList;

let list: LinkedList<u32, _> = LinkedList::new_in(System);

pub fn iter(&self) -> Iter<'_, T>

提供一个正向迭代器。

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

pub fn iter_mut(&mut self) -> IterMut<'_, T>

提供具有可变引用的正向迭代器。

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

pub fn cursor_front(&self) -> Cursor<'_, T, A>

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

在前元素处提供游标。

如果列表为空，则游标指向 “ghost” 非元素。

pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T, A>

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

在前面的元素上为游标提供编辑操作。

如果列表为空，则游标指向 “ghost” 非元素。

pub fn cursor_back(&self) -> Cursor<'_, T, A>

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

在 back 元素上提供游标。

如果列表为空，则游标指向 “ghost” 非元素。

pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T, A>

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

在 back 元素上为游标提供编辑操作。

如果列表为空，则游标指向 “ghost” 非元素。

pub fn is_empty(&self) -> bool

如果 LinkedList 为空，则返回 true。

此运算应在 O(1) 时间中进行计算。

Examples

use std::collections::LinkedList;

let mut dl = LinkedList::new();
assert!(dl.is_empty());

dl.push_front("foo");
assert!(!dl.is_empty());

pub fn len(&self) -> usize

返回 LinkedList 的长度。

此运算应在 O(1) 时间中进行计算。

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

pub fn clear(&mut self)

从 LinkedList 删除所有元素。

此运算应在 O(n) 时间中计算。

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

pub fn contains(&self, x: &T) -> boolwhere T: PartialEq<T>,

如果 LinkedList 包含等于给定值的元素，则返回 true。

此操作应在 O(n) 时间内线性计算。

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

pub fn front(&self) -> Option<&T>

提供对前元素的引用，如果列表为空，则为 None。

此运算应在 O(1) 时间中进行计算。

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

pub fn front_mut(&mut self) -> Option<&mut T>

提供对前元素的可变引用，如果列表为空，则为 None。

此运算应在 O(1) 时间中进行计算。

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

pub fn back(&self) -> Option<&T>

提供对 back 元素的引用，如果列表为空，则提供 None。

此运算应在 O(1) 时间中进行计算。

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

pub fn back_mut(&mut self) -> Option<&mut T>

提供对 back 元素的可变引用，如果列表为空，则为 None。

此运算应在 O(1) 时间中进行计算。

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

pub fn push_front(&mut self, elt: T)

首先在列表中添加一个元素。

此运算应在 O(1) 时间中进行计算。

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

pub fn pop_front(&mut self) -> Option<T>

删除第一个元素并返回它; 如果列表为空，则返回 None。

此运算应在 O(1) 时间中进行计算。

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

pub fn push_back(&mut self, elt: T)

将元素追加到列表的后面。

此运算应在 O(1) 时间中进行计算。

Examples

use std::collections::LinkedList;

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

pub fn pop_back(&mut self) -> Option<T>

从列表中删除最后一个元素并返回它; 如果它为空，则返回 None。

此运算应在 O(1) 时间中进行计算。

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

pub fn split_off(&mut self, at: usize) -> LinkedList<T, A>where A: Clone,

在给定的索引处将列表分为两部分。 返回给定索引之后的所有内容，包括索引。

此运算应在 O(n) 时间中计算。

Panics

如果为 at > len，就会出现 panics。

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

pub fn remove(&mut self, at: usize) -> T

🔬This is a nightly-only experimental API. (linked_list_remove #69210)

删除给定索引处的元素并返回它。

此运算应在 O(n) 时间中计算。

Panics

如果 >= len 就会出现 panics

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

pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F, A> where F: FnMut(&mut T) -> bool,

🔬This is a nightly-only experimental API. (drain_filter #43244)

创建一个迭代器，该迭代器使用闭包确定是否应删除元素。

如果闭包返回 true，则删除并生成元素。 如果闭包返回 false，则该元素将保留在列表中，并且不会由迭代器产生。

请注意，无论选择保留还是删除 drain_filter，您都可以对过滤器闭包中的每个元素进行可变的。

Examples

将列表分成偶数和几率，重新使用原始列表：

#![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

impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A>

fn clone(&self) -> Self

返回值的副本。

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

从 source 执行复制分配。

impl<T: Debug, A: Allocator> Debug for LinkedList<T, A>

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

使用给定的格式化程序格式化该值。

impl<T> Default for LinkedList<T>

fn default() -> Self

创建一个空的 LinkedList<T>。

impl<T, A: Allocator> Drop for LinkedList<T, A>

fn drop(&mut self)

执行此类型的析构函数。

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

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

使用迭代器的内容扩展集合。

fn extend_one(&mut self, elem: &'a T)

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

用一个元素扩展一个集合。

fn extend_reserve(&mut self, additional: usize)

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

在集合中为给定数量的附加元素保留容量。

impl<T, A: Allocator> Extend<T> for LinkedList<T, A>

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

使用迭代器的内容扩展集合。

fn extend_one(&mut self, elem: T)

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

用一个元素扩展一个集合。

fn extend_reserve(&mut self, additional: usize)

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

在集合中为给定数量的附加元素保留容量。

impl<T, const N: usize> From<[T; N]> for LinkedList<T>

fn from(arr: [T; N]) -> Self

将 [T; N] 转换为 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);

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

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

从迭代器创建一个值。

impl<T: Hash, A: Allocator> Hash for LinkedList<T, A>

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

将该值输入给定的 Hasher。

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

将这种类型的切片送入给定的 Hasher 中。

impl<'a, T, A: Allocator> IntoIterator for &'a LinkedList<T, A>

type Item = &'a T

被迭代的元素的类型。

type IntoIter = Iter<'a, T>

我们将其变成哪种迭代器？

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

从一个值创建一个迭代器。

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

type Item = &'a mut T

被迭代的元素的类型。

type IntoIter = IterMut<'a, T>

我们将其变成哪种迭代器？

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

从一个值创建一个迭代器。

impl<T, A: Allocator> IntoIterator for LinkedList<T, A>

fn into_iter(self) -> IntoIter<T, A>

将列表消耗到迭代器中，该迭代器按值产生元素。

type Item = T

被迭代的元素的类型。

type IntoIter = IntoIter<T, A>

我们将其变成哪种迭代器？

impl<T: Ord, A: Allocator> Ord for LinkedList<T, A>

fn cmp(&self, other: &Self) -> Ordering

此方法返回 self 和 other 之间的 Ordering。

fn max(self, other: Self) -> Selfwhere Self: Sized,

比较并返回两个值中的最大值。

fn min(self, other: Self) -> Selfwhere Self: Sized,

比较并返回两个值中的最小值。

fn clamp(self, min: Self, max: Self) -> Selfwhere Self: Sized + PartialOrd<Self>,

将值限制在某个时间间隔内。

impl<T: PartialEq, A: Allocator> PartialEq<LinkedList<T, A>> for LinkedList<T, A>

fn eq(&self, other: &Self) -> bool

此方法测试 self 和 other 值是否相等，并由 == 使用。

fn ne(&self, other: &Self) -> bool

此方法测试 !=。 默认实现几乎总是足够的，并且不应在没有充分理由的情况下被覆盖。

impl<T: PartialOrd, A: Allocator> PartialOrd<LinkedList<T, A>> for LinkedList<T, A>

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

如果存在，则此方法返回 self 和 other 值之间的顺序。

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

此方法测试的内容少于 (对于 self 和 other)，并且由 < 操作员使用。

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

此方法测试小于或等于 (对于 self 和 other)，并且由 <= 运算符使用。

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

此方法测试大于 (对于 self 和 other)，并且由 > 操作员使用。

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

此方法测试是否大于或等于 (对于 self 和 other)，并且由 >= 运算符使用。

impl<T: Eq, A: Allocator> Eq for LinkedList<T, A>

impl<T: Send, A: Allocator + Send> Send for LinkedList<T, A>

impl<T: Sync, A: Allocator + Sync> Sync for LinkedList<T, A>