手搓一个简单的链表

发表于 更新于 从0开始的rust之旅

已经学习rust一周了，是时候尝试一下链表了

按照TDD的规范，先写第一个测试：

//lib.rs
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_list_new(){
        let list : List <i32> = List::new();
        assert!(list.isempty())
    }
}

第一个细节是 use super::*，rust项目在一个crate里的组织是以mod为单元的，也就是说虽然tests模块写在了lib.rs，它和直接写在lib.rs里的函数仍然是分离的。use super::*表示把父模块的全部方法引入进当前模块

接下来定义List结构体，完成new和isempty方法

//lib.rs
pub struct List <T>{
    head : Option<Box<Node<T>>>,
}

impl<T> List<T>{
    pub fn new() -> List<T>{
        List{head : None,}
    }
    pub fn isempty(&self) -> bool{
        self.head.is_none()
    }
}

Option<Box<Node<T>>>，好冗长的东西。head应该是一个指向链表首地址的指针，而链表的本体要放在堆上。Box用来封装到堆上，类型是，元素为T类型的节点

type Link <T> = Option<Box<Node<T> >>;

所以补充这一行简化代码

另一个细节是impl<T> List<T>这里有两个< T>，第一个是声明这里要用到一个泛型模板T，第二个则是跟着每个List出现的类型说明

该写下一个测试了，关于pop和push方法，仅在头部进出元素：

/*other tests*/
    #[test]
    fn test_list_push_and_pop(){
        let mut list : List <i32> = List::new();
        list.push(3);
        list.push(336699);
        assert_eq!(list.pop(),Some(336699));
        assert_eq!(list.pop(),Some(3));
    }

如下：

/*existing code*/
    pub fn push(&mut self,val : T) {
        let new_node = Node{val : val,next : self.head.take()};
        self.head = Some(Box::new(new_node));
    }
    
    pub fn pop(&mut self) -> Option<T>{
        self.head.take().map(|node| {
            self.head = node.next;
            node.val
        })
    }

Option类型的take方法，可以把其中的值取出来。map方法，对取出来的值进行一个闭包形式的操作。这里take出来一个作为参数node，给self重新赋值

以上逻辑看着很理所当然，实际上却没有那么简单。试想如果写成:

pub fn pop(&mut self) -> Option<T> {
    if let Some(node) = self.head {
        self.head = node.next;
        Some(node.val)
    } else {
        None
    }
}

编译器就会提醒self是不可移动的，因为let Some(node) = self.head涉及所有权的转移，而take方法在把值转移出去之后会补充一个None以避免安全问题。

那么，下一个测试要实现peek函数功能，返回头节点的引用：

#[test]
fn test_peek() {
    let mut list = List::new();
    assert_eq!(list.peek(), None);

    list.push(42);
    assert_eq!(list.peek(), Some(&42));

    list.push(100);
    assert_eq!(list.peek(), Some(&100)); 
    assert_eq!(list.pop(), Some(100));
    assert_eq!(list.peek(), Some(&42));
}
pub fn peek(&mut self) -> Option<&T>{
    self.head.as_ref().map(|node| {
        &node.val
    })
}

as_ref()方法是必须的，因为函数返回了一个内部的引用，这可太危险了，参数出了函数就没了，而引用（指针）还在。

接下来是迭代器，rust中分为三种，移交所有权的，借用型的和可变借用型的。

首先实现转移所有权的into版本，还是先写测试：

#[test]
fn test_into_iter(){
    let mut list = List::new();
    list.push(3);
    list.push(2);
    list.push(1);
    let mut iter = list.into_iter();
    assert_eq!(iter.next(), Some(1));
    assert_eq!(iter.next(), Some(2));
    assert_eq!(iter.next(), Some(3));
    assert_eq!(iter.next(), None);
}

取出来的是数值，接下来要实现的有：一个迭代器结构体IntoIter，迭代器特征，以及List结构体的构造迭代器的方法

/*……*/
pub struct IntoIter<T>(List<T>);
/*……*/
    pub fn into_iter(self) -> IntoIter<T>{
        IntoIter(self)
    }
/*……*/
impl<T> Iterator for IntoIter<T>{
    type Item = T;
    fn next(&mut self) -> Option<Self::Item>{
        self.0.pop()
    }
}

IntoIter是一个元组结构体，类型是一个List，也就是一个指针

Into的版本在迭代时也把链表清空了，而下一个Iter，返回一个不可变引用，就没有这个问题了，为了展现这一特点，测试写成这样：

#[test]
fn test_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!(iter.next(), None);
    
    iter = list.iter();
    assert_eq!(iter.next(), Some(&3));
}

要实现的东西不变，一个结构体定义，一个特征，一个方法

pub struct Iter<'a, T>{
    next: Option<&'a Node<T>>,
}

/*List*/
    pub fn iter(&self) -> Iter<'_, T>{
        Iter{
            next: self.head.as_ref().map(|node| &**node)
        }
    }
    
/*other code*/    

impl<'a,T> Iterator for Iter<'a, T>{
    type Item =&'a T;
    fn next(&mut self) -> Option<Self::Item>{
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.val
        })
    }
}

因为涉及到了引用，所以编译器撂挑子了，把生命周期的难题还了回来，不过在此之前，&**node实在是丑陋，其表示对node做两次解引用再返回其引用，可以用as_deref简化：

pub fn iter(&self) -> Iter<'_, T>{
    Iter{
        next: self.head.as_deref()
    }
}

fn next(&mut self) -> Option<Self::Item>{
    self.next.map(|node| {
        self.next = node.next.as_deref();
        &node.val
    })
}

简洁多了

引用的生命周期要保证引用活得不能比其本体久，在iter函数中就是返回的迭代器活得不长于self，也就是链表头。
在迭代器特征的实现中，要保证self至少和Item活得一样久

接下来是更复杂一点的可变借用IterMut，测试：

#[test]
fn test_iter_mut() {
    let mut list = List::new();
    list.push(1);
    list.push(2);
    list.push(3);

    for val in list.iter_mut() {
        *val *= 10;
    }

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&30));
    assert_eq!(iter.next(), Some(&20));
    assert_eq!(iter.next(), Some(&10));
}
pub struct IterMut<'a, T>{
    next: Option<&'a mut Node<T>>,
}
//……
    pub fn iter_mut(&mut self) -> IterMut<'_, T>{
        IterMut{
            next: self.head.as_deref_mut()
        }
    }
//……
impl<'a, T> Iterator for IterMut<'a, T>{
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item>{
        self.next.take().map(|node| {
            self.next = node.next.as_deref_mut();
            &mut node.val
        })
    }
}

可变引用的难点在于同时只能有一个，是不可copy的，所以在next函数中要使用take()获取值

至此，一个很基本的链表就算是完成了，难怪不建议新手尝试😵‍💫

# rust# 链表