Populating a Linked List Inside a Loop

help
1

I am attempting to populate a linked list with values from an array, but am running into problems with the borrow checker, and I am unsure of how to express my algorithm without multiple mutable references. I have left comments where I am running into issues, and I would really appreciate suggestions on how to write this in a compilable way.

struct Node {
    next: Option<Box<Node>>,
    value: i64,
}

struct LinkedList {
    head: Option<Box<Node>>,
}

fn main () {
    let values: [i64; 11] = [1,1,5,3,5,4,2,7,7,7,8];
    let mut test_list = LinkedList {
        head: None
    };
    let mut current_node: &mut Option<Box<Node>> = &mut None;
    let mut new_node: Option<Box<Node>>;
    for value in values.iter() {
        new_node = Some(Box::new(Node {
            next: None,
            value: *value
        })); 
        if let Some(ref mut current_node_value) = current_node {
            current_node_value.next = new_node;
            // I cannot write to current node here because I already borrowed it. Somehow I need to unborrow it?? or avoid making two references??
            current_node = &mut current_node_value.next;
        } else {
            // Cannot assign here since I borrow it in a previous iteration on the next line (even though this will only run in the first iteration). 
            test_list.head = new_node;
            current_node = &mut test_list.head;
        }
    // The data that new_node refers to goes out of scope here, despite needing to live longer. What should I do about it?
    }
    remove_dups(test_list);
}
2

This code works fine with 2018 edition, thanks to NLL (non-lexical lifetimes).

You can change the edition on the playground in the "..." dropdown menu next to "Stable". 2015 edition has all the borrowing errors you mentioned, because lifetimes were then limited to lexical scope.

3

Thanks for the information. I'll go try and wrap my head around NLL (and figure out how to convince cargo script to run 2018 edition rust). However, I'm still curious how to implement this in 2015 rust.

4

Hi, I wanted to try to make it work but ended up with a completely different approach, maybe you'll find it interesting, maybe not playground.

The idea is that it is really simpler to build the linked list from the end because you never try to have the current node and the next one and getting the last element of a vector is just a pop.
Also, there is a rust introduction using linked lists you might find it interresting link.

2 Likes
5

Going in reverse is way more concise and elegant. I really like that solution.

Thanks for the link, I will check it out.

1 Like
7

This may be a bit OT, but since you're doing singly linked list, I'd recommend a "Lisp Cell" style list:

pub enum Node {
  Nil,
  Cons(u64, Box<Node>)
}

So then

[] -> Nil
[1] => Cons(1, Nil),
[1, 2] => Cons(1, Cons(2, Nil)),
[1, 2, 3] => Cons(1, (Cons 2, (Cons 3, Nil)))

Once it's written out this way, it's clear that @leudz 's reverse approach makes sense.

2 Likes
8

First of all, I suggest a minor refactoring of your base definitions:

#[derive(Debug)]
pub
struct Node {
    head: i64,
    tail: LinkedList,
}

pub use LinkedList::*;
#[derive(Debug)]
pub
enum LinkedList {
    Nil,
    Cons(Box<Node>),
}

// Let's add a nicer constructor
impl LinkedList {
    pub
    fn cons (head: i64, tail: Self) -> Self
    {
        LinkedList::Cons(Box::new(Node {
            head,
            tail,
        }))
    }
}

  • most of the change is that instead of using a newtype over an Option I find it best to use an enum with better named variants: it increases a lot the readability.

impl LinkedList {
    #[inline]
    pub
    fn take (self: &'_ mut Self) -> Self
    {
        mem::replace(self, LinkedList::Nil)
    }
}

Now we can reversely collect an iterable as in any classic functional language exercise:

impl LinkedList {
    pub
    fn from_iter_rev (iterable: impl IntoIterator<Item = i64>) -> Self
    {
        let mut list = LinkedList::Nil;
        for x in iterable {
            list = LinkedList::cons(x, list);
        }
        list
    }
}

However, Rust allows not only functional constructs, but also pointer/cursor mutation à la C/C++ (but without the need for unsafe raw pointers):

impl iter::FromIterator<i64> for LinkedList {
    fn from_iter<Iterable : IntoIterator<Item = i64>> (
        iterable: Iterable,
    ) -> Self
    {
        let mut list = LinkedList::Nil;
        let mut cursor = &mut list;
        for x in iterable {
            let singleton = Box::new(Node { head: x, tail: Nil });
            debug_assert!(// cursor points to an empty list (end of list)
                (*cursor)
                    .is_empty()
            );
            // mutate the pointee to append an element to the list
            *cursor = LinkedList::Cons(singleton);
            // move the cursor forward
            cursor = match *cursor {//
                | Cons(ref mut node) => &mut node.tail,

                | Nil => unreachable!(),
            }
        }
        list
    }
}

Finally we can go and implement remove_dups:

impl LinkedList {
    pub
    fn remove_dups (self: &'_ mut Self)
    {
        match *self {//
            | Nil => {},

            | Cons(ref mut node) => {
                with_prev(&mut node.tail, node.head);
            },
        }

        fn with_prev (cursor: &'_ mut LinkedList, prev: i64)
        {
            match *cursor {//
                | Nil => {},

                | Cons(ref mut node) => {
                    if node.head == prev {
                        // mutate the pointee
                        *cursor = node.tail.take();
                        with_prev(cursor, prev);
                    } else {
                       // advance the cursor
                        with_prev(&mut node.tail, node.head);
                    }
                },
            }
        }
    }
}

Note: NLL are really needed here to get a nicer syntax, else Rust has trouble with using a mut cursor: &mut _. Still, here is the previous function without NLL:

        fn with_prev (cursor: &'_ mut LinkedList, prev: i64)
        {
            // mutate the pointee
            *cursor = match *cursor {//
                | Nil => return, // early return

                | Cons(ref mut node) => {
                    if node.head == prev {
                        node.tail.take()
                    } else {
                        // early return
                        return with_prev(&mut node.tail, node.head);
                    }
                },
            };
            with_prev(cursor, prev);
        }

Bonus: LinkedList traversal (e.g., to Display it)

Although a LinkedList can lead to a very simple implementation of a stack:

pub
trait MutableStack {
    type Item;

    fn push (self: &'_ mut Self, value: Self::Item);
    fn pop  (self: &'_ mut Self) -> Option<Self::Item>;
}

impl MutableStack for LinkedList {
    type Item = i64;

    #[inline]
    fn push (self: &'_ mut Self, value: i64)
    {
        *self = Self::cons(value, self.take());
    }

    #[inline]
    fn pop (self: &'_ mut Self) -> Option<i64>
    {
        match self {//
            | Nil => None,

            | Cons(ref mut node) => {
                let (head, tail) = (node.head, node.tail.take());
                *self = tail;
                Some(head)
            },
        }
    }
}

which, in turn, leads to a trivial implementation of Iterator:

impl Iterator for LinkedList {
    type Item = i64;

    #[inline]
    fn next (
        self: &'_ mut Self,
    ) -> Option<Self::Item>
    {
        self.pop()
    }
}

but this requires in-place mutation...

To iterate over reads of the contents of the list, functional style favors internal iteration and folding:

impl Visit for LinkedList {
    #[inline]
    fn try_fold<Acc, Ret, Folder> (
        self: &'_ Self,
        initial_acc: Acc,
        mut folder: Folder,
    ) -> Ret
    where
        Ret : Try<Ok = Acc>,
        Folder : FnMut(Acc, i64) -> Ret,
    {
        let mut acc = initial_acc;
        let mut cursor = self;
        loop {
            // Advance cursor
            cursor = match *cursor {//
                | Nil => return Ret::from_ok(acc),

                | Cons(ref node) => {
                    acc = folder(acc, node.head)?;
                    &node.tail
                },
            }
        }
    }
}

pub
trait Visit {
    fn try_fold<Acc, Ret, Folder> (
        self: &'_ Self,
        initial_acc: Acc,
        folder: Folder,
    ) -> Ret
    where
        Ret : Try<Ok = Acc>,
        Folder : FnMut(Acc, i64) -> Ret,
    ;

    #[inline]
    fn fold<Acc, Folder> (
        self: &'_ Self,
        acc: Acc,
        folder: Folder,
    ) -> Acc
    where
        Folder : FnMut(Acc, i64) -> Acc,
    {
        enum Unfallible {}
        self.try_fold(acc, {
                let mut folder = folder;
                move |acc, x| Ok(folder(acc, x))
            })
            .unwrap_or_else(|unfallible: Unfallible| match unfallible {})
    }

    #[inline]
    fn for_each (
        self: &'_ Self,
        f: impl FnMut(i64),
    )
    {
        self.fold((), { let mut f = f; move |(), x| f(x) })
    }

    #[inline]
    fn try_for_each<R, F> (
        self: &'_ Self,
        f: F,
    ) -> R
    where
        F : FnMut(i64) -> R,
        R : Try<Ok = ()>,
    {
        self.try_fold((), { let mut f = f; move |(), x| f(x) })
    }
}

Thus allowing to easily define methods based on this folding:

impl fmt::Display for LinkedList {
    fn fmt (
        self: &'_ Self,
        stream: &'_ mut fmt::Formatter<'_>,
    ) -> fmt::Result
    {
        self.try_for_each(|x| write!(stream, "{} :: ", x))?;
        write!(stream, "[]")
    }
}

Running it

fn main ()
{
    use iter::FromIterator;

    const NUMBERS: &[i64] = &[1, 1, 5, 3, 5, 4, 2, 7, 7, 7, 8];

    let reversed_list = LinkedList::from_iter_rev(
        NUMBERS
            .iter()
            .cloned()
    );
    eprintln!("{}", reversed_list);

    let mut test_list = LinkedList::from_iter(
        NUMBERS
            .iter()
            .cloned()
    );
    eprintln!("{}", test_list);

    test_list.remove_dups();
    eprintln!("{}", test_list);
}

displays (Playground):

8 :: 7 :: 7 :: 7 :: 2 :: 4 :: 5 :: 3 :: 5 :: 1 :: 1 :: []
1 :: 1 :: 5 :: 3 :: 5 :: 4 :: 2 :: 7 :: 7 :: 7 :: 8 :: []
1 :: 5 :: 3 :: 5 :: 4 :: 2 :: 7 :: 8 :: []
4 Likes
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.