Implementing a singly linked list

help
1

I am new to rust and I currently have the following implementation to create a simple singly linked list:

#[derive(PartialEq, Eq, Clone, Debug)]
struct ListNode {
  val: i32,
  next: Option<Box<ListNode>>
}
 
impl ListNode {
   #[inline]
   fn new(val: i32) -> Self {
     ListNode {
       next: None,
       val
     }
   }
}

fn main() {
    createLinkedList();
}

fn createLinkedList() -> Option<Box<ListNode>> {
    let mut prevNode: Option<Box<ListNode>> = None;
    let mut ret: Option<Box<ListNode>> = None;

    for d in 1..5 {
        let newNode = Some(Box::<ListNode>::new(ListNode::new(d)));
        match prevNode {
            None => { ret = newNode;},
            Some(mut n) => { n.next = newNode;},
        };

        prevNode = newNode;
    }
    ret
}

This code doesn't compile because newNode isn't valid after being moved once. I understand the error, but I'm not really sure of how to fix this. I have tried to use different combinations of references and they all provide different errors.

If I use clone like the error suggests then the result is not what I want because then .next of a clone is modified instead of the original one.

Does anyone have some advice on how to solve this?

2

Linked lists are somewhat at heads with Rust's memory model. Fortunately there is an entire set of tutorials built around them: Introduction - Learning Rust With Entirely Too Many Linked Lists

1 Like
3

I unfortunately don't have time to write a detailed explanation, but you can make it work by doing something like this:

fn createLinkedList() -> Option<Box<ListNode>> {
    let mut ret: Option<Box<ListNode>> = Some(Box::<ListNode>::new(ListNode::new(1)));
    let mut prevNode: &mut ListNode = ret.as_mut().unwrap();

    for d in 2..5 {
        prevNode.next = Some(Box::<ListNode>::new(ListNode::new(d)));
        prevNode = prevNode.next.as_mut().unwrap();
    }
    
    ret
}
1 Like
4

Here's my first try at modifying the code

fn createLinkedList() -> Option<Box<ListNode>> {
    let mut ret: Option<Box<ListNode>> = None;
    let mut prev_node_next: &mut Option<Box<ListNode>> = &mut ret;
    
    for d in 1..5 {
        let new_node = Some(Box::<ListNode>::new(ListNode::new(d)));
        *prev_node_next = new_node;
        match prev_node_next {
            None => { unreachable!() ; },
            Some(n) => { prev_node_next = &mut n.next; },
        };
    }
    ret
}

and with some simplifications

fn createLinkedList() -> Option<Box<ListNode>> {
    let mut ret: Option<Box<ListNode>> = None;
    let mut prev = &mut ret;

    for d in 1..5 {
        let node = Box::new(ListNode::new(d));
        prev.insert(node);
        prev = &mut prev.as_mut().unwrap().next
    }
    ret
}

and taking it even further ends with

fn createLinkedList() -> Option<Box<ListNode>> {
    let mut ret = None;
    let mut prev = &mut ret;
    for d in 1..5 {
        prev = &mut prev.insert(Box::new(ListNode::new(d))).next;
    }
    ret
}

Edit: I couldn’t help but also add this single-line, single-expression, and hard-to-read solution nobody asked for:

use tap::Tap;
fn createLinkedList() -> Option<Box<ListNode>> {
    None.tap_mut(|r| drop((1..5).fold(r, |p, d| &mut p.insert(Box::new(ListNode::new(d))).next)))
}

More realistically though, I suppose using just the fold could still make sense, somewhat:

fn createLinkedList() -> Option<Box<ListNode>> {
    let mut ret = None;
    (1..5).fold(&mut ret, |prev, d| {
        &mut prev.insert(Box::new(ListNode::new(d))).next
    });
    ret
}
5 Likes