3.15.5 LinkedList（链表）

Rust 中的 LinkedList（链表）是一种线性数据结构，它由一系列相互连接的节点组成。每个节点都包含一个元素和指向前一个节点和后一个节点的指针。这是有关 Rust LinkedList 的一些详细信息：

1. 创建 LinkedList：

要创建一个新的空 LinkedList，可以使用 LinkedList::new() 方法。需要导入 std::collections::LinkedList 模块以使用 LinkedList。

#![allow(unused)]
fn main() {
use std::collections::LinkedList;

let mut list = LinkedList::new();
}

2. 添加元素：

可以使用 push_front() 和 push_back() 方法将元素添加到链表的开头和结尾。

#![allow(unused)]
fn main() {
list.push_front(1);
list.push_back(2);
}

3. 访问元素：

可以使用 front() 和 back() 方法分别访问链表的第一个和最后一个元素。这些方法返回一个 Option<&T> 类型，如果链表不为空，则返回 Some(&element)，否则返回 None。

#![allow(unused)]
fn main() {
let first_element = list.front(); // 返回 Option<&T>
let last_element = list.back(); // 返回 Option<&T>
}

还可以使用 front_mut() 和 back_mut() 方法获取可变引用。

4. 删除元素：

可以使用 pop_front() 和 pop_back() 方法分别删除并返回链表的第一个和最后一个元素。这些方法返回一个 Option<T> 类型，如果链表不为空且成功删除元素，则返回 Some(element)，否则返回 None。

#![allow(unused)]
fn main() {
list.pop_front(); // 删除并返回第一个元素
list.pop_back(); // 删除并返回最后一个元素
}

5. 遍历元素：

可以使用 iter() 方法遍历链表中的所有元素。iter_mut() 方法可用于遍历可变引用。

#![allow(unused)]
fn main() {
for element in list.iter() {
    println!("{}", element);
}
}

6. 链表长度：

可以使用 len() 方法获取链表中的元素数量。还可以使用 is_empty() 方法检查链表是否为空。

7. 清空链表：

可以使用 clear() 方法删除链表中的所有元素。

#![allow(unused)]
fn main() {
list.clear(); // 清空链表
}

8. 分割链表：

可以使用 split_off() 方法在指定索引处分割链表。此操作会将链表分成两个链表，前一个链表包含指定索引之前的元素，后一个链表包含指定索引及之后的元素。

#![allow(unused)]
fn main() {
let mut list1 = LinkedList::new();
list1.push_back(1);
list1.push_back(2);
list1.push_back(3);

let list2 = list1.split_off(1);
}

这样，list1 将包含元素 1，而 list2 将包含元素 2 和 3。

总之，Rust 中的 LinkedList 提供了一种基于节点的线性数据结构，它适用于需要快速插入和删除操作的场景。然而，对于许多其他用途，如随机访问和查找操作，链表通常比数组或向量（Vector）等基于连续内存的数据结构性能差。这是因为链表的元素在内存中是分散存储的，这会导致较差的缓存局部性（cache locality）。而连续内存数据结构在许多情况下可以更有效地利用 CPU 缓存，从而提高性能。

当考虑使用链表时，务必评估其适用性，并与其他数据结构（如 Vector）进行比较。在某些情况下，链表可能是一个很好的选择，特别是当插入和删除操作的性能比访问和查找操作更重要时。然而，在许多场景中，使用基于连续内存的数据结构会带来更好的性能和更简单的代码。