Rust中的裸指针-实现一个List

2025-12-16

字数统计: 460字 | 阅读时长: 2分

在Rust中也可以像C语言一样使用指针，叫做裸指针，本次实验使用裸指针实现一个List链表。

首先定义Node结构体，这是一个单链表的节点：

use std::alloc::{alloc, dealloc, Layout};
use std::marker::PhantomData;
use std::ptr::null_mut;

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

impl<T> Node<T> {
    fn new_ptr(value: T) -> *mut Self {
        unsafe {
            let ptr = alloc(Layout::new::<Self>()) as *mut Self;
            (*ptr).value = value;
            (*ptr).next = null_mut();
            ptr
        }
    }
}

接下来定义List结构体：

struct List<T> {
    head: *mut Node<T>,
    tail: *mut Node<T>,
    count: usize,
}

impl<T> List<T> {
    fn new() -> Self {
        Self {
            head: null_mut(),
            tail: null_mut(),
            count: 0,
        }
    }

    fn push(&mut self, value: T) {
        unsafe {
            let new_node = Node::new_ptr(value);
            if self.tail.is_null() || self.head.is_null() {
                self.head = new_node;
                self.tail = new_node;
            } else {
                (*self.tail).next = new_node;
                self.tail = new_node;
            }
            self.count += 1;
        }
    }

    fn iter(&'_ self) -> ListIterator<'_, T> {
        ListIterator {
            list: PhantomData,
            ptr: self.head,
        }
    }
}

手动申请的内存需要手动释放：

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut ptr = self.head;
        while !ptr.is_null() {
            unsafe {
                let next = (*ptr).next;
                dealloc(ptr as *mut u8, Layout::new::<Self>());
                ptr = next;
            }
        }
    }
}

实现List的迭代器，以引用的方式返回数据：

struct ListIterator<'a, T> {
    list: PhantomData<&'a List<T>>,
    ptr: *mut Node<T>,
}

impl<'a, T> Iterator for ListIterator<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        if self.ptr.is_null() {
            None
        } else {
            unsafe {
                let value = Some(&(*self.ptr).value);
                self.ptr = (*self.ptr).next;
                value
            }
        }
    }
}

编写测试代码：

fn main() {
    let mut list = List::new();
    for i in 0..10 {
        list.push(i);
    }

    for i in list.iter() {
        println!("{}", i);
    }
}

测试一下，结果如下：

本文作者： killf
本文链接： https://www.killf.info/编程语言/Rust/Rust中的裸指针-实现一个List/
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！