Rust链表的使用及实现

发布时间：2023-05-19

一、链表的概述

链表（Linked List）是数据结构的一种，它通过一组节点来表示一个序列。每个节点包含了数据和一个指向下一个节点的引用或指针。 链表和数组一样都是线性数据结构，但其对内存的使用更加灵活。链表不需要一块连续的内存空间，而是将每一个节点存储在任意的内存块中。这使得插入和删除操作更加高效。

二、Rust链表的创建

Rust内置了 std::collections::LinkedList，可以使用它来创建一个链表。

use std::collections::LinkedList;
let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

以上创建了一个包含有3个元素的链表：[1, 2, 3]，push_back 是将元素插入到链表末尾的方法。

三、Rust链表元素的访问

Rust链表的元素访问需要使用到迭代器。

use std::collections::LinkedList;
let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
for elem in list.iter() {
    println!("{}", elem);
}

以上遍历了链表中所有元素，并输出了每个元素的值。

四、Rust链表的插入和删除

由于链表的存储空间不是连续的，因此插入和删除操作比数组要高效。Rust链表提供了多种插入和删除元素的方法。 在链表的头部插入元素：

use std::collections::LinkedList;
let mut list = LinkedList::new();
list.push_back(2);
list.push_back(3);
list.push_front(1);
assert_eq!(list.front(), Some(&1));

在链表中间插入元素：

use std::collections::LinkedList;
let mut list = LinkedList::new();
list.push_back(1);
list.push_back(3);
list.insert(1, 2);
assert_eq!(list, [1, 2, 3]);

在链表的尾部插入元素：

use std::collections::LinkedList;
let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
assert_eq!(list.back(), Some(&3));

删除链表中的元素：

use std::collections::LinkedList;
let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.pop_back();
list.pop_front();
assert_eq!(list, [2]);

五、Rust链表的实现

下面是一个简单的 Rust 链表实现，包含节点的定义，以及节点和链表的基本操作方法。

pub struct Node<T> {
    pub data: T,
    pub next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
    pub fn new(data: T) -> Self {
        Node {
            data,
            next: None,
        }
    }
    pub fn append(&mut self, data: T) {
        let mut current_node = self;
        loop {
            if let Some(ref mut next_node) = current_node.next {
                current_node = &mut **next_node;
            } else {
                current_node.next = Some(Box::new(Node::new(data)));
                break;
            }
        }
    }
    pub fn remove(&mut self, target: &T) -> Option<T> where T: PartialEq + Copy {
        let mut current_node = self;
        let mut prev_node: Option<&mut Node<T>> = None;
        loop {
            if current_node.data == *target {
                if let Some(ref mut prev) = prev_node {
                    prev.next = current_node.next.take();
                } else {
                    return current_node.next.take().map(|node| node.data);
                }
            } else {
                prev_node = Some(current_node);
            }
            current_node = if let Some(ref mut next) = current_node.next {
                &mut **next
            } else {
                break;
            }
        }
        None
    }
}
pub struct LinkedList<T> {
    pub head: Option<Box<Node<T>>>,
}
impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList { head: None }
    }
    pub fn append(&mut self, data: T) {
        if let Some(ref mut head) = self.head {
            head.append(data);
        } else {
            self.head = Some(Box::new(Node::new(data)));
        }
    }
    pub fn remove(&mut self, target: &T) -> Option<T> where T: PartialEq + Copy {
        if let Some(ref mut head) = self.head {
            if head.data == *target {
                self.head = head.next.take();
                return Some(head.data);
            }
            return head.remove(target);
        }
        None
    }
}

以上是一个简单的链表实现示例，其中包含了节点的定义，以及节点和链表的基本操作方法。

六、总结

本文介绍了 Rust 链表的创建、元素访问、插入和删除操作，以及一个简单的链表实现示例。 链表是数据结构中非常常用的一种，对于需要频繁进行插入和删除操作的情况，链表比数组更加高效。Rust 的 std::collections::LinkedList 提供了多种插入和删除元素的方法，可以方便快捷地实现链表的操作。

推荐文章