Struct alloc::collections::linked_list::LinkedList

1.0.0 · source ·
pub struct LinkedList<T, A: Allocator = Global> { /* private fields */ }
Expand description

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

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

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

use std::collections::LinkedList;

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

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

Implementations§

source§

impl<T> LinkedList<T>

const: 1.39.0 · source

pub const fn new() -> Self

创建一个空的 LinkedList

Examples
use std::collections::LinkedList;

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

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());
Run
source§

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

source

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

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

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

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

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

在前元素处提供游标。

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

source

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

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

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

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

source

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

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

在 back 元素上提供游标。

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

source

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

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

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

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

source

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

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

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);
Run
1.12.0 · source

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

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

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

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

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

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

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

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

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

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

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

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

Trait Implementations§

source§

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

source§

fn clone(&self) -> Self

返回值的副本。 Read more
source§

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

source 执行复制分配。 Read more
source§

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

source§

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

使用给定的格式化程序格式化该值。 Read more
source§

impl<T> Default for LinkedList<T>

source§

fn default() -> Self

创建一个空的 LinkedList<T>

source§

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

source§

fn drop(&mut self)

执行此类型的析构函数。 Read more
1.2.0 · source§

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

source§

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

使用迭代器的内容扩展集合。 Read more
source§

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

🔬This is a nightly-only experimental API. (extend_one #72631)
用一个元素扩展一个集合。
source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)
在集合中为给定数量的附加元素保留容量。 Read more
source§

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

source§

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

使用迭代器的内容扩展集合。 Read more
source§

fn extend_one(&mut self, elem: T)

🔬This is a nightly-only experimental API. (extend_one #72631)
用一个元素扩展一个集合。
source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)
在集合中为给定数量的附加元素保留容量。 Read more
1.56.0 · source§

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

source§

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);
Run
source§

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

source§

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

从迭代器创建一个值。 Read more
source§

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

source§

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

将该值输入给定的 HasherRead more
1.3.0 · source§

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

将这种类型的切片送入给定的 Hasher 中。 Read more
source§

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

§

type Item = &'a T

被迭代的元素的类型。
§

type IntoIter = Iter<'a, T>

我们将其变成哪种迭代器?
source§

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

从一个值创建一个迭代器。 Read more
source§

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

§

type Item = &'a mut T

被迭代的元素的类型。
§

type IntoIter = IterMut<'a, T>

我们将其变成哪种迭代器?
source§

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

从一个值创建一个迭代器。 Read more
source§

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

source§

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

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

§

type Item = T

被迭代的元素的类型。
§

type IntoIter = IntoIter<T, A>

我们将其变成哪种迭代器?
source§

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

source§

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

此方法返回 selfother 之间的 OrderingRead more
1.21.0 · source§

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

比较并返回两个值中的最大值。 Read more
1.21.0 · source§

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

比较并返回两个值中的最小值。 Read more
1.50.0 · source§

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

将值限制在某个时间间隔内。 Read more
source§

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

source§

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

此方法测试 selfother 值是否相等,并由 == 使用。
source§

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

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

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

source§

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

如果存在,则此方法返回 selfother 值之间的顺序。 Read more
source§

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

此方法测试的内容少于 (对于 selfother),并且由 < 操作员使用。 Read more
source§

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

此方法测试小于或等于 (对于 selfother),并且由 <= 运算符使用。 Read more
source§

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

此方法测试大于 (对于 selfother),并且由 > 操作员使用。 Read more
source§

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

此方法测试是否大于或等于 (对于 selfother),并且由 >= 运算符使用。 Read more
source§

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

source§

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

source§

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

Auto Trait Implementations§

§

impl<T, A> RefUnwindSafe for LinkedList<T, A>where A: RefUnwindSafe, T: RefUnwindSafe,

§

impl<T, A> Unpin for LinkedList<T, A>where A: Unpin,

§

impl<T, A> UnwindSafe for LinkedList<T, A>where A: UnwindSafe, T: UnwindSafe + RefUnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

获取 selfTypeIdRead more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

从拥有的值中一成不变地借用。 Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

从拥有的值中借用。 Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

返回未更改的参数。

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

调用 U::from(self)

也就是说,这种转换是 From<T> for U 实现选择执行的任何操作。

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

获得所有权后的结果类型。
source§

fn to_owned(&self) -> T

从借用的数据创建拥有的数据,通常是通过克隆。 Read more
source§

fn clone_into(&self, target: &mut T)

使用借来的数据来替换拥有的数据,通常是通过克隆。 Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

发生转换错误时返回的类型。
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

执行转换。
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

发生转换错误时返回的类型。
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

执行转换。