023 通过链表学Rust之非安全方式实现链表1

介绍

视频地址：https://www.bilibili.com/video/av78062009/
相关源码：https://github.com/anonymousGiga/Rust-link-list

链表定义

我们重新定义链表如下：

pub struct List<T> {
  head: Link<T>,
  tail: *mut Node<T>,
}

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

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

new

pub fn new() -> Self {
    List { head: None, tail: ptr::null_mut() }
  }

push

下面我们来实现push，代码如下：

pub fn push(&mut self, elem: T)  {
    let mut new_tail = Box::new(Node {
      elem: elem,
      next: None,
    });

    let raw_tail: *mut _ = &mut *new_tail;

    if !self.tail.is_null() {
      unsafe {//非安全代码
        (*self.tail).next = Some(new_tail);
      }
    } else {
      self.head = Some(new_tail);
    }
    
    self.tail = raw_tail;
  }

pop

下面我们来实现pop，实现代码如下：

pub fn pop(&mut self) -> Option<T> {
    self.head.take().map(|head| {
      let head = *head;
      self.head = head.next;

      if self.head.is_none() {
        self.tail = ptr::null_mut();
      }
      head.elem
    })
  }

测试代码

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

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

        list.push(1);
        list.push(2);
        list.push(3);

        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));
        list.push(4);
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));
        assert_eq!(list.pop(), None);
    }
}

完整代码

use std::ptr;
pub struct List<T> {
    head: Link<T>,
    tail: *mut Node<T>,
}

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

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

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

    pub fn push(&mut self, elem: T)  {
        let mut new_tail = Box::new(Node {
            elem: elem,
            next: None,
        });

        let raw_tail: *mut _ = &mut *new_tail;

        if !self.tail.is_null() {
            unsafe {
                (*self.tail).next = Some(new_tail);
            }
        } else {
            self.head = Some(new_tail);
        }
        
        self.tail = raw_tail;
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|head| {
            let head = *head;
            self.head = head.next;

            if self.head.is_none() {
                self.tail = ptr::null_mut();
            }
            head.elem
        })
    }
}

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

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

        list.push(1);
        list.push(2);
        list.push(3);

        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));
        list.push(4);
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));
        assert_eq!(list.pop(), None);
    }
}