1. 链表简介
存储数组的空间是连续的。然而当需要的空间比较大时，空闲的内存空间并非都是连续的。因此引入链表这种相较于数组更灵活的数据结构，链表是一种线性数据结构。链表的每个节点对象由引用(指针)和值组成，每个节点散落分布在内存空间中。节点间通过引用连接，上一个节点通过将引用指向下一个节点来访问节点内存地址。起始节点称为头节点，结束节点称为尾节点。因链表节点除存储值外还存储引用，因此在相同数据量下，链表需要的空间比数组更多。
链表结构体说明
链表节点由值和指针两部分组成，因此在定义节点对象时，除声明值外，还要声明一个引用计数器。在Rust中使用智能指针Rc来定义链表引用，Rc即引用计数(reference counting)。
use std::rc::Rc;
use std::cell::RefCell;
/*链表结构体*/
struct ListNode{
value:i32,
next:Option<Rc<RefCell<ListNode>>>
}2. 链表相关操作
2.1 初始化链表
- 初始化各个节点
- 建立节点间的引用关系，以上述结构体为例，使用next建立引用关系
fn inite_link_list(){
let n0 = Rc::new(RefCell::new(LisstNode{value:0,next:None}));
let n1 = Rc::new(RefCell::new(LisstNode{value:1,next:None}));
let n2 = Rc::new(RefCell::new(LisstNode{value:2,next:None}));
n0.borrow_mut().next = Some(n1.clone());
n1.borrow_mut().next = Some(n2.clone());
}
//我们通常将头节点当作链表的代称，比如以上代码中的链表可记作链表 n0 。2.2 插入节点
链表中插入节点，需要将插入位置前一个节点的引用指向该节点，然后将该节点的引用指向插入位置的下一个节点，一下代码实现在头节点后插入节点。
//*参数说明*
//head:链表的头节点
//node:需插入节点
fn insert_node<T>(head:&Rc<RefCell<ListNode<T>>, node:Rc<RefCell<ListNode<T>>){
let n1 = head.borrow_mut().next.take() ;//取得原本链表头节点后面的节点，即第二节点
node.borrow_mut().next = n1; //将插入节点的指针指向原本第二节点
head.borrow_mut().next = SOme(node); //将头节点指针指向插入节点
}2.3 删除节点
删除链表节点相较于插入操作更简单，无需全部解除头尾节点的引用。因为链表节点间指针引用的单向性，只需要取消删除节点上一个节点对其的引用，那么就无法在内存中访问到该节点了，我们就认为这个节点从链表中删除了。
//*参数说明*
//prev_node：删除节点的前一节点，在这里我们删除头节点后的节点
fn delete_node<T>(prev_node:&Rc<RefCell<ListNode<T>>>){
if prev_node.borrow().next.is_one(){
return ; //如果只有头节点，返回空
}
let next_node = prev_node.borrow_mut().next.take(); //获得要删除的节点
if let Some(node) = next_node {
let n1 = node.borrow_mut().next.take(); //获得要删除节点后面的节点
prev_node.borrow_mut().next = n1; //将头节点的指针修改指向至删除节点后面的节点
}
}2.4 访问节点
不同于数组访问可以在O(1)时间内访问任意元素，链表访问元素则相对复杂。访问链表中的元素需要从头节点出发，遍历每个节点，需要执行n-1次，所以时间复杂度为O(n).
//*参数说明*
//head:动态参数，起始为头节点
//index：索引,控制访问范围，这里是访问所有的元素
fn access_node<T>(head:&Rc<RefCell<ListNode<T>>>,index:i32) -> Rc<RefCell<T>>{
if index <= 0{
return head
}
if let Some(node) = &head.borrow_mut().next{
return acess_node(node.clone(),index-1) //从头节点出发，一直访问下一个节点
}
return head
}2.5 查找节点
查找链表节点是一种线性查找，时间复杂度为O(n)。下面实现查找target节点，返回其索引的方法。
//*参数说明*
//head:动态参数，起始为头节点
//target:目标链表元素
//index：索引,tagart元素对应索引，初始值应为0
fn find_node<T PartialEq>(head:&Rc<RefCell<ListNode<T>>>,target:T,index:i32) -> i32{
if head.borrow().val == target{
return index //当前节点值等于target时，返回此时的索引
}
if let Some(node) = &head.borrow_mut().next{
return find_node(node.clone(),target,index+1) //从头节点向后依次访问，并传递动态head 和 index
}
return -1;
}3. 链表VS数组
对比链表和数组从空间和时间上出发。空间上对比二者的存储方式、效率，时间上对比它们的操作方法的时间复杂度。具体如下图所示。 `
| 链表(link_list) | 数组(Array) | |
|---|---|---|
| 存储方式 | 分散存储 | 连续存储 |
| 扩容 | 长度不可表 | 可扩展 |
| 内存效率 | 占用空间小，但分配较大时会造成浪费 | 需要存储指针引用,占用空间大 |
| 访问元素 | O(1) | O(n) |
| 添加元素 | O(n) | O(1) |
| 删除元素 | O(n) | O(1) |
`
4. 链表的类型及应用
4.1 常见的链表类型
单向链表：最普遍的链表类型，方向单一，由头节点开始，尾节点结束，尾节点指向空None。
环形链表：头节点和尾节点相连接形成闭环的链表，头尾的概念也就消失了，在环形链表中任一节点都可以作为头节点。
双向链表：每一个对象节点都存储两个方向的指针，头既是尾，尾既是头。存储空间更多但也更为灵活。
4.2 各类链表的应用
单向链表:
- 栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
- 哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
- 图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。
双向链表常用于需要快速查找前一个和后一个元素的场景。
- 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
- 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
- LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。
- 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
- 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。