Adding an append method to a singly linked list

by

As described in Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time, you need to transfer ownership of the mutable reference when performing iteration. This is needed to ensure you never have two mutable references to the same thing.

We use similar code as that Q&A to get a mutable reference to the last item (back) which will always be the Nil variant. We then call it and set that Nil item to a Cons. We wrap all that with a by-value function because that’s what the API wants.

No extra allocation, no risk of running out of stack frames.

use List::*;

#[derive(Debug)]
enum List {
    Cons(u32, Box<List>),
    Nil,
}

impl List {
    fn back(&mut self) -> &mut List {
        let mut node = self;

        loop {
            match {node} {
                &mut Cons(_, ref mut next) => node = next,
                other => return other,
            }
        }
    }

    fn append_ref(&mut self, elem: u32) {        
        *self.back() = Cons(elem, Box::new(Nil));
    }

    fn append(mut self, elem: u32) -> Self {
        self.append_ref(elem);
        self
    }
}

fn main() {
    let n = Nil;
    let n = n.append(1);
    println!("{:?}", n);
    let n = n.append(2);
    println!("{:?}", n);
    let n = n.append(3);
    println!("{:?}", n);
}

When non-lexical lifetimes are enabled, this function can be more obvious:

fn back(&mut self) -> &mut List {
    let mut node = self;

    while let Cons(_, next) = node {
        node = next;
    }

    node
}

More Related Contents:

  1. Why can’t I store a value and a reference to that value in the same struct?
  2. How do I create a heterogeneous collection of objects?
  3. Is it possible to control the size of an array using the type parameter of a generic?
  4. How do I stop iteration and return an error when Iterator::map returns a Result::Err?
  5. Are polymorphic variables allowed?
  6. Does println! borrow or own the variable?
  7. Why does Iterator::take_while take ownership of the iterator?
  8. When should I implement std::convert::From vs std::convert::Into?
  9. Efficiently mutate a vector while also iterating over the same vector
  10. Why is it possible to implement Read on an immutable reference to File?
  11. Compare enums only by variant, not value
  12. How do you unwrap a Result on Ok or return from the function on Err?
  13. What does “mismatched types: expected `()`” mean when using an if expression?
  14. How do I read the entire body of a Tokio-based Hyper request?
  15. When returning the outcome of consuming a StdinLock, why was the borrow to stdin retained?
  16. How does Rust pattern matching determine if the bound variable will be a reference or a value?
  17. Using generic trait methods like .into() when type inference is impossible
  18. Why does an enum require extra memory size?
  19. Why does Rust disallow mutable aliasing?
  20. How to store rusqlite Connection and Statement objects in the same struct in Rust? [duplicate]
  21. Why can’t I reuse a &mut reference after passing it to a function that accepts a generic type?
  22. print! macro not executed until pressing Enter
  23. How can I override a constant via a compiler option?
  24. Why am I getting “parameter is never used [E0392]”?
  25. How to quiet a warning for a single statement in Rust?
  26. Use of undeclared type or module `std` when used in a separate module
  27. Is there an elegant solution to modifying a structure while iterating?
  28. Can a struct containing a raw pointer implement Send and be FFI safe?
  29. Lazy sequence generation in Rust
  30. Is there a way to get the field names of a struct in a macro?

Leave a Comment