Swapping two elements of a singly-linked list Similarly to Learning Rust With Entirely Too Many Linked Lists, I'm trying to learn Rust by working with linked lists. Currently I'm trying to implement a function bubble(...) that takes 2 elements of a singly-linked list and swaps them.

Any feedback is greatly appreciated! (Rust playground link here.)

#![allow(dead_code)]

use ::std::mem::replace;
use ::std::mem::swap;

#[derive(Debug)]
pub struct List&lt;T&gt; {
    list: Node&lt;T&gt;,
}

type Node&lt;T&gt; = Option&lt;Box&lt;Link&lt;T&gt;&gt;&gt;;

#[derive(Debug)]
struct Link&lt;T&gt; {
  head: T,
  tail: Node&lt;T&gt;,
}

impl&lt;T&gt; List&lt;T&gt; {
  pub fn push(&amp;mut self, elem: T) {
    self.list = Some(Box::new(
      Link{ head: elem, tail: replace(&amp;mut self.list, None) }));
  }

  pub fn pop(&amp;mut self) -&gt; Option&lt;T&gt; {
    match replace(&amp;mut self.list, None) {
      Some(next_box) =&gt; {
        let next = *next_box;
        self.list = next.tail;
        Some(next.head)
      }
      _ =&gt; None
    }
  }

  // First attempt: Use push+pop. Not perfect, as we move the values
  // in and out, and if they're larger, we waste resources.
  pub fn bubble(&amp;mut self) -&gt; bool {
    if let Some(first) = self.pop() {
      if let Some(second) = self.pop() {
        self.push(first);
        self.push(second);
        return true;
      } else {
        self.push(first);
      }
    }
    false
  }

  // Learning from the above attempt, I created another push+pop
  // functions that don't move values, just Boxes instead.

  // Any tail of 'singleton' is silently discarded.
  fn push_singleton(&amp;mut self, mut singleton: Box&lt;Link&lt;T&gt;&gt;) {
    swap(&amp;mut self.list, &amp;mut singleton.tail);
    self.list = Some(singleton);
  }

  fn pop_singleton(&amp;mut self) -&gt; Node&lt;T&gt; {
    match replace(&amp;mut self.list, None) {
      Some(mut next_box) =&gt; {
        swap(&amp;mut self.list, &amp;mut next_box.tail);
        Some(next_box)
      }
      _ =&gt; None
    }
  }

  // Otherwise the implementation is very similar to 'bubble' above.
  pub fn bubble2(&amp;mut self) -&gt; bool {
    if let Some(first_box) = self.pop_singleton() {
      if let Some(second_box) = self.pop_singleton() {
        self.push_singleton(first_box);
        self.push_singleton(second_box);
        return true;
      } else {
        self.push_singleton(first_box);
      }
    }
    false
  }


  // Third attempt: Directly unpack the first two nodes and combine them
  // back together.
  pub fn bubble3(&amp;mut self) -&gt; bool {
    if let Some(mut first_box) = replace(&amp;mut self.list, None) {
      if let Some(mut second_box) = replace(&amp;mut first_box.tail, None) {
        first_box.tail = replace(&amp;mut second_box.tail, None);
        second_box.tail = Some(first_box);
        *self = List{ list: Some(second_box) };
        return true;
      } else {
        *self = List{ list: Some(first_box) };
      }
    }
    false
  }
}

fn main() {}
Run Rustfmt. It well automatically tell you such things as:


Idiomatic Rust uses 4-space indents.
Match arms without curly braces have trailing commas
You don't need to prefix paths in use with ::; that's the default.

You don't need #![allow(dead_code)] and it's better to not disable warnings that broadly.
It's usual to import only the module, not the free function, and then namespace the function. For example, mem::replace.
mem::replace(&amp;mut /* ... */, None) is equivalent to Option::take
You can also replace some usages of mem::swap with Option::take and direct assignment. This means you don't need to use functions from mem at all.


#[derive(Debug)]
pub struct List&lt;T&gt; {
    list: Node&lt;T&gt;,
}

type Node&lt;T&gt; = Option&lt;Box&lt;Link&lt;T&gt;&gt;&gt;;

#[derive(Debug)]
struct Link&lt;T&gt; {
    head: T,
    tail: Node&lt;T&gt;,
}

impl&lt;T&gt; List&lt;T&gt; {
    pub fn push(&amp;mut self, elem: T) {
        self.list = Some(Box::new(Link {
            head: elem,
            tail: self.list.take(),
        }));
    }

    pub fn pop(&amp;mut self) -&gt; Option&lt;T&gt; {
        match self.list.take() {
            Some(next_box) =&gt; {
                let next = *next_box;
                self.list = next.tail;
                Some(next.head)
            }
            _ =&gt; None,
        }
    }

    // First attempt: Use push+pop. Not perfect, as we move the values
    // in and out, and if they're larger, we waste resources.
    pub fn bubble(&amp;mut self) -&gt; bool {
        if let Some(first) = self.pop() {
            if let Some(second) = self.pop() {
                self.push(first);
                self.push(second);
                return true;
            } else {
                self.push(first);
            }
        }
        false
    }

    // Learning from the above attempt, I created another push+pop
    // functions that don't move values, just Boxes instead.

    // Any tail of 'singleton' is silently discarded.
    fn push_singleton(&amp;mut self, mut singleton: Box&lt;Link&lt;T&gt;&gt;) {
        singleton.tail = self.list.take();
        self.list = Some(singleton);
    }

    fn pop_singleton(&amp;mut self) -&gt; Node&lt;T&gt; {
        match self.list.take() {
            Some(mut next_box) =&gt; {
                self.list = next_box.tail.take();
                Some(next_box)
            }
            _ =&gt; None,
        }
    }

    // Otherwise the implementation is very similar to 'bubble' above.
    pub fn bubble2(&amp;mut self) -&gt; bool {
        if let Some(first_box) = self.pop_singleton() {
            if let Some(second_box) = self.pop_singleton() {
                self.push_singleton(first_box);
                self.push_singleton(second_box);
                return true;
            } else {
                self.push_singleton(first_box);
            }
        }
        false
    }

    // Third attempt: Directly unpack the first two nodes and combine them
    // back together.
    pub fn bubble3(&amp;mut self) -&gt; bool {
        if let Some(mut first_box) = self.list.take() {
            if let Some(mut second_box) = first_box.tail.take() {
                first_box.tail = second_box.tail.take();
                second_box.tail = Some(first_box);
                *self = List {
                    list: Some(second_box),
                };
                return true;
            } else {
                *self = List {
                    list: Some(first_box),
                };
            }
        }
        false
    }
}

fn main() {}


For what it's worth, I prefer bubble2 as the implementation is better factored and has helper functions.

I'm not a big fan of the word "singleton" here, as that feels like a misuse of the term. I don't have a great alternative name other than {push,pop}_boxed though.