CODEWITHSUNDEEP
rust
user541020
user541020

Reputation: 267

Is it possible to reverse a linked list in-place without allocating any nodes?

I'm trying to understand how ownership in Rust works with regard to linked lists. I have this code:

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

fn main() {
    let mut x = Box::new(Node {value: 1, next: None});
    let mut y = Box::new(Node {value: 2, next: Some(x)});
}

which creates a linked list y -> x -> null. Is it possible to switch this around in-place, so that we end up with x -> y -> null without allocating any new nodes?

Upvotes: 2

Views: 809

Answers (1)

DK.
DK.

Reputation: 59095

Absolutely. Ownership in this case is pretty simple: the main function owns y, which owns x, and owners can mutate the things they own.

To swap two nodes a and b where a → b → …, you just need to do the following:

  • Disconnect b from a, so that you have a → ⊥ and b → ….
  • Remove everything following b; call this c…. You now have b → ⊥, and c → …. Note that c might be empty, or it might be a long list; we don't care.
  • a and b are now alone, and don't connect to anything else, so you can just exchange their contents, swapping them in place.
  • Attach c to the end of a, giving you a → c → ….
  • Attach a to the end of b, giving you b → a → ….

No new nodes need allocating, and this can be transcribed pretty much directly into Rust:

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

impl Node {
    pub fn swap_with_next(&mut self) {
        use std::mem::swap;

        match self.next.take() {
            Some(mut next_node) => {
                let next_next = next_node.next.take();
                swap(self, &mut next_node);
                next_node.next = next_next;
                self.next = Some(next_node);
            },
            None => {
                // Uh-oh, there's nothing to swap *with*!
                panic!("cannot swap with nothing");
            }
        }
    }

    pub fn show(&self) {
        print!("{:?}", self.value);
        if let Some(next) = self.next.as_ref() {
            print!(" -> ");
            next.show();
        }
    }
}

fn main() {
    let mut w = Box::new(Node { value: 0, next: None });
    let mut x = Box::new(Node { value: 1, next: Some(w) });
    let mut y = Box::new(Node { value: 2, next: Some(x) });

    y.show();
    println!("");

    y.swap_with_next();
    y.show();
    println!("");
}

Finally, I'd be remiss if I didn't point you toward Learning Rust With Entirely Too Many Linked Lists.

Upvotes: 7

Related Questions