介绍

视频地址：www.bilibili.com/video/av78062009/

相关源码：github.com/anonymousGiga/Rust-link...

链表定义

我们重新定义链表如下：

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);}
}