如何使用rust实现简单的单链表

目录
  • 前言
  • 1.链表节点的定义
  • 2.链表的定义
  • 3.实现从链表头部插入节点的prepend方法
  • 4.为链表实现Display trait定制链表的打印显示
  • 5.为链表实现翻转链表功能的reverse方法
  • 注意事项
  • 总结

前言

作为初学者,在掌握了rust的基本语法和所有权机制,尝试写一下常见数据结构和算法,目标是为了更好的理解rust的所有权机制。 受限于个人目前对rust仍处于入门阶段,因此本文代码实现不一定是最合适的,甚至可能存在问题。

今天的目标是用rust实现一个简单的单链表LinkedList,同时为此链表提供从头部插入元素(头插法)、翻转链表、打印链表的功能。

1.链表节点的定义

实现链表,首先是实现链表的节点,根据其他编程语言的经验,于是用rust首先写出了下面的链表节点结构体定义:

代码片段1:

struct Node<T> {
    data: T,
    next: Option<Node<T>>, // recursive type `Node` has infinite size
}

在代码片段1中,定义一个Node结构体,data字段使用了泛型类型T用于链表节点的数据。 next使用了Option枚举,即如果该节点没有下一个节点时,next是可空的,在rust中没有其他编程语言中的空值(null, nil),而是提供了Option的解决方案,如果该链表节点的下个节点为空,则其next取值为Option::None。

遗憾的是代码片段1是无法编译通过的,报了recursive type ``Node`` has infinite size的编译错误。回顾Rust内存管理的基础知识,Rust需要在编译时知道一个类型占用多少空间,Node结构体内部嵌套了它自己,这样在编译时就无法确认其占用空间大小了。 在Rust中当有一个在编译时未知大小的类型,而又想要在需要确切大小的上下文中使用这个类型值的时候,可以使用智能指针Box。将next字段的类型修改为Option<Box<Node<T>>>,这样嵌套的类型为Box,嵌套的Node将会被分配到堆上,next字段在栈上存储的只是智能指针Box的数据(ptr, meta),这样在编译时就能确定Node类型的大小了。将代码片段1的修改如下:

代码片段2:

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

修改完成后,可以编译通过了。根据next: Option<Box<Node<T>>>,每个链表节点Node将拥有它下一个节点Node的所有权。

2.链表的定义

定义完链表之后,下一步再定义一个结构体LinkedList用来表示链表,将会封装一些链表的基本操作。 结构体中只需方一个链表头节点的字段head,类型为Option<Box<Node<T>>>。

代码片段3:

/// 单链表节点
#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

/// 单链表
#[derive(Debug)]
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

为了便于使用,再给Node和LinkedList这两个结构体各添加一下关联函数new。

代码片段4:

impl<T> Node<T> {
    fn new(data: T) -> Self {
        Self { data: data, next: None }
    }
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }
}

Node的new函数用来使用给定的data数据创建一个孤零零的(没有下一个节点的)节点。

LinkedList的new函数用来创建一个空链表。

3.实现从链表头部插入节点的prepend方法

前面已经完成了链表和链表节点的定义,下面我们为链表实现了prepend方法,这个方法将采用头插法的方式向链表中添加节点。

代码片段5:

impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    /// 在链表头部插入节点(头插法push front)
    fn prepend(&mut self, data: T) -> &mut Self {
        // 从传入数据构建要插入的节点
        let mut new_node = Box::new(Node::new(data));
        match self.head {
            // 当前链表为空时, 插入的节点直接作为头节点
            None => self.head = Some(new_node),
            // 当前链表非空时, 插入的节点作为新的头节点插入到原来的头结点前面
            Some(_) => {
                // 调用Option的take方法取出Option中的头结点(take的内部实现是mem::replace可避免内存拷贝), 作为新插入节点的下一个节点
                new_node.next = self.head.take();
                // 将新插入的节点作为链表的头节点
                self.head = Some(new_node);
            }
        }
        self
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    print!("{ll:?}"); // LinkedList { head: Some(Node { data: 1, next: Some(Node { data: 2, next: Some(Node { data: 3, next: Some(Node { data: 4, next: Some(Node { data: 5, next: None }) }) }) }) }) }
}

4.为链表实现Display trait定制链表的打印显示

前面我们实现了链表头部插入节点的prepend方法,并在main函数中构建了一个链表,以Debug的形式打印出了链表的信息。

为了使打印信息更好看,我们决定为LinkedList实现Display trait,使链表打印的格式类似为1 -> 2 -> 3 -> 4 -> 5 -> None。

代码片段6:

use std::fmt::Display;

......

impl<T: Display> Display for LinkedList<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.head.is_none() {
            // 如果链表为空, 只打印None
            write!(f, "None\n")?;
        } else {
            // 下面将遍历链表, 因为只是打印, 能获取链表各个节点的数据就行, 所以不需要获取所有权
            let mut next = self.head.as_ref();
            while let Some(node) = next {
                write!(f, "{} -> ", node.data)?;
                next = node.next.as_ref();
            }
            write!(f, "None\n")?;
        }
        Ok(())
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    print!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
}

5.为链表实现翻转链表功能的reverse方法

代码片段7:

impl<T> LinkedList<T> {
    ......

    /// 翻转链表
    fn reverse(&mut self) {
        let mut prev = None; // 记录遍历链表时的前一个节点
        while let Some(mut node) = self.head.take() {
            self.head = node.next;
            node.next = prev;
            prev = Some(node);
        }
        self.head = prev;
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    println!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
    ll.reverse(); // 5 -> 4 -> 3 -> 2 -> 1 -> None
    println!("{ll}");
}

注意事项

只有一个可变引用

在C里面,如果要在链表的头部插入元素,可以这样写

Node* new_node = create_new_node(v);
new_node->next = head;
head = new_node;

但是在Rust里面你不能这样做。

在Rust中,常见的指针是Box<T>,和其他对象一样,Box<T>对象同一时刻只能有一个可变引用,而在上面的插入过程中,第2行,有两个指针指向同一个头结点,这个在Rust中是有问题的。

那在Rust里面,要实现在头部插入的功能,首先得把指针从head里面拿出来,然后再放到新的结点里面去,而不是直接复制,这里需要用到Option中的take方法,即把Option中的东西取出来。

总结

到此这篇关于如何使用rust实现简单的单链表的文章就介绍到这了,更多相关rust实现单链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 如何使用rust实现简单的单链表

    目录 前言 1.链表节点的定义 2.链表的定义 3.实现从链表头部插入节点的prepend方法 4.为链表实现Display trait定制链表的打印显示 5.为链表实现翻转链表功能的reverse方法 注意事项 总结 前言 作为初学者,在掌握了rust的基本语法和所有权机制,尝试写一下常见数据结构和算法,目标是为了更好的理解rust的所有权机制. 受限于个人目前对rust仍处于入门阶段,因此本文代码实现不一定是最合适的,甚至可能存在问题. 今天的目标是用rust实现一个简单的单链表Linked

  • C++ 单链表的基本操作(详解)

    链表一直是面试的高频题,今天先总结一下单链表的使用,下节再总结双向链表的.本文主要有单链表的创建.插入.删除节点等. 1.概念 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素 + 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据.如下图: 2.链表的基本操作 SingleList.cpp: #include "stdafx.h" #include "SingleList.h&

  • C语言数据结构实例讲解单链表的实现

    目录 1.单链表 2.单链表的实现 头文件 函数的实现 (1)打印链表 (2)动态申请结点 (3)尾插 (4)头插 (5)尾删 (6)头删 (7)查找 (8)在pos之前插入 (9)删除pos (10)在pos之后插入 (11)在pos后删除 (12)最后用完记得销毁 3.各功能的测试 这里我们来简单实现单链表的增删查找. 1.单链表 概念:链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 . (链表和我们生活中最接近的就是火车了.) 2.单链

  • Python单链表简单实现代码

    本文实例讲述了Python单链表简单实现代码.分享给大家供大家参考,具体如下: 用Python模拟一下单链表,比较简单,初学者可以参考参考 #coding:utf-8 class Node(object): def __init__(self, data): self.data = data self.next = None class NodeList(object): def __init__(self, node): self.head = node self.head.next = No

  • Python单链表的简单实现方法

    本文实例讲述了Python单链表的简单实现方法,分享给大家供大家参考.具体方法如下: 通常来说,要定义一个单链表,首先定义链表元素:Element.它包含3个字段: list:标识自己属于哪一个list datum:改元素的value next:下一个节点的位置 具体实现代码如下: class LinkedList(object): class Element(object): def __init__(self,list,datum,next): self._list = list self.

  • Java单链表的简单操作实现教程

    前言 用Java实现单链表的简单操作,阅读本文和上一篇文章体会Java中类与C++中结构体指针的区别 提示:以下是本篇文章正文内容,下面案例可供参考 一.基本实现思路 构造结点类 构造链表类 具体测试实现 二.代码实现 1.定义结点类 package list.test01; /* *定义结点类 */ public class Node { private int data; public Node next; public Node(int data) { this.data = data;

  • java实现简单单链表

    本文实例为大家分享了java实现简单单链表的具体代码,供大家参考,具体内容如下 一.定义: 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(相当于JAVA中的引用,指示后继元素存储位置,),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据. 二.结构: 如图所示,data就是当前节点的数据,next是指针,指针存放的是内存地址,是当前结点的下一结点内存地址,顺着这个地址就能找

  • 利用C++简单实现顺序表和单链表的示例代码

    本文主要给大家介绍了关于C++实现顺序表和单链表的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍: 一.顺序表示例代码: #include <assert.h> #include <iostream> using namespace std; typedef int Datatype; class SeqList { public: SeqList() :_array(NULL) ,_size(0) ,_capacity(0) { } SeqList(const

  • Java模拟单链表和双端链表数据结构的实例讲解

    模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1.集合中必存在唯一的一个"第一元素": 2.集合中必存在唯一的一个 "最后元素" : 3.除最后一个元素之外,均有 唯一的后继(后件):

  • java 数据结构单链表的实现

    java 数据结构单链表的实现 单链表实现链表的打印及元素删除操作,链表的实现主要是next属性的定义,将一堆节点关联起来的.实现简单的链表如下: public class LinkNode { private int value; private LinkNode next; public LinkNode(int x) { value = x; } public LinkNode getNext(){ return next; } public void setNext(LinkNode n

随机推荐