Циклический связанный список на Rust

Question

Хочу написать циклический односвязный список. Но проблема в том что при создании первый элемент должен ссылаться на сам себя. я вроде бы слышал что для этого нужно обернуть в Pin. но это не помогло. как это можно реализовать?

struct node {
    data:i32,
    next: Option<Pin<Box<node>>>
}

struct List {
    frist: Box<node>,
    last: Box<node>
}

fn create_list(data:i32) {
    let mut node = Box::new(node{ data, next: None });
    let pin = Pin::new(node);
    node.next = Some(pin);
}

Ошибка:

error[E0382]: assign to part of moved value: `*node`

     let mut node = Box::new(node { data, next: None });
         -------- move occurs because `node` has type `std::boxed::Box<node>`, which does not implement the `Copy` trait
     let pin = Pin::new(node);
                        ---- value moved here
     node.next = Some(pin);
     ^^^^^^^^^ value partially assigned here after move

Answer 1

Попробуйте клонировать или передать по ссылке.


use std::pin::Pin;

#[derive(Clone)]
struct Node {
    data:i32,
    next:Option<Pin<Box<Node>>>
}
#[derive(Clone)]
struct List {
    frist: Box<Node>,
    last: Box<Node>
}

fn create_list(data:i32) {
    let mut node = Box::new(Node{data,next: None});
    let a = node.clone();
    node.next = Some(Pin::new(a));
}

fn main () {

create_list(4);

}

Answer 2

Проблема всех связных списков в Rust, кроме простейшего односвязного - в том, что отношение владения между элементами неопределено. Элементами владеет список целиком, но у него нет указателя на каждый элемент списка - потому стандартный контейнер для элемента и не выбрать.

Контейнером должен стать список целиком, и единственный нормальный способ такой контейнер сделать - это unsafe и сырые указатели:

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

struct List<T> {
    first: *mut Node<T>
}

fn create_list<T>(data: T) -> List<T> {
    unsafe {
        let node = Node { data, next: std::ptr::null_mut() };
        let node_ptr = Box::into_raw(Box::new(node));
        (*node_ptr).next = node_ptr;
        List { first: node_ptr }
    }
}

И не забудьте написать деструктор для списка:

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        unsafe {
            let head = self.first;
            if head.is_null() { return; }

            let mut node = head;
            loop {
                let next = (*node).next;
                Box::from_raw(node);
                node = next;
                if node == head { break; }
            }
        }
    }
}

Код я не запускал, так что прошу относиться к нему как к черновику, и исправить ошибки если таковые будут замечены.

БЛОГ НА HUSL

Циклический связанный список на Rust

Ответы (2 шт):