Swapping two elements of a singly-linked list

Question

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<T> {
 list: Node<T>,
}
type Node<T> = Option<Box<Link<T>>>;
#[derive(Debug)]
struct Link<T> {
 head: T,
 tail: Node<T>,
}
impl<T> List<T> {
 pub fn push(&mut self, elem: T) {
 self.list = Some(Box::new(
 Link{ head: elem, tail: replace(&mut self.list, None) }));
 }
 pub fn pop(&mut self) -> Option<T> {
 match replace(&mut self.list, None) {
 Some(next_box) => {
 let next = *next_box;
 self.list = next.tail;
 Some(next.head)
 }
 _ => 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(&mut self) -> 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(&mut self, mut singleton: Box<Link<T>>) {
 swap(&mut self.list, &mut singleton.tail);
 self.list = Some(singleton);
 }
 fn pop_singleton(&mut self) -> Node<T> {
 match replace(&mut self.list, None) {
 Some(mut next_box) => {
 swap(&mut self.list, &mut next_box.tail);
 Some(next_box)
 }
 _ => None
 }
 }
 // Otherwise the implementation is very similar to 'bubble' above.
 pub fn bubble2(&mut self) -> 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(&mut self) -> bool {
 if let Some(mut first_box) = replace(&mut self.list, None) {
 if let Some(mut second_box) = replace(&mut first_box.tail, None) {
 first_box.tail = replace(&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() {}

• Zeta: *Checks name, double checks language*. Huh, another familiar face learning Rust :D.
• Petr: @Zeta Sorry about that, fixed. Now it should compile and without errors/warnings.

Answer 1

1. 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.

2. You don't need #![allow(dead_code)] and it's better to not disable warnings that broadly.

3. It's usual to import only the module, not the free function, and then namespace the function. For example, mem::replace.

4. mem::replace(&mut /* ... */, None) is equivalent to Option::take

5. 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<T> {
 list: Node<T>,
}
type Node<T> = Option<Box<Link<T>>>;
#[derive(Debug)]
struct Link<T> {
 head: T,
 tail: Node<T>,
}
impl<T> List<T> {
 pub fn push(&mut self, elem: T) {
 self.list = Some(Box::new(Link {
 head: elem,
 tail: self.list.take(),
 }));
 }
 pub fn pop(&mut self) -> Option<T> {
 match self.list.take() {
 Some(next_box) => {
 let next = *next_box;
 self.list = next.tail;
 Some(next.head)
 }
 _ => 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(&mut self) -> 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(&mut self, mut singleton: Box<Link<T>>) {
 singleton.tail = self.list.take();
 self.list = Some(singleton);
 }
 fn pop_singleton(&mut self) -> Node<T> {
 match self.list.take() {
 Some(mut next_box) => {
 self.list = next_box.tail.take();
 Some(next_box)
 }
 _ => None,
 }
 }
 // Otherwise the implementation is very similar to 'bubble' above.
 pub fn bubble2(&mut self) -> 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(&mut self) -> 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.