Circular linked list on Rust

Question

Circular linked list on Rust

I want to write a cyclic singly linked list. But the problem is that when creating the first element, it must refer to itself. I seem to have heard that to do this, you need to wrap in Pin. but it didn't help. how can this be implemented?

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);
}

Mistake:

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

2

rust

Author: Ainar-G, 2020-04-22

Source

2 answers

score 0 · Answer 1

The problem with all connected lists in Rust, except for the simplest singly connected one , is that the ownership relationship between the elements is undefined. The entire list owns the elements, but it does not have a pointer to each element of the list - therefore, the standard container for the element is not selected.

The container should be the entire list, and the only normal way to make such a container is unsafe and raw pointers:

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 }
    }
}

And don't forget to write a destructor for the list:

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; }
            }
        }
    }
}

I did not run the code, so please treat it as a draft, and correct the errors if any are noticed.

score -2 · Answer 2

Try cloning it or passing it by link.


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);

}