---

目录

Rust LinkedList 双向链表深度解析 🔗

一、理论基础与 Rust 特性碰撞

为什么 Rust 的链表这么特殊？

二、双向链表结构深度剖析

2.1 核心数据结构

2.2 双向循环特性

三、实践：构建自己的双向链表迭代器

四、性能与权衡分析

五、深层思考：所有权与生命周期

---

Rust LinkedList 双向链表深度解析 🔗

一、理论基础与 Rust 特性碰撞

Rust 的 LinkedList<T> 实现了一个双向循环链表，这个设计相比单向链表更复杂，也更能体现 Rust 所有权系统的精妙之处。传统语言中链表很容易实现，但 Rust 因为严格的所有权规则，让链表变成了一个"优雅的挑战"。

为什么 Rust 的链表这么特殊？

在 C/C++ 中，你可以随意使用原始指针，但 Rust 不允许。LinkedList 内部使用了 NonNull<Node<T>> 这样的原始指针包装，绕过了 Rust 的借用检查器。这是 Rust 设计的妥协——为了性能和灵活性，允许 unsafe 代码存在，但将其隔离在标准库内部。

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

这个设计让我理解到：Rust 不是绝对禁止不安全操作，而是明确了边界。 LinkedList 的实现正是这种哲学的体现。

---

二、双向链表结构深度剖析

2.1 核心数据结构

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
    tail: *mut Node<T>,
    len: usize,
    _marker: PhantomData<Box<Node<T>>>,
}

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

关键细节解读：

• head 使用 Option<Box<T>>：拥有第一个节点的所有权

• tail 使用原始指针：避免多重所有权冲突

• _marker 是 PhantomData：告诉编译器我们"逻辑上"拥有 Box<Node<T>>，用于正确的 drop 行为

这个设计是权衡艺术——既要满足 Rust 所有权规则，又要实现高效的双向遍历。

2.2 双向循环特性

不同于许多实现，Rust 标准库的 LinkedList 支持循环访问：

impl<T> LinkedList<T> {
    pub fn push_back(&mut self, elt: T) {
        // 创建新节点
        let node = Box::new(Node {
            prev: null_mut(),
            next: null_mut(),
            element: elt,
        });
        
        let node_ptr = Box::into_raw(node);
        
        match self.tail.as_mut() {
            None => {
                // 链表为空，新节点既是head又是tail
                self.head = Some(unsafe { Box::from_raw(node_ptr) });
                self.tail = node_ptr;
            }
            Some(tail) => {
                // 连接到末尾
                unsafe {
                    (*tail).next = node_ptr;
                    (*node_ptr).prev = tail;
                }
                self.tail = node_ptr;
            }
        }
        self.len += 1;
    }
}

---

三、实践：构建自己的双向链表迭代器

这是深度实践的关键——实现一个安全的迭代器，体现 Rust 对内存安全的承诺：

pub struct Iter<'a, T> {
    head: Option<&'a Node<T>>,
    tail: Option<&'a Node<T>>,
    len: usize,
    _marker: PhantomData<&'a T>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    
    fn next(&mut self) -> Option<&'a T> {
        if self.len == 0 {
            return None;
        }
        
        self.head.take().map(|node| {
            self.len -= 1;
            // 从head指针推进到下一个节点
            self.head = unsafe {
                node.next.as_ref().map(|n| &*n)
            };
            &node.element
        })
    }
    
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        if self.len == 0 {
            return None;
        }
        
        self.tail.take().map(|node| {
            self.len -= 1;
            self.tail = unsafe {
                node.prev.as_ref().map(|n| &*n)
            };
            &node.element
        })
    }
}

专业思考：这个迭代器为什么使用 DoubleEndedIterator？因为双向链表的核心价值就在于从两端高效访问。实现这个 trait 让用户可以用 .rev() 反向遍历，这是函数式编程范式与链表结构的完美结合。

---

四、性能与权衡分析

操作	时间复杂度	空间复杂度	备注
push_front/push_back	O(1)	O(n)	摊销常数时间
pop_front/pop_back	O(1)	-	真正的常数时间
随机访问	O(n)	-	是的，很慢
内存碎片化	-	中等	每个节点独立分配

为什么 Rust 用户应该谨慎：

• LinkedList 在现代 CPU 缓存面前很无力（内存局部性差）

• 大多数场景 VecDeque 会更快

• LinkedList 适用场景：频繁的头尾插删 + 需要中间迭代

---

五、深层思考：所有权与生命周期

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        // 必须手动清理所有节点
        while self.pop_front().is_some() {}
    }
}

这行代码揭示了 Rust 的设计哲学：即使使用 unsafe 代码，也必须保证 RAII 原则的遵循。LinkedList 的析构函数确保所有节点被正确释放，这是 safe API 的保证。

---

本文结束，谢谢你的观看。