介绍

视频地址：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);}
}