掌握Rust双向链表（从零开始构建高效可变数据结构）

为什么在 Rust 中实现双向链表很困难？

Rust 的所有权系统（Ownership System）要求内存安全，禁止同时存在多个可变引用。而双向链表天然需要节点之间相互持有可变引用（前驱和后继），这直接违反了 Rust 的借用规则。因此，标准库 std::collections 提供了 LinkedList，但它是一个单向链表。

要实现 Rust数据结构 中的双向链表，我们必须借助 Rc<RefCell<T>> 或 Box + unsafe。本文将采用更安全的方式：使用 Rc<RefCell<Node>> 来管理共享所有权和内部可变性。

步骤一：定义节点结构

首先，我们定义一个节点（Node）结构体：

use std::rc::Rc;use std::cell::RefCell;#[derive(Debug)]struct Node {    data: i32,    next: Option<Rc<RefCell<Node>>>,    prev: Option<Rc<RefCell<Node>>>,}

这里：
- Rc 允许多个所有者共享同一个节点。
- RefCell 提供运行时借用检查，允许内部可变性。
- next 和 prev 都是 Option<Rc<RefCell<Node>>> 类型，表示可能为空。

步骤二：定义双向链表结构

pub struct DoublyLinkedList {    head: Option<Rc<RefCell<Node>>>,    tail: Option<Rc<RefCell<Node>>>,}

链表只需维护头（head）和尾（tail）指针。

步骤三：实现基本方法

我们先实现构造函数和在尾部插入节点的方法：

impl DoublyLinkedList {    pub fn new() -> Self {        DoublyLinkedList {            head: None,            tail: None,        }    }    pub fn push_back(&mut self, data: i32) {        let new_node = Rc::new(RefCell::new(Node {            data,            next: None,            prev: None,        }));        match self.tail.take() {            Some(old_tail) => {                // 将旧尾部的 next 指向新节点                old_tail.borrow_mut().next = Some(Rc::clone(&new_node));                // 新节点的 prev 指向旧尾部                new_node.borrow_mut().prev = Some(old_tail);                // 更新 tail                self.tail = Some(new_node);            }            None => {                // 链表为空                self.head = Some(Rc::clone(&new_node));                self.tail = Some(new_node);            }        }    }}

注意：take() 会将 self.tail 设置为 None，避免在修改过程中产生多重可变借用。

步骤四：测试你的双向链表

fn main() {    let mut list = DoublyLinkedList::new();    list.push_back(1);    list.push_back(2);    list.push_back(3);    // 手动遍历打印（仅用于演示）    let mut current = list.head.clone();    while let Some(node) = current {        println!("{}", node.borrow().data);        current = node.borrow().next.clone();    }}

这段代码会输出：

123

进阶建议

这个基础实现支持尾部插入。你可以继续扩展功能，例如：
- push_front：头部插入
- pop_back / pop_front：删除尾部或头部节点
- iter：实现迭代器

需要注意的是，由于使用了 Rc，这种实现无法处理循环引用（比如删除中间节点时需小心断开前后连接），否则会造成内存泄漏。对于高性能场景，可考虑使用 unsafe 和原始指针，但这超出了初学者的范围。

总结

通过本 Rust编程教程，你已经学会了如何在 Rust 中安全地实现一个 Rust双向链表。虽然 Rust 的所有权模型带来了一些挑战，但借助 Rc 和 RefCell，我们可以在不牺牲内存安全的前提下构建复杂的 Rust数据结构。希望这篇 Rust链表实现 教程能为你打下坚实的基础！