美文网首页
Rust单链表

Rust单链表

作者: noobHuKai | 来源:发表于2022-01-02 21:09 被阅读0次

节点的结构

希望链表存储在堆上,所以使用 Box 包裹节点 Rust 没有空值,所以用 Option 在包裹一层

#[derive(PartialEq, Eq, Clone, Debug)]
struct ListNode<T> {
    pub data: T,
    pub next: Option<Box<ListNode<T>>>,
}

根据索引查找节点和找尾节点是通过递归来查找的

impl<T> ListNode<T> {
    // 新建一个节点
    #[inline]
    fn new(data: T) -> ListNode<T> {
        ListNode { next: None, data }
    }
    // 获取最后的节点
    fn get_last_node<'a>(&'a mut self) -> &'a mut Self {
        if let Some(ref mut node) = self.next {
            return node.get_last_node();
        }
        self
    }
    // 根据索引查找节点
    fn get_index_node<'a>(&'a mut self, cur: usize, index: usize) -> &'a mut Self {
        if cur >= index {
            return self;
        }
        if let Some(ref mut node) = self.next {
            return node.get_index_node(cur + 1, index);
        }
        self
    }
}

链表的结构

#[derive(PartialEq, Eq, Clone, Debug)]
struct List<T> {
    pub head: Option<Box<ListNode<T>>>,
    pub length: usize,
}

链表插入

链表的插入先判断头结点是否为空。如果插入的是头结点的话,需要将新的节点的下个节点设置为头结点,再将新结点设置为头节点。插入的是其他的位置的话,先找到索引的前一个节点,将前一个节点的下个节点设置为新节点,将新节点的下个节点设置为前节点的下个节点。

// 插入
fn insert(&mut self, index: usize, data: T) {
    let mut new_node = ListNode::new(data);
    if let Some(ref mut head) = self.head {
        if index == 0 {
            let head = self.head.take();
            new_node.next = head;
            self.head = Some(Box::new(new_node));
        } else {
            let mut prev_node = head.get_index_node(0, index - 1);
            let next_node = prev_node.next.take();
            new_node.next = next_node;
            prev_node.next = Some(Box::new(new_node));
        }
    } else {
        self.head = Some(Box::new(new_node));
    }
    self.length += 1
}

链表删除

// 删除
    fn delete(&mut self, index: usize) {
        if let Some(ref mut head) = self.head {
            self.length -= 1;
            if index == 0 {
                self.head = head.next.take();
            } else if index >= self.length {
                let prev_node = head.get_index_node(0, self.length - 1);
                prev_node.next.take();
            } else {
                let mut prev_node = head.get_index_node(0, index - 1);
                let mut next_node = prev_node.next.take();
                prev_node.next = next_node.as_mut().unwrap().next.take();
            }
        }
    }

链表的修改和查询

  // 修改
    fn change(&mut self, mut index: usize, data: T) {
        if let Some(ref mut head) = self.head {
            if index >= self.length {
                index = self.length;
            }
            let mut node = head.get_index_node(0, index);
            node.data = data;
        }
    }
    //  查询
    fn search(&mut self, index: usize) -> Option<T> {
        if let Some(ref mut head) = self.head {
            if index >= self.length {
                return None;
            }
            let node = head.get_index_node(0, index);
            let data = node.data;
            return Some(data);
        } else {
            return None;
        }
    }

链表打印

impl<T> Display for List<T>
where
    T: Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if let Some(head) = &self.head {
            let mut head = Some(head);
            while let Some(node) = head {
                write!(f, "{:?} => ", node.data).unwrap();
                head = node.next.as_ref();
            }
        }
        write!(f, "None")
    }
}

代码地址

相关文章

  • Rust单链表

    节点的结构 希望链表存储在堆上,所以使用 Box 包裹节点 Rust 没有空值,所以用 Option 在包裹一层 ...

  • 单链表 C++

    单链表 C++ 题目 1、创建单链表2、初始化单链表3、释放单链表4、获取单链表中元素的数量5、输出单链表中的所有...

  • 线性表:顺序表和链表

    顺序表(数组)优缺点 链表优点 单链表使用 单链表结构 单链表初始化 单链表初始化 单链表建立: 头插法 尾插法 ...

  • 单向链表算法

    单向链表 反转单向链表 单链表查找倒数第k个节点 单链表递归倒序打印 单链表排序 单链表删除重复节点

  • 链表基本操作

    1、删除单链表节点 2、插入单链表结点 单链表具体实现

  • 25_静态单链表的实现

    关键词: 单链表的一个缺点、静态单链表设计思路、静态单链表的继承层次结构、静态单链表的实现思路、静态单链表的实现 ...

  • 线性表的链式存储-单链表

    单链表操作 [x] 单链表的创建(尾插法、头插法) [x] 单链表的查找操作 [x] 单链表的删除操作 [x] 单...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下: 1.1 递归反转整个单链表...

  • 单链表反转

    单链表 单链表反转 递归方法

  • JavaScript数据结构2——单链表

    以下的代码包括了以下几部分 单链表初始化 单链表的插入 单链表的删除 单链表的创建(头插法) 单链表的创建(尾插法...

网友评论

      本文标题:Rust单链表

      本文链接:https://www.haomeiwen.com/subject/vbltcrtx.html