Construction of a linked list: how to avoid the mess?

help
1

Hello there, I'm learning Rust! To do so, I'm working on easy problems found on several websites. In one of them, I should create a linked list having the following definition for a node:

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
	pub val: i32,
	pub next: Option<Box<ListNode>>
}

impl ListNode {
	#[inline]
	pub fn new(val: i32) -> Self {
		ListNode {
			next: None,
			val
		}
	}
}

To create a linked list using this definition I came up with this:

let mut l1 = Some(Box::new(ListNode {
        next: Some(Box::new(ListNode {
            next: Some(Box::new(ListNode {
                next: None,
                val: 4,
            })),
            val: 2
        })),
        val: 1,
    }));

Even if the linked list is correct (1->2->4), it obvious does not seem right to me. In fact, I tried to build it as follows:

let mut l11 = Box::new(ListNode::new(1));
let mut l12 = Box::new(ListNode::new(2));
let l13 = Box::new(ListNode::new(4));

l11.next = Some(l12);
l12.next = Some(l13);

But the borrow checker arises, highlighting that Box<ListNode>does not implement the Copy trait. I'm pretty sure I cannot create the list like that but I'm missing why.

2

Here you first try to move l12 into l11, then you try to modify l12 again. Do it in the opposite order to avoid the ownership transfer conflict.

3

That's right, thank you!

However, my doubt still remains. What if I want to build the list starting from the head (and not from the tail as in this case)? Suppose I take subsequential nodes from input, starting from the first one (head) and ending to the last one (tail). In such case, I couldn't use the approach you mentioned (cause I don't have all of the nodes at compile time).

4

You could rewrite your code like this to make it look a little less backward:

let mut l1 = Some(Box::new(ListNode {
    val: 1,
    next: Some(Box::new(ListNode {
        val: 2
        next: Some(Box::new(ListNode {
            val: 4,
            next: None,
        })),
    })),
}));

(Note: I just swapped the order of the val and next fields inside each ListNode.)

5

Have you already been pointed to the classic article about this? Linked lists are the worst way to learn Rust:

3 Likes
6

You can also write some helpers as shorthand:

type List = Option<Box<ListNode>>;

fn cons(val: i32, next: List) -> List {
    Some(Box::new(ListNode { val, next }))
}

let l1 = cons(1, cons(2, cons(4, None)));
1 Like
7

Correct. One way you can solve this is to use a reference-counted pointer type instead. This will allow you to avoid giving up ownership of a node when adding it to the list.

use std::rc::Rc;

pub struct ListNode {
	pub val: i32,
	pub next: Option<Rc<ListNode>>
}

let mut l11 = Rc::new(ListNode::new(1));
let mut l12 = Rc::new(ListNode::new(2));
let l13 = Rc::new(ListNode::new(4));

l11.next = Some(Rc::clone(&l12));
l12.next = Some(Rc::clone(&l13));

except, whoops, even this fails, because Rc does not allow mutation! (if it did, you could use two copies of an Rc to create aliasing mutable references). So to perform this mutation you will have to additionally use RefCell to check for aliasing at runtime.

use std::rc::Rc;
use std::cell::RefCell;

pub struct ListNode {
	pub val: i32,
	pub next: Option<Rc<RefCell<ListNode>>>
}

impl ListNode {
    pub fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(ListNode { val, next: None }))
    }
}

fn main() {
    let mut l11 = ListNode::new(1);
    let mut l12 = ListNode::new(2);
    let l13 = ListNode::new(4);
    
    l11.borrow_mut().next = Some(Rc::clone(&l12));
    l12.borrow_mut().next = Some(Rc::clone(&l13));
}

The above works (Rust Playground), but I think that at this point it goes without saying that using a linked list like this is a fairly unidiomatic thing to do in Rust and little effort has been spent to make them easier to build. Linked lists are common in C, because in that language they are one of the easiest kinds of variable-length container type to implement.

But in Rust, if you want a simple variable length container, you should be using a Vec. Not only will it be far more ergonomic but it will also tend to be several orders of magnitude faster due to incurring far fewer cache misses during iteration.

If you really want a linked list for the benefits that are uniquely provided by linked lists, which are:

  • O(1) insertion of an element after any arbitrary node in the list (provided that you already have some form of pointer or "cursor" to that node)
  • in doubly-linked lists, you also get O(1) removal of a node (again, provided some form of pointer or cursor)

then a more idiomatic way to do this in Rust is to use indices instead. I won't write a full implementation, but sort of what I'm thinking is (might need a bit more thought because it's currently unclear how to insert the first node):

pub type NodeLabel = usize;
pub struct Node {
    pub val: i32,
    pub next: Option<NodeLabel>,
}

pub struct List {
    head: Option<NodeLabel>,
    nodes: Vec<Node>,
}

impl List {
    /// Get an empty list.
    pub fn new() -> Self { ... }
    /// Get a cursor to the beginning of the list, if it has at least one element.
    pub fn head() -> Option<NodeLabel> { ... }
    /// Insert a node after a given node.
    pub fn insert_after(label: NodeLabel, val: i32) -> NodeLabel { ... }
    /// Look up a node given its label.
    pub fn get_node(label: NodeLabel) -> &Node { ... }
}

This technique of using indices instead of pointers can extend more generally to any graphlike data structure, such as trees or graphs.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.