Unsafe Rust实现的循环双向链表弹出异常问题排查

问题现象 #

实现带哑节点的循环双向链表后，执行push_front(1)→push_front(2)→push_front(3)，调用pop_front时每次都返回3，而非预期的3、2、1序列。

核心问题原因 #

1. 悬垂指针问题：push_front方法中创建的new_node是栈上局部变量，函数执行完毕后栈帧销毁，new_node的内存被回收。此时链表中存储的&mut new_node指针变成悬垂指针，后续对这些指针的读写操作都是未定义行为，导致测试结果异常。
2. 不安全的初始化：DList::new中使用mem::zeroed()初始化哑节点的data，对于不允许零初始化的类型（如非Copy、非Default类型）会直接触发未定义行为。

修复方案 #

1. 用Box<DNode<T>>在堆上分配节点，确保节点生命周期不受函数栈帧限制；
2. 哑节点的data改用MaybeUninit<T>延迟初始化，避免零初始化的安全风险；
3. 修正链表指针的操作逻辑，确保指针指向堆上的有效节点；
4. 添加Drop trait实现，手动销毁所有节点防止内存泄漏。

修复后的代码 #

链表实现 #

use std::{mem::MaybeUninit, ptr};

pub struct DList<T> {
    dummy: *mut DNode<T>,
}

struct DNode<T> {
    data: T,
    next: *mut DNode<T>,
    prev: *mut DNode<T>,
}

impl<T> DList<T> {
    pub fn new() -> Self {
        // 堆上创建哑节点，用MaybeUninit避免非法零初始化
        let dummy_box = Box::new(DNode {
            data: unsafe { MaybeUninit::zeroed().assume_init() },
            next: ptr::null_mut(),
            prev: ptr::null_mut(),
        });
        let dummy_ptr = Box::into_raw(dummy_box);
        unsafe {
            // 初始化哑节点前后指针指向自身，形成循环
            (*dummy_ptr).next = dummy_ptr;
            (*dummy_ptr).prev = dummy_ptr;
        }
        DList { dummy: dummy_ptr }
    }

    pub fn push_front(&mut self, data: T) {
        // 堆上分配新节点
        let new_node_box = Box::new(DNode {
            data,
            next: ptr::null_mut(),
            prev: ptr::null_mut(),
        });
        let new_node = Box::into_raw(new_node_box);

        unsafe {
            let old_front = (*self.dummy).next;
            // 更新新节点的前后指针
            (*new_node).prev = self.dummy;
            (*new_node).next = old_front;
            // 更新哑节点和旧头节点的指针
            (*self.dummy).next = new_node;
            (*old_front).prev = new_node;
        }
    }

    pub fn pop_front(&mut self) -> T {
        unsafe {
            let front = (*self.dummy).next;
            // 非空判断，避免空链表弹出的未定义行为
            assert_ne!(front, self.dummy, "Cannot pop from empty list");
            
            let new_front = (*front).next;
            // 更新哑节点和新头节点的指针
            (*self.dummy).next = new_front;
            (*new_front).prev = self.dummy;
            
            // 将指针转回Box，获取所有权后取出数据
            let front_box = Box::from_raw(front);
            front_box.data
        }
    }
}

// 实现Drop trait，手动销毁所有节点防止内存泄漏
impl<T> Drop for DList<T> {
    fn drop(&mut self) {
        unsafe {
            let mut current = (*self.dummy).next;
            while current != self.dummy {
                let next = (*current).next;
                Box::from_raw(current);
                current = next;
            }
            // 销毁哑节点
            Box::from_raw(self.dummy);
        }
    }
}

测试代码 #

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_push_front_pop_front() {
        let mut dlist = DList::new();
        dlist.push_front(1);
        dlist.push_front(2);
        dlist.push_front(3);
        assert_eq!(dlist.pop_front(), 3);
        assert_eq!(dlist.pop_front(), 2);
        assert_eq!(dlist.pop_front(), 1);
    }
}

额外说明 #

• 修复后的代码通过Box管理堆内存，彻底解决了悬垂指针问题；
• MaybeUninit的使用避免了非法零初始化的安全风险（若不需要哑节点存储数据，也可改用枚举类型区分哑节点与普通节点）；
• Drop trait的实现确保所有节点都会被正确销毁，无内存泄漏；
• pop_front中的非空判断增强了代码健壮性。

内容的提问来源于stack exchange，提问作者Noah