关键词:
【中文标题】Rust 中的单链表【英文标题】:Singly-Linked List in Rust 【发布时间】:2022-01-09 14:44:12 【问题描述】:我最近一直在尝试自学一些 Rust,并想通过实现一个简单的链表来练习一下。我从 Rust 库的链表中获得了一些灵感,并尝试复制我已经理解的部分。我还决定暂时将其设为单链接。
struct Node<T>
element: T,
next: Option<Box<Node<T>>>,
impl<T> Node<T>
fn new(element: T) -> Self
Node
element: element,
next: None,
fn append(&mut self, element: Box<Node<T>>)
self.next = Some(element);
pub struct LinkedList<T>
head: Option<Box<Node<T>>>,
tail: Option<Box<Node<T>>>,
len: u32,
impl<T> LinkedList<T>
pub fn new() -> Self
head: None,
tail: None,
len: 0,
pub fn push(&mut self, element: T)
let node: Box<Node<T>> = Box::new(Node::new(element));
match self.tail
None => self.head = Some(node),
Some(mut ref tail) => tail.append(node),
self.tail = Some(node);
self.len += 1;
pub fn pop(&mut self) -> Option<T>
//not implemented
pub fn get(&self, index: u32) -> Option<T>
//not implemented
这是我到目前为止所得到的;据我了解,这段代码的问题是Box
不能有多个引用以保护内存安全。
所以当我将列表头设置为节点时
None => self.head = Some(node),
我不能继续设置
self.tail = Some(node);
稍后,我的理解到目前为止是否正确?这样做的正确方法是什么?我必须像在库中那样使用Shared
,还是有办法可以使用Box
或其他类型?
【问题讨论】:
obligatory reference (Learning Rust With Entirely Too Many Linked Lists) 请注意,传统的单链接(Cons List)不会记住tail
。这是一种允许在 O(1) 中追加的方法,但不是必需的。
@Oliver 如果它回答了你的问题,你能接受 Ijedrzs 的回答吗?否则请说明缺少的内容。
【参考方案1】:
你可以使用比这更简单的东西,只使用你的节点
use std::fmt;
struct Payload
id: i32,
value: i32,
impl fmt::Display for Payload
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
write!(f, "(, )", self.id, self.value)
struct Node<T>
element: T,
next: Option<Box<Node<T>>>,
impl<T> Node<T> where T: std::fmt::Display
fn new(element: T) -> Self
Node
element: element,
next: None,
fn append(&mut self, element: T)
match &mut self.next
None => let n = Node
element: element,
next: None,
;
self.next = Some(Box::new(n));
,
Some(ref mut x) => x.append(element),
fn list(& self)
println!("", self.element);
match &self.next
None => ,
Some(x) => x.list(),
fn main()
let mut h = Node::new(Payload id:1, value:1);
h.append(Payload id:2, value:2);
h.append(Payload id:3, value:3);
h.append(Payload id:4, value:4);
h.append(Payload id:5, value:5);
h.list();
h.append(Payload id:6, value:6);
h.list();
【讨论】:
所以它是递归的append
,它是非性能的
@prehistoricpenguin 如果我们只迭代元素并执行它而不是递归会更好吗?【参考方案2】:
您的问题是您在移动某个值 (node
) 后尝试使用它;由于Box<Node<T>>
没有实现Copy
,当你在match
表达式中使用它时:
match self.tail
None => self.head = Some(node),
Some(ref mut tail) => tail.append(node),
node
被移动到 self.head
或 self.tail
,以后不能再使用。除了阅读必读的 Learning Rust With Entirely Too Many Linked Lists 以了解在 Rust 中实现链表的不同方式之外,我建议您首先在 Rust 的基本概念领域做更多的研究,尤其是:
【讨论】:
openharmony中的hdf单链表及其迭代器(代码片段)
...统一般自己设计和实现链表这种数据结构。单链表是链表中的一种,本文描述OpenAtomOpenHarmony(以下简称“OpenHarmony”)中HDF软件模块自己定义的单链表,并学习其设计和实现方法。其中包含一些技巧,可以提高读者的软件开发能... 查看详情
删除单链表保留顺序中的重复项
】删除单链表保留顺序中的重复项【英文标题】:removeduplicatesinsinglylinkedlistretainingorder【发布时间】:2012-09-2800:34:10【问题描述】:所以我有一个单链表的抽象数据类型,而我的编译器在运行这部分测试代码时卡住了。test.removeD... 查看详情
单链表~增删查改(附代码)~简单实现(代码片段)
...非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 今天我们主要了解的是链表中的单链表我们对一个结构体简单定义typed 查看详情
[lintcode]linkedlistcycle单链表中的环
Givenalinkedlist,determineifithasacycleinit.ExampleGiven-21->10->4->5,tailconnectstonodeindex1,returntrueChallengeFollowup:Canyousolveitwithoutusingextraspace? s 查看详情
java单链表的实现自己动手写一个单链表(代码片段)
...存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象)+指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每... 查看详情
如何找出单链表中的倒数第k个元素
...化。于是想到了第二种方法,如果从头至尾的方向从链表中的某个元素开始,遍历k个元 查看详情
在单链表中的特定节点之前插入一个节点
】在单链表中的特定节点之前插入一个节点【英文标题】:Insertinganodebeforeaspecificnodeinasinglylinkedlist【发布时间】:2021-08-0221:11:03【问题描述】:我已经实现了一种在特定节点之前插入新节点的方法。#ifndefFORWARD_SINGLY_LINKED_LIST_H#de... 查看详情
13.删除单链表中重复的元素
...链表就能搞定。同高级函数9的原因,我不太会使用C++STL中的hash。而如果使用set集合来存储链表中的所有的值,实际上效率和每次重新遍历单链表是一样的。“用了c++标准库中的set来保存访问过的元素,所以很方便的就可以 查看详情
数据结构——单链表
...点访问后继结点。B、定义内部结点类型,用于描述链表中的结点的数据域和指针域。C、实现线性表的关键操作2、单链表中结点的定义structNode:publicObject{Tvalue;//数据域Node*next;//指针域};3、单链表的内部结构头结点不存储实际的数... 查看详情
oj--单链表
#include<stdio.h>#include<stdlib.h>typedefintEtype;//定义结点类型typedefstructNode{Etypedata;//单链表中的数据域structNode*next;//单链表的指针域}Node,*List,*position;//单链表的初始化ListListInit(){Node*L;/ 查看详情
单链表,main函数中的一个小问题
】单链表,main函数中的一个小问题【英文标题】:Singlylinkedlist,Asmallprobleminmainfunction【发布时间】:2021-09-0311:51:12【问题描述】:编写此程序以删除排序链表中具有相同数据的Node,但while循环未按预期执行。通过使用一些printf语... 查看详情
java中的单链表栈队列三种数据结构(代码片段)
一、单链表1、在我们数据结构中,单链表非常重要。它里面的数据元素是以结点为单位,每个结点是由数据元素的数据和下一个结点的地址组成,在java集合框架里面 LinkedList、HashMap(数组加链表)等等的底... 查看详情
c语言中数据结构中的单向链表的问题;
...下:structLNode//定义单链表节点类型ElemTypedata;//存放结点中的数据信息LNode*next;//指示下一个结点地址的指针⑵线性表基本操作可包括如下一些:①voidInitList(LNode*&H)//初始化单链表②voidClearList(LNode*&H)//清除单链表③intLengthList(LNode*H... 查看详情
数据结构(线性表之单链表)(代码片段)
...表之头插法单链表之尾插法单链表之把一个节点插到链表中的任意位置单链表之查找链表中是否某个元素单链表之删除的一次出现value值的节点单链表之删除链表中出现value值 查看详情
单链表练习题(代码片段)
...建立一个带头结点的单链表,再输入一个数据m,将单链表中的值为m的结点全部删除。分别输出建立的初始单链表和完成删除后的单链表。Input第一行输入数据个数n;第二行依次输入n个整数;第三行输入欲删除数据m。Output第一行... 查看详情
c_cppc中的单链表-现在只实现交换(代码片段)
第二十五课静态单链表的实现
...据元素。配合单链表就形成了静态单链表。在静态单链表中的操作和普通单链表几乎一样,只有两个函数有差异:create和destroy静态单链表的继 查看详情
单链表实现“插入”和“删除”操作
...在单链表中。根据插入操作的逻辑定义,还需修改结点a中的指针域,令其指向结点x,而结点x中的指针域应该指向b结点,从而实现3个元素a 查看详情