当前位置：首页 > article >正文

【Rust中的链表实现】

article 2024/11/13 19:20:43

Rust中的链表实现

链表
C/C++中的链表定义
Rust中的链表定义
链表push_top
- next: self.head.take() 为什么是这种写法？
- 链表pop
- 链表peek
- 链表迭代器Iter

链表

C/C++中的链表通常出现在系统级编程的实现中，抑或是在面试考试中常被提及，此数据结构在大学课程中也十分的经典，链表的特点就是插入代价地低，查找消耗高，链表的结构通常由一个指针+value组成一个节点，指针指向下一个节点，从而将数据串联起来。C++中的List容器，Hash数据结构中的链式存储解决Hash冲突都是使用的链表这样的数据结构。

C/C++中的链表定义

typedef struct ListNode {
    int value;
    struct ListNode* next;  
} ListNode;

next既每一个节点中指向下一个节点的指针，所谓指向下一个节点，即存储下一个节点的地址，从而后续通过解引用把数据拿出来。C++中的指针相对自由，它的声明和释放在不使用智能指针的情况下均需要由开发者进行释放，带来一定便利性的同时也引入了空悬指针的风险，而Rust中由于所有权和生命周期的存在，在声明节点，改变链表，遍历链表上需要注意的事项在实现时也多一些，由于Rust编译器的严格性，这些需要注意的点并不会因为开发者的疏漏而在runtime才暴露，相反，如果开发者对Rust语言特性不熟悉，甚至无法写出能够通过编译的链表数据结构。

ps: 日常的开发中，Vec！和Deque都已经足够好用也足以覆盖百分之90的需要，就算真的需要使用链表也有第三方库的存在，再此我们从定义到关键方法实现，就是为了更加理解和熟悉Rust 的语言特性。

Rust中的链表定义

type Link<T> = Option<Box<LinkNode<T>>>;
//首先为了方便编写，为Option<Box<LinkNode<T>>> 起个别名
//Option 即可以是空的，如空链表或者链表最后一个节点的指向是空
//Box 可使得LinkNode 嵌套定义时Rust编译器可确定其大小，从而能够通过编译。
pub struct List<T> { //这里仅是使定义看起来更加明确，尤其是在实现头插链表时，head即指向整个链表的第一个节点，
					 //pub是为了保持其可被crate外访问内部数据。
    head: Link<T>,
}
struct LinkNode<T> {
    elem: T,
    next: Link<T>,//这里实际上是Option<Box<LinkNode<T>>>，即LinkNode嵌套定义处。
}

链表push_top

    pub fn push_top(&mut self, elem: T) {
        let new_link_node = Box::new(LinkNode { //建造新节点，赋值，并将新节点的next指向原节点
            elem: elem,
            next: self.head.take(),
        });
        self.head = Some(new_link_node); //将head指向新节点
    }

next: self.head.take() 为什么是这种写法？

由于Rust所有权的存在，我们无法如下写法：

    pub fn push_top(&mut self, elem: T) {
        let new_link_node = Box::new(LinkNode { //建造新节点，赋值，并将新节点的next指向原节点
            elem: elem,
            next: self.head, <---------------ERROR------------------
        });
        self.head = Some(new_link_node); //将head指向新节点
    }

next: self.head 如此即是将head的所有权直接转移给next，而self又是借用的，你不可以将你借来的东西直接送给别人。

考虑使用#[derive(Clone)]
这是可以的，为什么不，Clone本身的消耗对于直接的转移来讲还是代价有些大。
self.head.take()源码：

    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[rustc_const_unstable(feature = "const_option", issue = "67441")]
    pub const fn take(&mut self) -> Option<T> {
        // FIXME replace `mem::replace` by `mem::take` when the latter is const ready
        mem::replace(self, None)
    }

可见，take内部使用了replace，即将head值赋予next，并将head置为None。让我们继续看一下replace的源码：

pub const fn replace<T>(dest: &mut T, src: T) -> T {
    // It may be tempting to use `swap` to avoid `unsafe` here. Don't!
    // The compiler optimizes the implementation below to two `memcpy`s
    // while `swap` would require at least three. See PR#83022 for details.

    // SAFETY: We read from `dest` but directly write `src` into it afterwards,
    // such that the old value is not duplicated. Nothing is dropped and
    // nothing here can panic.
    unsafe {
        let result = ptr::read(dest);
        ptr::write(dest, src);
        result
    }
}

显而易见的，源代码很简单，尽管使用了一块unsafe，但是却很safe，先将源数据读出来，再将新数据写进去，最后返回一个原来的数据。

链表pop

代码示例：

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

这里使用pop的作用是一样的，不能直接转移内部的所有权，所以使用take把值偷出来用，再使用map闭包将头指针后移，最后将原来的数据扔出去。

链表peek

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

peek用于返回链表表头的元素引用，需要注意的点是一样的，开发者不该也不能将funciton内部变量出借，即如果我们没有使用as_ref，那当我们调用map的时候由于所有权的转移，我们最后返回的引用就将内部变量引用出去了，就会导致编译不过。归根揭底还是所有权的使用需要开发者多加注意。

链表迭代器Iter

代码示例：

pub struct Iter<'a, T> {
    next: Option<&'a LinkNode<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|link_node| {
            self.next = link_node.next.as_deref();
            &link_node.elem
        })
    }
}