1

I am learning about link list & thought to write a simple one.

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

with a impl block

impl ListNode {

    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }

    // Issue with insert method.
    fn insert(&mut self, val: i32) -> &mut Self {
       // Match causing issue because it takes mut ref.
        match &mut self.next {
            Some(node) => node.insert(val),
            None => {
                // Cannot update value because only one mut ref allowed.
                self.next = Some(Box::new(ListNode::new(val)));
                self
            }
        }
    }
}

If I replace mut ref with just self in insert() it works fine but at every insert call transferring ownership doesn't feel logical. Is there any way to insert new item in link list while only taking node's ref?

wejoey
  • 216
  • 1
  • 3
  • 14
Siddharth Teli
  • 87
  • 6

2 Answers2

1

Here's an iterative rather than recursive version of @kmdreko's answer. A recursive approach can cause stack overflows on long lists.

fn insert(&mut self, val: i32) -> &mut Self {
    // Iterate to last node
    let mut tail = self;
    while let Some(ref mut next) = tail.next {
        tail = next;
    }
    // Insert new node at the end
    tail.next.insert(Box::new(ListNode::new(val)))
}

Note the usage of Option::insert. It returns a mutable reference to the inserted value, making it easy to return a reference to the new end node.

PitaJ
  • 12,969
  • 6
  • 36
  • 55
1

This is a niche case where you would want to bypass match ergonomics so the None case doesn't hold an exclusive reference. You can do that by matching on the value directly (not a mutable reference) and binding to a variable via mut ref like so:

fn insert(&mut self, val: i32) -> &mut Self {
    match self.next {
        Some(ref mut node) => node.insert(val),
        None => {
            self.next = Some(Box::new(ListNode::new(val)));
            self
        }
    }
}

For some background: "match ergonomics" is the mechanism that allows matching on references to seamlessly match on the referent's structure, and thus cause the bindings to be references into that structure. However, the problem here is that the mutable reference is created in the match scrutinee and is held for the whole match, even when the None case doesn't need to preserve any reference. Using the older ref syntax makes it so that only the Some case needs to create and hold a mutable reference while the None case does not, leaving self unbound.

kmdreko
  • 42,554
  • 6
  • 57
  • 106