How to construct linked list from vector with Arc<Mutex> in rust

Question

The task is simple: construct a linked list from a vector. The link list shall support multi-threading.

My first attempt is to iterate through the vector, set a pointer to the end of the linked list, create new node in each step and link as appropriate. Yet rust's borrow checker has made it very troublesome.

Here is the code:

// dummy struct for simplicity
struct LinkedList {
    next: Option<Arc<Mutex<LinkedList>>>,
    val: u32,
}

fn main() {
    let vec_int: Vec<u32> = vec![1, 2, 3, 4, 5];

    let normal_res = LinkedList { next: None, val: 0 };
    // head pointer
    let mut head = Arc::new(Mutex::new(normal_res));
    for (i, val) in vec_int.iter().enumerate() {
        // the first one is different: fill in the created LinkedList
        if i == 0 {
            (*head).lock().unwrap().val = *val;
            continue;
        }

        // create new LinkedList and link it
        let next = LinkedList {
            next: None,
            val: *val,
        };
        (*head).lock().unwrap().next = Some(Arc::new(Mutex::new(next)));

        // make head into the pointer to the proper child, but it will not work

        // error: use of moved value
        head = Arc::new(Mutex::new(next));

        // error: can not assign to head because it is borrowed
        head = (*head).lock().unwrap().next.as_ref().unwrap().clone();
        // I have tried many more ways of manipulating the pointers, all failed
    }
}

My second attempt works, but is not optimal as it has to inverse the vector.

fn main(){
    let mut reversed = Arc::new(Mutex::new(LinkedList { next: None, val: 0 }));
    for (i, val) in vec_int.iter().rev().enumerate() {
        if i == 0 {
            (*reversed).lock().unwrap().val = *val;
            continue;
        }
        // assign the next
        reversed = Arc::new(Mutex::new(LinkedList {
            next: Some(reversed.clone()),
            val: *val,
        }));
    }
}

I found several answers and tutorials for the same topic, but their method does not seem to apply to Arc<Mutex>.

Answer 1 :Cannot assign to variable because it is borrowed

Answer 2 : create ListNode from Vec with ref to first Node

Any help is greatly appreciated.

Arc<Mutex<_>> is typically used when sharing things across threads. I don't see any threading mentioned here, so this is expensive and unnecessary. Mutability challenges here are better addressed using other tools (RefCell?) — Sergio Tulentsev
– Sergio Tulentsev, Commented May 20, 2024 at 11:01
My application uses multithreading, so Mutex is the only option as it appears to me. — YuhaoHanHarry
– YuhaoHanHarry, Commented May 20, 2024 at 13:37
Recommended reading: Learn Rust With Entirely Too Many Linked Lists. Building a linked list is not as simple as assumed here. — E_net4
– E_net4, Commented May 20, 2024 at 14:13
Besides linked lists not being simple, they are also bad for almost any kind of task. So reconsider your task. — Chayim Friedman
– Chayim Friedman, Commented May 25, 2024 at 18:44
Why is it "not optimal"? rev() does not reverse the vector in memory, it only walks it backwards. This is the most optimal you can get. — Chayim Friedman
– Chayim Friedman, Commented May 25, 2024 at 18:46

Alex Xia · Accepted Answer · 2024-05-27 09:50:16Z

As you are using Arc, most ownership problems can be circumvented by using Arc::clone(&).

Here is the code

fn main() {
    let vec_int: Vec<u32> = vec![1, 2, 3, 4, 5];

    let normal_res = LinkedList { next: None, val: 0 };
    // head pointer
    let mut head = Arc::new(Mutex::new(normal_res));
    let normal_res = Arc::clone(&head);
    for (i, val) in vec_int.iter().enumerate() {
        // the first one is different: fill in the created LinkedList
        if i == 0 {
            (*head).lock().unwrap().val = *val;
            continue;
        }

        // create new LinkedList and link it
        let next = LinkedList {
            next: None,
            val: *val,
        };
        // use clone to circumvent ownership problem
        let next = Arc::new(Mutex::new(next));
        (*head).lock().unwrap().next = Some(Arc::clone(&next));

        head = next;
    }
}

If you want to loop through the linked list, this is how:

    let mut head = normal_res;
    loop {
        let dummy_head = Arc::clone(&head);
        let dummy_head = dummy_head.lock().unwrap();
        println!("val: {}", dummy_head.val);
        if dummy_head.next.is_none(){
            break;
        }
        head = Arc::clone(&dummy_head.next.as_ref().unwrap());
    }

Collectives™ on Stack Overflow

How to construct linked list from vector with Arc<Mutex> in rust

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related