单链表

还在学习中，写得可能不好，有错误的地方，恳请指正。

前言

因为 Rust 的所有权机制，实现起来比较麻烦。这次实现的是 C 风格（抄书）。

实现

数据结构

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

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

看一下数据结构，相比其它语言来说，这里 next 需要 Option 包裹，而不是直接给一个 Box 指针。利用 type 别名可以缩短类型长度。

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

这里是为了隐藏实现细节。

添加元素

这是头插法：

pub fn push(&mut self, elem: T) {
    // 取下 head 的 Link
    let old = self.head.take(); // 取走 Option，留下 None
    
    // 创建一个 Node
    let node = Node {
        elem: elem,
        next: old,
    };
    // 用 Option 包裹
    let link = Option::Some(Box::new(node));

    // 插入 头插法
    self.head = link;
}

简化下：

pub fn push(&mut self, elem: T) {
    let node = Node {
        elem: elem,
        next: self.head.take(),
    };

    self.head = Some(Box::new(node));
}

我想尾插呢？

pub fn push(&mut self, elem: T) {
    // 定义一个 l 
    let mut l;
    // 获取 head 的可变引用
    l = &mut self.head;
    // 循环
    while !l.is_none() {
        let node = l.as_mut().unwrap();
        l = &mut node.next;
    }

    // 创建一个 Node
    let node = Node {
        elem: elem,
        next: None,
    };
    // 用 Option 包裹
    let link = Option::Some(Box::new(node));

    // 插入 尾插法 此时 l = None
    *l = link;
}

简化下：

pub fn push(&mut self, elem: T) {
    let mut l = &mut self.head;
    while !l.is_none() {
        l = &mut l.as_mut().unwrap().next;
    }

    let node = Node {
        elem: elem,
        next: None,
    };
    *l =  Some(Box::new(node));
}

获取元素

index 按照书上的习惯，从 1 开始。

pub fn get_elem(&self, index: usize) -> Option<T> {
    let mut l = &self.head;
    let mut count = 1;
    while !l.is_none() && count != index {
        l = &l.as_ref().unwrap().next;
        count += 1;
    }

    if l.is_none() || index == 0 {     // index 大于链表长度或 index = 0
        return None;
    }

    Some(l.as_ref().unwrap().elem.clone())
}

整个过程和 C++ 类似。不过这里注意倒数第二行的返回值，用到了 clone() 方法，所以需要给我们的泛型加上约束。像这样：

pub struct List<T: Clone> {...

impl<T: Clone> List<T> {...

查找元素

pub fn locate_elem(&self, elem: T) -> Option<usize> {
    let mut l = &self.head;
    let mut count = 1;
    while !l.is_none() && l.as_ref().unwrap().elem != elem {
        l = &l.as_ref().unwrap().next;
        count += 1;
    }

    if l.is_none() {
        return None;
    }

    Some(count)
}

同上，这里又需要比较的 trait。需要加上 PartialEq，像这样：

pub struct List<T: Clone + PartialEq> {...

impl<T: Clone + PartialEq> List<T> {...

插入元素

pub fn insert(&mut self, index: usize, elem: T) -> Option<()> {
    let mut l = &mut self.head;
    let mut count = 1;
    while !l.is_none() && count != index {
        l = &mut l.as_mut().unwrap().next;
        count += 1;
    }

    if l.is_none() || index == 0 {
        return None;
    }

    // 类似 头插法
    let node = Node {
        elem: elem,
        next: l.take(),
    };

    *l = Some(Box::new(node));

    Some(())
}

删除元素

pub fn delete(&mut self, index: usize) -> bool {
    let mut l = &mut self.head;
    let mut count = 1;
    while !l.is_none() && count != index {
        l = &mut l.as_mut().unwrap().next;
        count += 1;
    }

    if l.is_none() || index == 0 {
        return false;
    }

    *l = l.as_mut().unwrap().next.take();
    true
}

随便测试一下

fn main() {
    let mut list = List::<i32>::new();
    list.push(12345);
    list.push(64890);
    list.push(11111);
    list.push(22222);
    list.push(33333);

    let e = list.get_elem(2).unwrap();
    println!("{}", e);

    let i = list.locate_elem(12345).unwrap();
    println!("{}", i);
    let i = list.locate_elem(11111).unwrap();
    println!("{}", i);
    
    list.insert(1, 44444);
    let e1 = list.get_elem(1).unwrap();
    let e2 = list.get_elem(2).unwrap();
    println!("1: {}, 2: {}", e1, e2);

    list.delete(1);
    let e = list.get_elem(2).unwrap();
    println!("{}", e);
}

参考

• Learn Rust With Entirely Too Many Linked Lists
• 《趣学数据结构》 陈小玉