在计算机科学中，链表是最基础且重要的数据结构之一。双向链表作为链表的一种变体，允许我们从两个方向遍历元素，提供了更灵活的操作能力。然而，在Rust中实现双向链表是一个极具挑战性的任务，因为它涉及到了Rust所有权系统的核心限制。在 Exercism 的 “doubly-linked-list” 练习中，我们将深入探索如何使用不安全Rust来实现一个完整的双向链表，这不仅能帮助我们掌握Rust的高级特性，还能深入理解内存管理和数据结构设计。

什么是双向链表？

双向链表是一种链表数据结构，其中每个节点都包含：

  1. 数据元素
  2. 指向前一个节点的指针
  3. 指向后一个节点的指针

这种结构允许我们：

  • 从任一节点向前或向后遍历
  • 在任意位置高效地插入和删除元素
  • 从两端高效地添加和移除元素

让我们先看看练习提供的结构和函数签名：

// this module adds some functionality based on the required implementations
// here like: `LinkedList::pop_back` or `Clone for LinkedList<T>`
// You are free to use anything in it, but it's mainly for the test framework.
mod pre_implemented;

pub struct LinkedList<T>(std::marker::PhantomData<T>);

pub struct Cursor<'a, T>(std::marker::PhantomData<&'a mut T>);

pub struct Iter<'a, T>(std::marker::PhantomData<&'a T>);

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        unimplemented!()
    }

    // You may be wondering why it's necessary to have is_empty()
    // when it can easily be determined from len().
    // It's good custom to have both because len() can be expensive for some types,
    // whereas is_empty() is almost always cheap.
    // (Also ask yourself whether len() is expensive for LinkedList)
    pub fn is_empty(&self) -> bool {
        unimplemented!()
    }

    pub fn len(&self) -> usize {
        unimplemented!()
    }

    /// Return a cursor positioned on the front element
    pub fn cursor_front(&mut self) -> Cursor<'_, T> {
        unimplemented!()
    }

    /// Return a cursor positioned on the back element
    pub fn cursor_back(&mut self) -> Cursor<'_, T> {
        unimplemented!()
    }

    /// Return an iterator that moves from front to back
    pub fn iter(&self) -> Iter<'_, T> {
        unimplemented!()
    }
}

// the cursor is expected to act as if it is at the position of an element
// and it also has to work with and be able to insert into an empty list.
impl<T> Cursor<'_, T> {
    /// Take a mutable reference to the current element
    pub fn peek_mut(&mut self) -> Option<&mut T> {
        unimplemented!()
    }

    /// Move one position forward (towards the back) and
    /// return a reference to the new position
    #[allow(clippy::should_implement_trait)]
    pub fn next(&mut self) -> Option<&mut T> {
        unimplemented!()
    }

    /// Move one position backward (towards the front) and
    /// return a reference to the new position
    pub fn prev(&mut self) -> Option<&mut T> {
        unimplemented!()
    }

    /// Remove and return the element at the current position and move the cursor
    /// to the neighboring element that's closest to the back. This can be
    /// either the next or previous position.
    pub fn take(&mut self) -> Option<T> {
        unimplemented!()
    }

    pub fn insert_after(&mut self, _element: T) {
        unimplemented!()
    }

    pub fn insert_before(&mut self, _element: T) {
        unimplemented!()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        unimplemented!()
    }
}

这个练习要求我们实现一个完整的双向链表，包括基本操作、游标操作和迭代器。

设计分析

1. 核心挑战

在Rust中实现双向链表的主要挑战是所有权和借用检查：

  • 每个节点需要引用前一个和后一个节点
  • 这形成了循环引用，Rust的所有权系统不允许这样做
  • 必须使用Rc<RefCell<T>>或不安全代码来解决

2. 解决方案选择

我们可以选择以下几种方式：

  1. 使用Rc<RefCell<T>>实现安全版本（有运行时开销）
  2. 使用不安全代码实现高性能版本（无运行时开销）
  3. 使用原始指针实现

在本练习中，我们将使用不安全代码实现。

完整实现

1. 基础结构定义

use std::ptr::NonNull;
use std::marker::PhantomData;

// 节点结构
struct Node<T> {
    value: T,
    prev: Option<NonNull<Node<T>>>,
    next: Option<NonNull<Node<T>>>,
}

// 链表结构
pub struct LinkedList<T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<Box<Node<T>>>,
}

// 游标结构
pub struct Cursor<'a, T> {
    list: &'a mut LinkedList<T>,
    current: Option<NonNull<Node<T>>>,
}

// 迭代器结构
pub struct Iter<'a, T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<&'a Node<T>>,
}

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

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList {
            front: None,
            back: None,
            len: 0,
            _marker: PhantomData,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn cursor_front(&mut self) -> Cursor<'_, T> {
        Cursor {
            current: self.front,
            list: self,
        }
    }

    pub fn cursor_back(&mut self) -> Cursor<'_, T> {
        Cursor {
            current: self.back,
            list: self,
        }
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            front: self.front,
            back: self.back,
            len: self.len,
            _marker: PhantomData,
        }
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while let Some(node) = self.front {
            unsafe {
                let node = Box::from_raw(node.as_ptr());
                self.front = node.next;
            }
        }
    }
}

2. 游标实现

impl<T> Cursor<'_, T> {
    pub fn peek_mut(&mut self) -> Option<&mut T> {
        unsafe {
            self.current.map(|node| &mut (*node.as_ptr()).value)
        }
    }

    #[allow(clippy::should_implement_trait)]
    pub fn next(&mut self) -> Option<&mut T> {
        unsafe {
            match self.current {
                None => {
                    self.current = self.list.front;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
                Some(current) => {
                    self.current = (*current.as_ptr()).next;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
            }
        }
    }

    pub fn prev(&mut self) -> Option<&mut T> {
        unsafe {
            match self.current {
                None => {
                    self.current = self.list.back;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
                Some(current) => {
                    self.current = (*current.as_ptr()).prev;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
            }
        }
    }

    pub fn take(&mut self) -> Option<T> {
        unsafe {
            let node = self.current?;
            let node_ref = &mut *node.as_ptr();
            
            // 更新前一个节点的next指针
            match node_ref.prev {
                None => self.list.front = node_ref.next,
                Some(mut prev) => (*prev.as_ptr()).next = node_ref.next,
            }
            
            // 更新后一个节点的prev指针
            match node_ref.next {
                None => self.list.back = node_ref.prev,
                Some(mut next) => (*next.as_ptr()).prev = node_ref.prev,
            }
            
            self.current = node_ref.next.or(node_ref.prev);
            
            self.list.len -= 1;
            
            let boxed_node = Box::from_raw(node.as_ptr());
            Some(boxed_node.value)
        }
    }

    pub fn insert_after(&mut self, element: T) {
        unsafe {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(element))));
            
            match self.current {
                None => {
                    // 在空列表中插入
                    self.list.front = Some(new_node);
                    self.list.back = Some(new_node);
                }
                Some(current) => {
                    let current_ref = &mut *current.as_ptr();
                    let next = current_ref.next;
                    
                    // 设置新节点的链接
                    (*new_node.as_ptr()).prev = Some(current);
                    (*new_node.as_ptr()).next = next;
                    
                    // 更新当前节点的链接
                    current_ref.next = Some(new_node);
                    
                    // 更新下一个节点的链接
                    if let Some(mut next_node) = next {
                        (*next_node.as_ptr()).prev = Some(new_node);
                    } else {
                        // 如果当前节点是最后一个节点，更新back指针
                        self.list.back = Some(new_node);
                    }
                }
            }
            
            self.list.len += 1;
        }
    }

    pub fn insert_before(&mut self, element: T) {
        unsafe {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(element))));
            
            match self.current {
                None => {
                    // 在空列表中插入
                    self.list.front = Some(new_node);
                    self.list.back = Some(new_node);
                }
                Some(current) => {
                    let current_ref = &mut *current.as_ptr();
                    let prev = current_ref.prev;
                    
                    // 设置新节点的链接
                    (*new_node.as_ptr()).prev = prev;
                    (*new_node.as_ptr()).next = Some(current);
                    
                    // 更新当前节点的链接
                    current_ref.prev = Some(new_node);
                    
                    // 更新前一个节点的链接
                    if let Some(mut prev_node) = prev {
                        (*prev_node.as_ptr()).next = Some(new_node);
                    } else {
                        // 如果当前节点是第一个节点，更新front指针
                        self.list.front = Some(new_node);
                    }
                }
            }
            
            self.list.len += 1;
        }
    }
}

3. 迭代器实现

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;
        }
        
        unsafe {
            let node = self.front?;
            let node_ref = &*node.as_ptr();
            self.front = node_ref.next;
            self.len -= 1;
            Some(&node_ref.value)
        }
    }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        if self.len == 0 {
            return None;
        }
        
        unsafe {
            let node = self.back?;
            let node_ref = &*node.as_ptr();
            self.back = node_ref.prev;
            self.len -= 1;
            Some(&node_ref.value)
        }
    }
}

测试用例分析

通过查看测试用例，我们可以更好地理解需求：

#[test]
fn basics_empty_list() {
    let list: LinkedList<i32> = LinkedList::new();
    assert_eq!(list.len(), 0);
    assert!(list.is_empty());
}

空链表应该正确报告长度和状态。

#[test]
fn basics_single_element_back() {
    let mut list: LinkedList<i32> = LinkedList::new();
    list.push_back(5);

    assert_eq!(list.len(), 1);
    assert!(!list.is_empty());

    assert_eq!(list.pop_back(), Some(5));

    assert_eq!(list.len(), 0);
    assert!(list.is_empty());
}

链表应该支持在尾部添加和移除元素。

#[test]
fn cursor_insert_before_on_empty_list() {
    let mut list = LinkedList::new();
    list.cursor_front().insert_before(0);
    assert_eq!(Some(0), list.pop_front());
}

游标应该能在空列表中插入元素。

#[test]
fn cursor_next_and_peek() {
    let mut list = (0..10).collect::<LinkedList<_>>();
    let mut cursor = list.cursor_front();

    assert_eq!(cursor.peek_mut(), Some(&mut 0));

    for n in 1..10 {
        let next = cursor.next().cloned();
        assert_eq!(next, Some(n));
        assert_eq!(next, cursor.peek_mut().cloned());
    }
}

游标应该能正确遍历链表元素。

#[test]
fn drop_no_leak_when_removing_single_element() {
    let mut list = (0..10).collect::<LinkedList<_>>();

    let mut cursor = list.cursor_front();
    assert!(cursor.seek_forward(4));

    let allocated_before = ALLOCATED.load(SeqCst);
    cursor.take();
    let allocated_after = ALLOCATED.load(SeqCst);

    assert!(allocated_before > allocated_after);
}

链表应该正确释放内存，不发生内存泄漏。

性能优化版本

考虑性能的优化实现：

use std::ptr::NonNull;
use std::marker::PhantomData;

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

pub struct LinkedList<T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<Box<Node<T>>>,
}

pub struct Cursor<'a, T> {
    list: &'a mut LinkedList<T>,
    current: Option<NonNull<Node<T>>>,
}

pub struct Iter<'a, T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<&'a Node<T>>,
}

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

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList {
            front: None,
            back: None,
            len: 0,
            _marker: PhantomData,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn cursor_front(&mut self) -> Cursor<'_, T> {
        Cursor {
            current: self.front,
            list: self,
        }
    }

    pub fn cursor_back(&mut self) -> Cursor<'_, T> {
        Cursor {
            current: self.back,
            list: self,
        }
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            front: self.front,
            back: self.back,
            len: self.len,
            _marker: PhantomData,
        }
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while let Some(node) = self.front {
            unsafe {
                let node = Box::from_raw(node.as_ptr());
                self.front = node.next;
            }
        }
    }
}

impl<T> Cursor<'_, T> {
    pub fn peek_mut(&mut self) -> Option<&mut T> {
        unsafe {
            self.current.map(|node| {
                &mut (*node.as_ptr()).value
            })
        }
    }

    #[allow(clippy::should_implement_trait)]
    pub fn next(&mut self) -> Option<&mut T> {
        unsafe {
            match self.current {
                None => {
                    self.current = self.list.front;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
                Some(current) => {
                    self.current = (*current.as_ptr()).next;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
            }
        }
    }

    pub fn prev(&mut self) -> Option<&mut T> {
        unsafe {
            match self.current {
                None => {
                    self.current = self.list.back;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
                Some(current) => {
                    self.current = (*current.as_ptr()).prev;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
            }
        }
    }

    pub fn take(&mut self) -> Option<T> {
        unsafe {
            let node = self.current?;
            let node_ref = &mut *node.as_ptr();
            
            match node_ref.prev {
                None => self.list.front = node_ref.next,
                Some(mut prev) => (*prev.as_ptr()).next = node_ref.next,
            }
            
            match node_ref.next {
                None => self.list.back = node_ref.prev,
                Some(mut next) => (*next.as_ptr()).prev = node_ref.prev,
            }
            
            self.current = node_ref.next.or(node_ref.prev);
            
            self.list.len -= 1;
            
            let boxed_node = Box::from_raw(node.as_ptr());
            Some(boxed_node.value)
        }
    }

    pub fn insert_after(&mut self, element: T) {
        unsafe {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(element))));
            
            match self.current {
                None => {
                    self.list.front = Some(new_node);
                    self.list.back = Some(new_node);
                }
                Some(current) => {
                    let current_ref = &mut *current.as_ptr();
                    let next = current_ref.next;
                    
                    (*new_node.as_ptr()).prev = Some(current);
                    (*new_node.as_ptr()).next = next;
                    
                    current_ref.next = Some(new_node);
                    
                    if let Some(mut next_node) = next {
                        (*next_node.as_ptr()).prev = Some(new_node);
                    } else {
                        self.list.back = Some(new_node);
                    }
                }
            }
            
            self.list.len += 1;
        }
    }

    pub fn insert_before(&mut self, element: T) {
        unsafe {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(element))));
            
            match self.current {
                None => {
                    self.list.front = Some(new_node);
                    self.list.back = Some(new_node);
                }
                Some(current) => {
                    let current_ref = &mut *current.as_ptr();
                    let prev = current_ref.prev;
                    
                    (*new_node.as_ptr()).prev = prev;
                    (*new_node.as_ptr()).next = Some(current);
                    
                    current_ref.prev = Some(new_node);
                    
                    if let Some(mut prev_node) = prev {
                        (*prev_node.as_ptr()).next = Some(new_node);
                    } else {
                        self.list.front = Some(new_node);
                    }
                }
            }
            
            self.list.len += 1;
        }
    }
}

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;
        }
        
        unsafe {
            let node = self.front?;
            let node_ref = &*node.as_ptr();
            self.front = node_ref.next;
            self.len -= 1;
            Some(&node_ref.value)
        }
    }
}

unsafe impl<T: Send> Send for LinkedList<T> {}
unsafe impl<T: Sync> Sync for LinkedList<T> {}

unsafe impl<'a, T: Send> Send for Cursor<'a, T> {}
unsafe impl<'a, T: Sync> Sync for Cursor<'a, T> {}

unsafe impl<'a, T: Send> Send for Iter<'a, T> {}
unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}

错误处理和边界情况

考虑更多边界情况的实现：

use std::ptr::NonNull;
use std::marker::PhantomData;

#[derive(Debug, PartialEq)]
pub enum ListError {
    EmptyList,
    InvalidOperation,
}

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

pub struct LinkedList<T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<Box<Node<T>>>,
}

pub struct Cursor<'a, T> {
    list: &'a mut LinkedList<T>,
    current: Option<NonNull<Node<T>>>,
}

pub struct Iter<'a, T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<&'a Node<T>>,
}

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

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList {
            front: None,
            back: None,
            len: 0,
            _marker: PhantomData,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn cursor_front(&mut self) -> Cursor<'_, T> {
        Cursor {
            current: self.front,
            list: self,
        }
    }

    pub fn cursor_back(&mut self) -> Cursor<'_, T> {
        Cursor {
            current: self.back,
            list: self,
        }
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            front: self.front,
            back: self.back,
            len: self.len,
            _marker: PhantomData,
        }
    }
    
    // 安全的前端弹出方法
    pub fn pop_front(&mut self) -> Option<T> {
        let mut cursor = self.cursor_front();
        cursor.take()
    }
    
    // 安全的后端弹出方法
    pub fn pop_back(&mut self) -> Option<T> {
        let mut cursor = self.cursor_back();
        cursor.take()
    }
    
    // 安全的前端插入方法
    pub fn push_front(&mut self, element: T) {
        let mut cursor = self.cursor_front();
        cursor.insert_before(element);
    }
    
    // 安全的后端插入方法
    pub fn push_back(&mut self, element: T) {
        let mut cursor = self.cursor_back();
        cursor.insert_after(element);
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while let Some(node) = self.front {
            unsafe {
                let node = Box::from_raw(node.as_ptr());
                self.front = node.next;
            }
        }
    }
}

impl<T> Cursor<'_, T> {
    pub fn peek_mut(&mut self) -> Option<&mut T> {
        unsafe {
            self.current.map(|node| &mut (*node.as_ptr()).value)
        }
    }

    #[allow(clippy::should_implement_trait)]
    pub fn next(&mut self) -> Option<&mut T> {
        unsafe {
            match self.current {
                None => {
                    self.current = self.list.front;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
                Some(current) => {
                    self.current = (*current.as_ptr()).next;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
            }
        }
    }

    pub fn prev(&mut self) -> Option<&mut T> {
        unsafe {
            match self.current {
                None => {
                    self.current = self.list.back;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
                Some(current) => {
                    self.current = (*current.as_ptr()).prev;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
            }
        }
    }

    pub fn take(&mut self) -> Option<T> {
        // 处理空列表情况
        if self.list.is_empty() {
            return None;
        }
        
        unsafe {
            let node = self.current?;
            let node_ref = &mut *node.as_ptr();
            
            match node_ref.prev {
                None => self.list.front = node_ref.next,
                Some(mut prev) => (*prev.as_ptr()).next = node_ref.next,
            }
            
            match node_ref.next {
                None => self.list.back = node_ref.prev,
                Some(mut next) => (*next.as_ptr()).prev = node_ref.prev,
            }
            
            self.current = node_ref.next.or(node_ref.prev);
            
            self.list.len -= 1;
            
            let boxed_node = Box::from_raw(node.as_ptr());
            Some(boxed_node.value)
        }
    }

    pub fn insert_after(&mut self, element: T) {
        unsafe {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(element))));
            
            match self.current {
                None => {
                    self.list.front = Some(new_node);
                    self.list.back = Some(new_node);
                }
                Some(current) => {
                    let current_ref = &mut *current.as_ptr();
                    let next = current_ref.next;
                    
                    (*new_node.as_ptr()).prev = Some(current);
                    (*new_node.as_ptr()).next = next;
                    
                    current_ref.next = Some(new_node);
                    
                    if let Some(mut next_node) = next {
                        (*next_node.as_ptr()).prev = Some(new_node);
                    } else {
                        self.list.back = Some(new_node);
                    }
                }
            }
            
            self.list.len += 1;
        }
    }

    pub fn insert_before(&mut self, element: T) {
        unsafe {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(element))));
            
            match self.current {
                None => {
                    self.list.front = Some(new_node);
                    self.list.back = Some(new_node);
                }
                Some(current) => {
                    let current_ref = &mut *current.as_ptr();
                    let prev = current_ref.prev;
                    
                    (*new_node.as_ptr()).prev = prev;
                    (*new_node.as_ptr()).next = Some(current);
                    
                    current_ref.prev = Some(new_node);
                    
                    if let Some(mut prev_node) = prev {
                        (*prev_node.as_ptr()).next = Some(new_node);
                    } else {
                        self.list.front = Some(new_node);
                    }
                }
            }
            
            self.list.len += 1;
        }
    }
}

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;
        }
        
        unsafe {
            let node = self.front?;
            let node_ref = &*node.as_ptr();
            self.front = node_ref.next;
            self.len -= 1;
            Some(&node_ref.value)
        }
    }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        if self.len == 0 {
            return None;
        }
        
        unsafe {
            let node = self.back?;
            let node_ref = &*node.as_ptr();
            self.back = node_ref.prev;
            self.len -= 1;
            Some(&node_ref.value)
        }
    }
}

扩展功能

基于基础实现，我们可以添加更多功能：

use std::ptr::NonNull;
use std::marker::PhantomData;

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

pub struct LinkedList<T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<Box<Node<T>>>,
}

pub struct Cursor<'a, T> {
    list: &'a mut LinkedList<T>,
    current: Option<NonNull<Node<T>>>,
}

pub struct Iter<'a, T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<&'a Node<T>>,
}

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

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList {
            front: None,
            back: None,
            len: 0,
            _marker: PhantomData,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn cursor_front(&mut self) -> Cursor<'_, T> {
        Cursor {
            current: self.front,
            list: self,
        }
    }

    pub fn cursor_back(&mut self) -> Cursor<'_, T> {
        Cursor {
            current: self.back,
            list: self,
        }
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            front: self.front,
            back: self.back,
            len: self.len,
            _marker: PhantomData,
        }
    }
    
    // 清空链表
    pub fn clear(&mut self) {
        while self.pop_front().is_some() {}
    }
    
    // 获取前端元素的引用
    pub fn front(&self) -> Option<&T> {
        unsafe {
            self.front.map(|node| &(*node.as_ptr()).value)
        }
    }
    
    // 获取后端元素的引用
    pub fn back(&self) -> Option<&T> {
        unsafe {
            self.back.map(|node| &(*node.as_ptr()).value)
        }
    }
    
    // 将另一个链表的所有元素追加到当前链表尾部
    pub fn append(&mut self, other: &mut LinkedList<T>) {
        match self.back {
            None => {
                // 当前链表为空
                self.front = other.front;
                self.back = other.back;
                self.len = other.len;
            }
            Some(mut back_node) => {
                match other.front {
                    None => {
                        // 其他链表为空，无需操作
                    }
                    Some(mut other_front) => {
                        // 连接两个链表
                        unsafe {
                            (*back_node.as_ptr()).next = Some(other_front);
                            (*other_front.as_ptr()).prev = Some(back_node);
                        }
                        self.back = other.back;
                        self.len += other.len;
                    }
                }
            }
        }
        
        // 清空另一个链表
        other.front = None;
        other.back = None;
        other.len = 0;
    }
    
    // 分割链表，在指定索引处分割
    pub fn split_off(&mut self, at: usize) -> LinkedList<T> {
        if at >= self.len {
            return LinkedList::new();
        }
        
        if at == 0 {
            // 分割点在开头，返回整个链表
            let mut result = LinkedList::new();
            std::mem::swap(self, &mut result);
            return result;
        }
        
        let mut cursor = self.cursor_front();
        for _ in 0..at {
            cursor.next();
        }
        
        // 分割链表
        unsafe {
            let current_node = cursor.current.unwrap();
            let current_ref = &*current_node.as_ptr();
            
            let mut new_list = LinkedList {
                front: Some(current_node),
                back: self.back,
                len: self.len - at,
                _marker: PhantomData,
            };
            
            // 更新原链表
            match current_ref.prev {
                Some(mut prev_node) => {
                    (*prev_node.as_ptr()).next = None;
                    self.back = Some(prev_node);
                }
                None => {
                    // 这种情况不应该发生
                    unreachable!();
                }
            }
            
            // 更新新链表的第一个节点
            (*current_node.as_ptr()).prev = None;
            
            self.len = at;
            new_list
        }
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while let Some(node) = self.front {
            unsafe {
                let node = Box::from_raw(node.as_ptr());
                self.front = node.next;
            }
        }
    }
}

impl<T> Cursor<'_, T> {
    pub fn peek_mut(&mut self) -> Option<&mut T> {
        unsafe {
            self.current.map(|node| &mut (*node.as_ptr()).value)
        }
    }

    #[allow(clippy::should_implement_trait)]
    pub fn next(&mut self) -> Option<&mut T> {
        unsafe {
            match self.current {
                None => {
                    self.current = self.list.front;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
                Some(current) => {
                    self.current = (*current.as_ptr()).next;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
            }
        }
    }

    pub fn prev(&mut self) -> Option<&mut T> {
        unsafe {
            match self.current {
                None => {
                    self.current = self.list.back;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
                Some(current) => {
                    self.current = (*current.as_ptr()).prev;
                    self.current.map(|node| &mut (*node.as_ptr()).value)
                }
            }
        }
    }

    pub fn take(&mut self) -> Option<T> {
        if self.list.is_empty() {
            return None;
        }
        
        unsafe {
            let node = self.current?;
            let node_ref = &mut *node.as_ptr();
            
            match node_ref.prev {
                None => self.list.front = node_ref.next,
                Some(mut prev) => (*prev.as_ptr()).next = node_ref.next,
            }
            
            match node_ref.next {
                None => self.list.back = node_ref.prev,
                Some(mut next) => (*next.as_ptr()).prev = node_ref.prev,
            }
            
            self.current = node_ref.next.or(node_ref.prev);
            
            self.list.len -= 1;
            
            let boxed_node = Box::from_raw(node.as_ptr());
            Some(boxed_node.value)
        }
    }

    pub fn insert_after(&mut self, element: T) {
        unsafe {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(element))));
            
            match self.current {
                None => {
                    self.list.front = Some(new_node);
                    self.list.back = Some(new_node);
                }
                Some(current) => {
                    let current_ref = &mut *current.as_ptr();
                    let next = current_ref.next;
                    
                    (*new_node.as_ptr()).prev = Some(current);
                    (*new_node.as_ptr()).next = next;
                    
                    current_ref.next = Some(new_node);
                    
                    if let Some(mut next_node) = next {
                        (*next_node.as_ptr()).prev = Some(new_node);
                    } else {
                        self.list.back = Some(new_node);
                    }
                }
            }
            
            self.list.len += 1;
        }
    }

    pub fn insert_before(&mut self, element: T) {
        unsafe {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(element))));
            
            match self.current {
                None => {
                    self.list.front = Some(new_node);
                    self.list.back = Some(new_node);
                }
                Some(current) => {
                    let current_ref = &mut *current.as_ptr();
                    let prev = current_ref.prev;
                    
                    (*new_node.as_ptr()).prev = prev;
                    (*new_node.as_ptr()).next = Some(current);
                    
                    current_ref.prev = Some(new_node);
                    
                    if let Some(mut prev_node) = prev {
                        (*prev_node.as_ptr()).next = Some(new_node);
                    } else {
                        self.list.front = Some(new_node);
                    }
                }
            }
            
            self.list.len += 1;
        }
    }
    
    // 将游标移动到链表前端
    pub fn move_to_front(&mut self) {
        self.current = self.list.front;
    }
    
    // 将游标移动到链表后端
    pub fn move_to_back(&mut self) {
        self.current = self.list.back;
    }
}

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;
        }
        
        unsafe {
            let node = self.front?;
            let node_ref = &*node.as_ptr();
            self.front = node_ref.next;
            self.len -= 1;
            Some(&node_ref.value)
        }
    }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        if self.len == 0 {
            return None;
        }
        
        unsafe {
            let node = self.back?;
            let node_ref = &*node.as_ptr();
            self.back = node_ref.prev;
            self.len -= 1;
            Some(&node_ref.value)
        }
    }
}

impl<T> IntoIterator for LinkedList<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter { list: self }
    }
}

pub struct IntoIter<T> {
    list: LinkedList<T>,
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.list.pop_front()
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.list.pop_back()
    }
}

实际应用场景

双向链表在实际开发中有以下应用：

  1. 浏览器历史记录：支持前进和后退功能
  2. 音乐播放器：支持上一首和下一首切换
  3. 文本编辑器：实现撤销/重做功能
  4. LRU缓存：最近最少使用缓存算法
  5. 任务调度：操作系统中的进程调度
  6. 游戏开发：游戏对象管理
  7. 内存管理：操作系统的空闲内存块管理

算法复杂度分析

  1. 时间复杂度：

    • 插入/删除（已知位置）：O(1)
    • 访问元素：O(n)
    • 遍历：O(n)
    • 长度查询：O(1)

  2. 空间复杂度：O(n)

    • 每个元素需要额外的前后指针空间

与其他实现方式的比较

// 使用 Rc<RefCell<T>> 的安全实现
use std::rc::{Rc, Weak};
use std::cell::RefCell;

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

pub struct LinkedListSafe<T> {
    front: Option<Rc<RefCell<NodeSafe<T>>>>,
    back: Option<Weak<RefCell<NodeSafe<T>>>>,
    len: usize,
}

impl<T> LinkedListSafe<T> {
    pub fn new() -> Self {
        LinkedListSafe {
            front: None,
            back: None,
            len: 0,
        }
    }
    
    pub fn push_front(&mut self, value: T) {
        let new_node = Rc::new(RefCell::new(NodeSafe {
            value,
            prev: None,
            next: self.front.clone(),
        }));
        
        match self.front.take() {
            Some(old_front) => {
                old_front.borrow_mut().prev = Some(Rc::downgrade(&new_node));
                self.front = Some(new_node);
            }
            None => {
                self.front = Some(new_node.clone());
                self.back = Some(Rc::downgrade(&new_node));
            }
        }
        
        self.len += 1;
    }
    
    pub fn pop_front(&mut self) -> Option<T> {
        self.front.take().map(|node| {
            let mut node_ref = node.borrow_mut();
            self.front = node_ref.next.take();
            
            match self.front.take() {
                Some(new_front) => {
                    new_front.borrow_mut().prev = None;
                    self.front = Some(new_front);
                }
                None => {
                    self.back = None;
                }
            }
            
            self.len -= 1;
            drop(node_ref);
            Rc::try_unwrap(node).ok().unwrap().into_inner().value
        })
    }
}

// 使用标准库实现
use std::collections::VecDeque;

pub struct LinkedListStd<T> {
    inner: VecDeque<T>,
}

impl<T> LinkedListStd<T> {
    pub fn new() -> Self {
        LinkedListStd {
            inner: VecDeque::new(),
        }
    }
    
    pub fn push_front(&mut self, value: T) {
        self.inner.push_front(value);
    }
    
    pub fn push_back(&mut self, value: T) {
        self.inner.push_back(value);
    }
    
    pub fn pop_front(&mut self) -> Option<T> {
        self.inner.pop_front()
    }
    
    pub fn pop_back(&mut self) -> Option<T> {
        self.inner.pop_back()
    }
}

总结

通过 doubly-linked-list 练习，我们学到了：

  1. 不安全Rust：掌握了unsafe代码的使用和风险控制
  2. 内存管理：理解了手动内存管理的原理和技巧
  3. 数据结构设计：学会了设计复杂的链式数据结构
  4. 所有权系统：深入理解了Rust所有权系统的限制和解决方案
  5. 生命周期管理：熟练处理复杂的数据结构生命周期
  6. 性能优化：了解了零成本抽象和内存布局优化

这些技能在实际开发中非常有用，特别是在实现高性能数据结构、系统编程和需要精细内存控制的场景中。双向链表虽然是一个基础数据结构，但它涉及到了Rust的高级特性和系统编程的核心概念，是学习Rust深入知识的良好起点。

通过这个练习，我们也看到了Rust在系统编程方面的强大能力，以及如何用安全且高效的方式实现复杂的内存操作。这种结合了安全性和性能的语言特性正是Rust的魅力所在。

# rust # 链表 # 安全
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

Yearning+客户端+手工EXPLAIN，NineData社区版能作为替代方案？

avatar AtomGit开源社区
cover

2026 毕业季终极破局：PaperXie 四大核心功能，重构降重 + AIGC 检测双达标新范式

avatar AtomGit开源社区
cover

答辩 PPT 不用熬！PaperXie AI PPT 生成器：把论文变专业 slides，10 分钟搞定毕业关

avatar AtomGit开源社区