如何理解 rust 的单向链表

为了实现遍历功能，将该链表（集合类型）转化成可迭代功能

实现一个迭代器，可以通过实现3个trait：1.对象所有权 ，2.对象可变引用 ，3.对象不可变引用Iter

毫无疑问，我们实际上想要取的是第三个不可变的引用，因为，我们不能说遍历完链表，链表就没了，而获取所有权的迭代器会把链表消耗掉的，因为要把链表所有权转给迭代器，然后迭代器进行消耗，这就没意义了。

如果我们想要通过迭代并实现元素的更新，那就必须实现对象可变的引用，这种trait对吧，原因很简单，你取到了对该链表的引用，然后当你想要修改链表的时候（不管是插入数据，删除数据，还是更新数据）都是要做mut操作的。

通过上面的分析，我们知道，最终目的是实现Iter和，但是通过学习rust我们知道，最简单的是获取所有权，获取所有权是不需要分析生命周期的，而rust的生命周期又是仅次于难度的坑（我个人理解），因此简单入手，逐渐增加难度才是作为一个新能做的。

part1.实现获取所有权类型的迭代器：.

// 首先定义trait，只要实现这个trait就可以进行next操作进行下一个元素的迭代，因此要有一个next方法
// 这里还用了关联类型，实际上使用泛型也可以，不过泛型有他的局限性，并且每个实现它的对象都要重写泛型的定义（具体原因见rust圣经）
pub trait Iterator {type Item; // 这里的 Item 是关联类型，用于在trait中指代某个类型fn next(&mut self) -> Option<Self::Item>; // 由于next最后一个为None，因此元素用Option包裹一层
}// 创建一个元祖结构体IntoIter (List)
pub struct IntoIter<T> (List<T>);
// 给IntoIter实现Iterator 的trait，也就是重载next方法
impl<T> Iterator for IntoIter<T> {type Item = T;fn next(&mut self) -> Option<Self::Item> {// 从元组中取出第一个元素就是List了self.0.pop()}
}impl<T> List<T> {// type: List ---> (List>)pub fn into_iter(self) -> IntoIter<T> {IntoIter(self)}
}// 测试部分（注意，上面只写了迭代器部分的代码，需要将上面的代码放到原来的代码中方可）
#[test]fn into_iter() {let mut list = List::new();list.push(1);list.push(2);list.push(3);let mut iter = list.into_iter();assert_eq!(iter.next(), Some(3));assert_eq!(iter.next(), Some(2));assert_eq!(iter.next(), Some(1));// assert_eq!(iter.next(), None);}

part2， 实现不可变的引用迭代器： Iter

要实现这个不可变的引用，我们不能想part1一样，获取链表List，然后用List的pop方法了，那我们就必须要创建一个能存储一个节点指针信息的对象，获取该节点，并且通过该节点的next属性，查到下一个节点的指针对象，之所以是指针对象，是因为我们是要引用（&）节点，才能不影响对象的移动。

这里会有一个新的api：: 可以将的数据取出来，然后返回一个里面对象的引用

// 通过上面的分析，我们知道这个Iter对象不能和之前的IntoIter一样，它应该是一个有属性的结构体，因为他要存放节点的指针信息，用于展示
// pub struct Iter {
//     info: Option<&Node>,
// }// 这么写之后，编译会爆：Option<&Node>中的type `T` may not live long enough，也就是我们最早分析的，这里要涉及到生命周期的指定
// 编译器报错也会提示，是不是要考虑给&Node加一个'a的生命周期参数
// 原因就是struct中的元素如果是引用类型的，那就必须要求这个引用的生命长于这个struct，否则这个指针可能会悬垂
// pub struct Iter<'a, T> {
//     info: Option<&'a Node>,
// }// 接下来就是要给他实现之前定义的iterator的trait
// impl<'a, T>Iterator for Iter<'a, T> {
//     type Item = &T;
//     
//     // 这里的self是Node节点的引用，因此是&self，而又因为这个next要随着取出下一个换掉，因此还要是mut类型
//     fn next(&mut self) -> Option {
//         todo!()
//     }
// }// 这里Item要指定是T类型的指针，因为定义好的next返回的是一个Option<&Node>
// 但是当这么修改后：type Item = &T;会报错缺少生命参数，因此最后改成：type Item = &'a T;
// pub struct Iter<'a, T> {
//     info: Option<&'a Node>,
// }
// 
// impl<'a, T>Iterator for Iter<'a, T> {
//     type Item = &'a T;
// 
//     // 这里的self要知道是Node节点的引用，因此是&self，而又因为这个next要随着取出下一个换掉，因此还要是mut类型
//     fn next(&mut self) -> Option {
//         self.info.map(|node|{
//             // 将临时变量node中的数据返回，展示出去
//             &node.value
//         })
//     }
// }
// 上面在定义next时候，直接把node的value返回回去之后，是不是发现Iter的info没有指向下一个元素，这样就没办法再次next了
// 因此在返回前还需要加一行内容，将self.info指向下一个node的指针：self.info = node.next.as_deref();
// 最终代码：
pub struct Iter<'a, T> {info: Option<&'a Node<T>>,
}impl<'a, T>Iterator for Iter<'a, T> {type Item = &'a T;// 这里的self要知道是Node节点的引用，因此是&self，而又因为这个next要随着取出下一个换掉，因此还要是mut类型fn next(&mut self) -> Option<Self::Item> {self.info.map(|node|{// 将self.info换成下一个节点数据，node.next是一个Option类型，而Option.as_deref()可以获取定义关联类型的值的引用// 相当于多去掉一层self.info = node.next.as_deref();// 将临时变量node中的数据返回，展示出去&node.value})}
}
// 接下来再给List实现iter方法，将List转成Iter// 测试部分#[test]fn iter() {let mut list = List::new();list.push(1);list.push(2);list.push(3);let mut iter = list.iter();assert_eq!(iter.next(), Some(&3));assert_eq!(iter.next(), Some(&2));assert_eq!(iter.next(), Some(&1));assert_eq!(list.pop(), Some(3)); // 因为是引用迭代，因此并不影响源List可以pop()数据assert_eq!(list.pop(), Some(2));assert_eq!(list.pop(), Some(1));}

part3: 可变引用:

分析和part2一样，只不过这个变成了mut类型，因此，只需要按部就班的和part2一样，现将创建出来，多加一个mut即可。然后按照编译器的要求添加相应的生命周期参数

pub struct MutIter<'a, T> {
// 因为这里查到的Node不仅要用来显示，而且还可以外部修改，因此把原来的Option<&'a Node> --> Option<&'a mut Node>info: Option<&'a mut Node<T>>,
}impl<'a, T> Iterator for MutIter<'a, T> {type Item = &'a T; // 最后这里也要改成mut的： type Item = &'a mut T;fn next(&mut self) -> Option<Self::Item> {// 实际这么写是会报错的，因为这里的self.info中的&mut T是不可Copy的，因此这里就会move，// cannot move out of `self.info` which is behind a mutable reference，因为可变的引用self压根不拥有info// 那肯定就更不可能move info了，因此这里使用take()，将数据临时取出再放进去一个空self.info.map(|node|{self.info = node.next.as_deref_mut();&node.value // 当然这里最后也必须是mut的，不然返回的数据不可修改: &mut node.value })}
}impl<T> List<T> {pub fn iter_mut(&mut self) -> IterMut<T> {// 很清楚，这个和as_deref()方法返回的值一样，不过这个值是mut的IterMut{ info: self.head.as_deref_mut() }}
}

注： 为什么可变的引用(&mut T)不可以Copy，因为一个引用说白了就是一个指针，拷贝一个指针就是多一个指向某值的拷贝，而如果这个值是可变的，那很可能它在某次变化后它的地址就变了（比如vec元素增加的时候，超过cap值进行扩容，此时它会选一块新的内存地址，将原来的数据拷贝过去），这样就会产生悬垂引用，即一个指向无效内存的指针

最终part3完整的样子：

pub struct IterMut<'a, T> {info: Option<&'a mut Node<T>>,
}impl<'a, T> Iterator for IterMut<'a, T> {type Item = &'a mut T;fn next(&mut self) -> Option<Self::Item> {// 由于self.info中的&mut T是没有满足copy的trait，因此这里就会move，但是我们又不能move这个值// 这里使用self.info.take()将self.info临时拿出来，然后放进去一个None，然后在对拿出来的数据做map操作// 不用担心self.info变成None会指向空，因为里面会重新把下一个元素取出来放到这个self.info中self.info.take().map(|node| {self.info = node.next.as_deref_mut();&mut node.value})}
}impl<T> List<T> {pub fn iter_mut(&mut self) -> IterMut<T> {IterMut{ info: self.head.as_deref_mut() }}
}// 测试代码
#[test]
fn iter_mut() {let mut list = List::new();list.push(1); list.push(2); list.push(3);let mut iter = list.iter_mut();assert_eq!(iter.next(), Some(&mut 3));assert_eq!(iter.next(), Some(&mut 2));assert_eq!(iter.next(), Some(&mut 1));
}

最终的代码

type Next<T> = Option<Box<Node<T>>>;#[derive(Debug)]
struct List<T> {size: u32,head: Next<T>,
}#[derive(Debug, PartialEq)]
struct Node<T> {value: T,next: Next<T>,
}impl<T> List<T> {fn new() -> Self {List {size: 0,// 给头添加一个空元素，空元素里面是没值的，这样就有一个头了head: None,}}fn push(&mut self, value: T) {// 创建node对象，需要了解的是，当插入的时候，需要将这个节点的下一个元素指向原来List的头，这样才是在头部插入// Option.take()的方法描述的很清楚，取出Option中的Some(?)，然后把原来的对象设置为Nonelet new_node = Box::new(Node { value, next: self.head.take() });self.head = Some(new_node);// 此时是添加操作，因此元素长度+1self.size += 1;}fn pop(&mut self) -> Option<T> {if self.size == 0 {panic!("no value to pop.")}//  由于self.size == 0的情况已经考虑，因此就不需要match或if let的模式匹配 ,直接letlet node = self.head.take().unwrap();self.head = node.next;self.size -= 1;Some(node.value)}fn peek(&self) -> Option<&T> {if self.size == 0 {return None;}// map可以从一个Option中取到里面的数据，然后操作后再返回给Option进行包装// 就是他描述的：Maps an Option to Option by applying a function to a contained value.self.head.as_ref().map(|node| {&node.value})}fn peek_by_unwrap(&self) -> Option<&T> {if self.size == 0 {return None;}// 这种方法比较直接，先用unwrap打开Option,获取值value后，再用Some包起来，一样return Some(&self.head.as_ref().unwrap().value);}// 可取出并改值fn peek_mut(&mut self) -> Option<&mut T> {if self.size == 0 {return None;}self.head.as_mut().map(|node| {&mut node.value})}fn peek_and_update(&mut self, new_value: T) {if self.size == 0 {return ();}self.head.as_mut().map(|node| {node.value = new_value;});}// 由于实现了iter类型，即不可变引用，因此满足通过show链表数据，因为T类型并没有bind debug trait，因此没办法在里面直接打印// 只能直接把迭代器返回出去得了，然后在外面遍历打印fn show(&self) -> Iter<T> {self.iter()}
}impl<T> Drop for List<T> {fn drop(&mut self) {let mut cur_node = self.head.take();while let Some(mut temp_node) = cur_node {println!("---> dropping node --->");cur_node = temp_node.next.take();// temp_node 在这里超出作用域并被 drop,// 由于它的 `next` 字段拥有的 `Node` 被设置为 None,// 因此这里并不会有无边界的递归发生}}
}// 集合类型可以通过 Iterator 特征进行迭代
// 准备一个trait(特征)，包含一个next方法，调用的时候就会取出下一个元素
pub trait Iterator {type Item;// 这里的 Item 是关联类型，用于在trait中指代某个类型fn next(&mut self) -> Option<Self::Item>;
}// 实现一个迭代器，需要实现3个trait，对象所有权IntoIter ，对象可变引用IterMut ，对象不可变引用Iter
// 创建一个元祖结构体IntoIter (List)
pub struct IntoIter<T> (List<T>);impl<T> Iterator for IntoIter<T> {type Item = T;fn next(&mut self) -> Option<Self::Item> {// 从元组中取出第一个元素就是List了self.0.pop()}
}impl<T> List<T> {// type: List ---> (List>)pub fn into_iter(self) -> IntoIter<T> {IntoIter(self)}
}pub struct Iter<'a, T> {info: Option<&'a Node<T>>,
}impl<'a, T>Iterator for Iter<'a, T> {type Item = &'a T;// 这里的self要知道是Node节点的引用，因此是&self，而又因为这个next要随着取出下一个换掉，因此还要是mut类型fn next(&mut self) -> Option<Self::Item> {self.info.map(|node|{// 将self.info换成下一个节点数据self.info = node.next.as_deref();// 将临时变量node中的数据返回，展示出去&node.value})}
}
impl<T> List<T> {pub fn iter(&self) -> Iter<T> {Iter{ info: self.head.as_deref() }}
}pub struct IterMut<'a, T> {info: Option<&'a mut Node<T>>,
}impl<'a, T> Iterator for IterMut<'a, T> {type Item = &'a mut T;fn next(&mut self) -> Option<Self::Item> {// 由于self.info中的&mut T是没有满足copy的trait，因此这里就会move，但是我们又不能move这个值// 这里使用self.info.take()将self.info临时拿出来，然后放进去一个None，然后在对拿出来的数据做map操作// 不用担心self.info变成None会指向空，因为里面会重新把下一个元素取出来放到这个self.info中self.info.take().map(|node| {self.info = node.next.as_deref_mut();&mut node.value})}
}impl<T> List<T> {pub fn iter_mut(&mut self) -> IterMut<T> {IterMut{ info: self.head.as_deref_mut() }}
}#[cfg(test)]
mod test {use super::*;#[test]fn basics2() {let mut list = List::new();// Populate listlist.push(1);list.push(2);list.push(3);// Check normal removalassert_eq!(list.pop(), Some(3));assert_eq!(list.pop(), Some(2));}#[test]fn peek2() {let mut list = List::new();assert_eq!(list.peek(), None);assert_eq!(list.peek_mut(), None);list.push(1);list.push(2);list.push(3);assert_eq!(list.peek(), Some(&3));assert_eq!(list.peek_mut(), Some(&mut 3));list.peek_and_update(4);assert_eq!(list.peek(), Some(&4));list.peek_mut().map(|value| {*value = 42});assert_eq!(list.peek(), Some(&42));assert_eq!(list.pop(), Some(42));}#[test]fn into_iter() {let mut list = List::new();list.push(1);list.push(2);list.push(3);let mut iter = list.into_iter();assert_eq!(iter.next(), Some(3));assert_eq!(iter.next(), Some(2));assert_eq!(iter.next(), Some(1));// assert_eq!(iter.next(), None);}#[test]fn iter() {let mut list = List::new();list.push(1);list.push(2);list.push(3);let mut iter = list.iter();assert_eq!(iter.next(), Some(&3));assert_eq!(iter.next(), Some(&2));assert_eq!(iter.next(), Some(&1));assert_eq!(list.pop(), Some(3));assert_eq!(list.pop(), Some(2));assert_eq!(list.pop(), Some(1));}#[test]fn iter_mut() {let mut list = List::new();list.push(1); list.push(2); list.push(3);let mut iter = list.iter_mut();assert_eq!(iter.next(), Some(&mut 3));assert_eq!(iter.next(), Some(&mut 2));assert_eq!(iter.next(), Some(&mut 1));}#[test]fn show_list() {let mut list = List::new();list.push(1);list.push(2);list.push(3);let mut iter = list.show();// let mut size = list.size;// while size > 0 {//     let node = iter.next();//     size -= 1;//     println!("node: {:?}", node);// }// 直接使用while let进行循环匹配更加优雅while let Some(node) = iter.next() {println!("node value: {:?}", node);}}
}