Rust新手求助：如何实现双向链表？

在Rust里，编译器的借用检查器确实会阻止传统双向链表的实现方式（同时持有多个可变引用），但有几种安全的替代方案，按初学者友好程度排序：

1. 基于索引的链表（最安全易上手） #

放弃指针，用容器存储节点，通过索引关联前后节点。这种方式完全绕开了引用冲突问题，实现简单：

struct Node<T> {
    value: T,
    prev: Option<usize>,
    next: Option<usize>,
}

struct LinkedList<T> {
    nodes: Vec<Node<T>>,
    head: Option<usize>,
    tail: Option<usize>,
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        LinkedList {
            nodes: Vec::new(),
            head: None,
            tail: None,
        }
    }

    fn push_back(&mut self, value: T) {
        let new_idx = self.nodes.len();
        let new_node = Node {
            value,
            prev: self.tail,
            next: None,
        };
        self.nodes.push(new_node);

        if let Some(tail_idx) = self.tail {
            self.nodes[tail_idx].next = Some(new_idx);
        } else {
            self.head = Some(new_idx);
        }
        self.tail = Some(new_idx);
    }

    // 示例：遍历链表
    fn iter(&self) -> impl Iterator<Item = &T> {
        let mut current_idx = self.head;
        std::iter::from_fn(move || {
            current_idx.map(|idx| {
                let node = &self.nodes[idx];
                current_idx = node.next;
                &node.value
            })
        })
    }
}

这种方式的优点是完全安全，不需要处理引用计数或unsafe代码；缺点是删除中间节点时会留下空槽（可以用Vec的swap_remove优化，但会改变节点索引）。

2. 结合Rc和RefCell的安全链表 #

用Rc共享节点所有权，RefCell提供内部可变性，在运行时检查借用规则，模拟传统双向链表的结构：

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

struct Node<T> {
    value: T,
    prev: RefCell<Option<Rc<Node<T>>>>,
    next: RefCell<Option<Rc<Node<T>>>>,
}

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

    // 链接两个节点
    fn link(&self, next: &Rc<Node<T>>) {
        *self.next.borrow_mut() = Some(Rc::clone(next));
        *next.prev.borrow_mut() = Some(Rc::clone(self));
    }
}

struct LinkedList<T> {
    head: Option<Rc<Node<T>>>,
    tail: Option<Rc<Node<T>>>,
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        LinkedList { head: None, tail: None }
    }

    fn push_back(&mut self, value: T) {
        let new_node = Node::new(value);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.link(&new_node);
                self.tail = Some(new_node);
            }
            None => {
                self.head = Some(Rc::clone(&new_node));
                self.tail = Some(new_node);
            }
        }
    }
}

这种方式更贴近传统双向链表的设计，但Rc会带来一定的运行时开销，且RefCell的借用违规会直接触发panic，需要注意代码逻辑的正确性。

3. Unsafe裸指针实现（不推荐初学者） #

如果需要极致性能，且能自行保证内存安全，可以用UnsafeCell配合裸指针手动管理节点：

use std::cell::UnsafeCell;

struct Node<T> {
    value: T,
    prev: UnsafeCell<*mut Node<T>>,
    next: UnsafeCell<*mut Node<T>>,
}

impl<T> Node<T> {
    fn new(value: T) -> *mut Self {
        Box::into_raw(Box::new(Node {
            value,
            prev: UnsafeCell::new(std::ptr::null_mut()),
            next: UnsafeCell::new(std::ptr::null_mut()),
        }))
    }
}

struct LinkedList<T> {
    head: *mut Node<T>,
    tail: *mut Node<T>,
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        LinkedList {
            head: std::ptr::null_mut(),
            tail: std::ptr::null_mut(),
        }
    }

    fn push_back(&mut self, value: T) {
        let new_node = Node::new(value);
        if !self.tail.is_null() {
            unsafe {
                (*self.tail).next = UnsafeCell::new(new_node);
                (*new_node).prev = UnsafeCell::new(self.tail);
            }
        } else {
            self.head = new_node;
        }
        self.tail = new_node;
    }
}

// 必须手动实现Drop避免内存泄漏
impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        let mut current = self.head;
        while !current.is_null() {
            let next = unsafe { (*current).next.get() };
            unsafe { Box::from_raw(current); }
            current = next;
        }
    }
}

这种方式完全绕开了Rust的安全检查，所有内存安全问题（比如悬垂指针、双重释放）都需要开发者自行负责，初学者极易写出bug，仅推荐有经验的开发者使用。

内容的提问来源于stack exchange，提问作者Matthias F.