Implement Single LinkedList method

1

Hello,

I am trying to implement a Single LinkedList, in an effort to better understand Options and Box<> ptrs.

  1. Would appreciate on my two approach to adding to Head - add_head1 and add_head2.
  2. Having some trouble implementing add_tail(). Would appreciate some help understanding the error.
type NodePointer = Option<Box<Node>>;
#[derive(Debug)]
struct LinkedList {
    head: NodePointer,
}

#[derive(Debug)]
struct Node {
    element: u32,
    next: NodePointer,
}

impl LinkedList {
    fn new() -> LinkedList {
        LinkedList { head: None, }
    }

    fn add_head1(&mut self, element: u32) {
        let prev_head = self.head.take();
        let new_head = Some(Box::new(Node {
            element,
            next: prev_head,
        }));
        self.head = new_head;
    }

    fn add_head2(&mut self, element: u32) {
        let mut new_head = Box::new(Node {
            element,
            next: None,
        });
        if self.head.is_some() {
            new_head.next.insert(self.head.take().unwrap());
        }
        self.head.insert(new_head);
    }

    fn remove_head(&mut self) -> Option<u32> {
        match self.head.take() {
            Some(previous_head) => {
                self.head = previous_head.next;
                Some(previous_head.element)
            }
            None => None,
        }
    }
    
    fn add_tail(&mut self, element: u32) {
        let new_node = Some(Box::new( Node {
            element,
            next: None,
        }));

        if self.head.is_none() {
            self.head = new_node;
        } else {
            // traverse the list till end, then insert.
            let mut runner_node = &self.head;
            while (*runner_node).as_ref().unwrap().next.is_some() {
                runner_node = &runner_node.as_ref().unwrap().next;
            }
            // Tried both the following, getting different compile error for all of them.
            (*runner_node).as_ref().unwrap().next = *new_node;
            // (*runner_node).as_ref().unwrap().next = new_node;
            // runner_node.as_ref().unwrap().next = new_node;
        }
    }
2

this is pretty much the best you can do with an imperative style API. there's only one thing you can do to make it more concise, that is to inline the variables prev_head and new_head:

    fn add_head1(&mut self, element: u32) {
-       let prev_head = self.head.take();
-       let new_head = Some(Box::new(Node {
+       self.head = Some(Box::new(Node {
            element,
-           next: prev_head,
+           next: self.head.take(),
        }));
-       self.head = new_head;
    }

one alternative is a functional style API, which consumes a list and returns another list. basically, mimic cons in lisp:

fn add_head3(self, element: u32) -> Self {
    LinkedList {
        head: Some(Box::new(Node {
            element,
            next: self.head
        }))
    }
}

you don't need the if statement, Option::take() is all you need.

also, Option::insert() can be replaced with Option::replace() if you don't need the returned mut reference from Option::insert().

    fn add_head2(&mut self, element: u32) {
        let mut new_head = Box::new(Node {
            element,
            next: None,
        });
-       if self.head.is_some() {
-           new_head.next.insert(self.head.take().unwrap());
-       }
+       new_head.next = self.head.take();
        self.head.replace(new_head);
    }

and then, you see the assignment of new_head.next is unnecessary, so you move it to the construction of new_head:

    fn add_head2(&mut self, element: u32) {
-       let mut new_head = Box::new(Node {
+       let new_head = Box::new(Node {
            element,
-           next: None,
+           next: self.head.take(),
        });
-       new_head.next = self.head.take();
        self.head.replace(new_head);
    }

then you get the same outcome as add_head1(). note: self.head.replace(new_head) is exactly the same as self.head = Some(new_head);

you are very close to make it working, what you are missing is Option::as_mut(), which turns a &mut Option<T> into an Option<&mut T>. [1]. first, you need to take mut reference instead of shared reference, then you just do a pattern match on the &mut NodePointer to move the runner_node (what I call a "cursor") to runner_node.next when it's not nil (nil is functional language term, here it means None)

here's how to do it (see caveat below):

/// this function needs `-Zpolonius` to compile
fn next_tail(&mut self) -> &mut NodePointer {
    let mut cursor = &mut self.head;
    while let Some(node) = cursor.as_mut() {
        cursor = &mut node.next;
    }
    cursor
}

fn add_tail(&mut self, element: u32) {
    self.next_tail().replace(Box::new(Node {
        element,
        next: None,
    }));
}

caveat: there's a technicality remaining: the current borrow checker cannot understand the lifetime due to the loop, and the code only compiles with the (still unstable) polonius borrow checker.

unfortunately, workaround on stable requires unsafe, but you don't have to write the unsafe code if you are not comfortable, the polonius-the-crab crate is recommended.

EDIT:

after some thinking, the lifetime error is caused by the combination of the loop, and the fact Option::as_mut() is a function. it turns out you don't need -Zpolonius at all, if you eliminate the function boundary (i.e. inline it).

better yet, thanks to match ergonomics, the code can be made even more consice:

fn next_tail2(&mut self) -> &mut NodePointer {
    let mut cursor = &mut self.head;
    // the commented line is the "verbose" syntax WITHOUT match ergonomics
    //while let &mut Some(ref mut node) = cursor {
    while let Some(node) = cursor {
        cursor = &mut node.next;
    }
    cursor
}

END of EDIT

linked list in rust is notoriously hard, that's why there's a whole book (or blog series) on this topic.

  1. technically, Option::as_deref_mut() is actually the "correct" API to use, but Option::as_mut() also works because of auto deref coercion ↩ī¸Ž

1 Like