用rust实现简单的双向链表

本文将通过实现一个简单的双向链表，理解Rust中的引用计数 (Rc)、引用单元 (RefCell) 和内部可变性 (Interior Mutability) 的概念。

双向链表是一种常见的数据结构，它允许我们在节点之间向前或向后遍历。为了实现双向链表，我们需要存储指向下一个和前一个节点的指针。然而，Rust的所有权系统会带来一些挑战。例如，因为简单使用引用(reference)可能会导致悬垂指针(dangling pointer）问题，这在Rust中是无法编译通过的。

使用智能指针Rc和RefCell

为了克服这些挑战，Rust提供了智能指针类型，例如 Rc 和 RefCell。

Rc (Reference Counting) 用于共享所有权。它允许多个地方引用同一个数据，并会在引用计数为零时自动释放内存。
RefCell (Reference Cell) 提供可变借用(mutable borrow)的功能。虽然Rc本身只能进行不可变借用，但通过 RefCell包装数据，我们可以实现对内部数据的可变访问。

代码1：定义链表节点结构体

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

type NodeRef<T> = Rc<RefCell<Node<T>>>;

在这段代码中，我们定义了Node结构体，用来表示双向链表中的节点。

data字段存储节点的实际数据。
prev和next字段分别存储指向链表中前一个和后一个节点的指针。
NodeRef类型是Rc<RefCell<Node<T>>>的别名。它表示对Node<T>的引用计数指针，并将其内部数据用RefCell包装，允许可变借用。

代码2：定义双向链表

struct DoublyLinkedList<T> {
    head: NodeRef<T>,
}

impl<T> DoublyLinkedList<T> {
    fn new(data: T) -> Self {
        Self {
            head: Rc::new(RefCell::new(Node::new(data))),
        }
    }
}

在DoublyLinkedList结构体中，我们使用head字段存储指向链表头结点的指针 (NodeRef<T>)。 new 函数负责创建链表，它通过 Rc::new 创建一个引用计数为1的Node对象，并将其用RefCell包装，最后将该引用赋值给head字段。

内部可变性

虽然Rc本身只能进行不可变借用，但通过RefCell的borrow_mut方法，我们可以获取对内部数据的可变借用。

代码3：尾插操作

fn append(&mut self, data: T) {
    let tail = Self::get_tail(self.head.clone());
    let new_node = Rc::new(RefCell::new(Node::new(data)));
    new_node.borrow_mut().prev = Some(tail.clone());
    tail.borrow_mut().next = Some(new_node);
}

append函数用于向链表尾部添加新节点。

首先，我们调用 get_tail 找到链表的尾节点。
创建一个新的Node 对象并将其用Rc和RefCell包装。
然后，使用borrow_mut 获取对新节点内部数据的可变借用，并设置其prev字段指向尾节点。
最后，同样使用 borrow_mut获取对尾节点内部数据的可变借用，并设置其next字段指向新节点。

通过RefCell的borrow_mut方法，我们可以在保持所有权不变的情况下修改内部数据。

代码4：get_tail 函数

fn get_tail(node: NodeRef<T>) -> NodeRef<T> {
    match &node.borrow().next {
        Some(next) => Self::get_tail(next.clone()),
        None => node.clone(),
    }
}

get_tail函数用于查找链表的尾节点。它接收一个NodeRef<T>类型的参数node，表示当前正在检查的节点。

node.borrow().next获取当前节点的next 字段。由于next是Option<NodeRef<T>>类型，我们需要使用 match表达式进行模式匹配。
如果next是Some(next)，表示当前节点不是尾节点，那么我们递归调用get_tail(next.clone())，继续查找下一个节点。这里clone()是必要的，因为它克隆了Rc指针，增加了引用计数，使得我们可以在递归调用中使用next。
如果next是None，表示当前节点是尾节点，那么我们返回 node.clone()。同样，clone() 克隆了Rc指针，使得调用者可以持有尾节点的所有权。

这个递归过程会一直进行，直到找到next字段为None的节点，即尾节点。

遍历链表

代码5：遍历链表

fn main() {
    let mut list = DoublyLinkedList::new("head");
    // ... (链表节点初始化代码省略)
    let mut node = list.head();
    loop {
        println!("{}", node.borrow().data());
        if node.borrow().next.is_none() {
            break;```rust
        } else {
            let next_item = node.borrow().next.as_ref().unwrap().clone();
            node = next_item;
        }
    }
    println!("====================");
    let mut node = list.tail();
    loop {
        println!("{}", node.borrow().data());
        if node.borrow().prev.is_none() {
            break;
        } else {
            let prev_item = node.borrow().prev.as_ref().unwrap().clone();
            node = prev_item;
        }
    }
}

这段代码演示了如何正向和反向遍历链表。

我们首先从 list.head() 获取头节点。
在循环中，我们使用node.borrow().data() 获取当前节点的数据并打印。
然后，通过 node.borrow().next.as_ref().unwrap().clone() 获取下一个节点的Rc 指针，并将其赋值给node，从而移动到下一个节点。注意这里需要clone()，因为我们需要拥有Rc 的所有权才能在下次循环中使用。as_ref() 将 Option<Rc<RefCell<Node<T>>>> 转换为 Option<&Rc<RefCell<Node<T>>>>，unwrap()解包Option，因为在循环中我们已经确保了next 不为 None。
反向遍历的逻辑类似，只是使用prev字段来移动到前一个节点。

总结

我们学习了如何使用Rc和RefCell 在 Rust 中实现双向链表。Rc允许我们共享所有权，而RefCell提供了内部可变性的能力，使我们能够在共享所有权的情况下修改数据。

虽然使用Rc和RefCell可以实现双向链表，但它也有一些缺点，例如运行时借用检查 (runtime borrow checking) 的开销。在某些情况下，使用unsafe代码或其他方法可能会更有效率。然而，对于初学者来说，理解Rc和RefCell是非常重要的，它们是Rust中处理共享可变性的重要工具。

完整代码:

use std::cell::RefCell;
use std::rc::Rc;

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

type NodeRef<T> = Rc<RefCell<Node<T>>>;

struct DoublyLinkedList<T> {
    head: NodeRef<T>,
}

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

    fn data(&self) -> &T {
        &self.data
    }
}

impl<T> DoublyLinkedList<T> {
    fn new(data: T) -> Self {
        Self {
            head: Rc::new(RefCell::new(Node::new(data))),
        }
    }

    fn head(&self) -> NodeRef<T> {
        self.head.clone()
    }

    fn tail(&self) -> NodeRef<T> {
        Self::get_tail(self.head.clone())
    }

    fn get_tail(node: NodeRef<T>) -> NodeRef<T> {
        match &node.borrow().next {
            Some(next) => Self::get_tail(next.clone()),
            None => node.clone(),
        }
    }

    fn append(&mut self, data: T) {
        let tail = Self::get_tail(self.head.clone());
        let new_node = Rc::new(RefCell::new(Node::new(data)));
        new_node.borrow_mut().prev = Some(tail.clone());
        tail.borrow_mut().next = Some(new_node);
    }
}

fn main() {
    let mut list = DoublyLinkedList::new("head");
    list.append("1st");
    list.append("2nd");
    list.append("3rd");
    list.append("tail");
    let mut node = list.head();
    loop {
        println!("{}", node.borrow().data());
        if node.borrow().next.is_none() {
            break;
        } else {
            let next_item = node.borrow().next.as_ref().unwrap().clone();
            node = next_item;
        }
    }
    println!("====================");
    let mut node = list.tail();
    loop {
        println!("{}", node.borrow().data());
        if node.borrow().prev.is_none() {
            break;
        } else {
            let prev_item = node.borrow().prev.as_ref().unwrap().clone();
            node = prev_item;
        }
    }
}