013 通過連結清單學習Rust之實作連結清單的通用函數

介紹

視訊位址：https://www.bilibili.com/video/av78062009/

相關源碼：https://github.com/anonymousGiga/Rust-link-list

詳細内容

本節我們就在上一節定義的連結清單的基礎上來實作連結清單的通用函數。

因為本章的連結清單更多的操作連結清單的頭尾和尾，是以我們在通用函數中不提供push和pop，而是提供append和tail函數。

append

append函數類似于之前我們實作的push，但是因為現在我們使用的Rc而不是Box，是以代碼上略有差别，如下：

pub fn append(&mut self, elem: T) -> List<T> {
    List { head: Some(Rc::new(Node {
      elem: elem,
      next: self.head.clone(),
    }))}  
  }      

tail

tail函數主要傳回最後放傳入連結表的元素，實作代碼如下：

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().and_then(|node| {
      node.next.clone()
    })}
  }      

head

head函數類似于我們之前的peek函數，代碼如下：

pub fn head(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
  }      

上述函數的測試函數

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

    let list = list.append(1).append(2).append(3);
    assert_eq!(list.head(), Some(&3));

    let list = list.tail();
    assert_eq!(list.head(), Some(&2));

    let list = list.tail();
    assert_eq!(list.head(), Some(&1));

    let list = list.tail();
    assert_eq!(list.head(), None);
  }      

iter

下面我們來實作疊代器，代碼如下：

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

impl<T> List<T> {
  pub fn iter(&self) -> Iter<T> {
    Iter { next: self.head.as_deref() }
  }
}

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_deref();
      &node.elem
    })
  }
}      

疊代器的測試代碼

#[test]
  fn iter() {
    let list = List::new().append(1).append(2).append(3);

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), Some(&1));
  }      

完整代碼

use std::rc::Rc;

pub struct List<T> {
  head: Link<T>,
}

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

struct Node<T> {
  elem: T,
  next: Link<T>,
}

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None }
  }

  pub fn append(&mut self, elem: T) -> List<T> {
    List { head: Some(Rc::new(Node {
      elem: elem,
      next: self.head.clone(),
    }))}  
  }

  pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().and_then(|node| {
      node.next.clone()
    })}
  }

  pub fn head(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
  }
}

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

impl<T> List<T> {
  pub fn iter(&self) -> Iter<T> {
    Iter { next: self.head.as_deref() }
  }
}

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_deref();
      &node.elem
    })
  }
}

#[cfg(test)]
mod test {
  use super::List;

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

    let list = list.append(1).append(2).append(3);
    assert_eq!(list.head(), Some(&3));

    let list = list.tail();
    assert_eq!(list.head(), Some(&2));

    let list = list.tail();
    assert_eq!(list.head(), Some(&1));

    let list = list.tail();
    assert_eq!(list.head(), None);
  }

  #[test]
  fn iter() {
    let list = List::new().append(1).append(2).append(3);

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), Some(&1));
  }
}