Ufdjrw

I've implemented my own version of a singly linked list in Rust as one of the challenges for me to learn it, and I'm satisfied with everything I have there except for the .pop() method. Using 2 while loops is very ugly and inefficient, but I found no other way to overcome the problem of setting the node at the index len() - 2 to None (popping the list), and using the data from the node at the index len() - 1 for the Some(data) return value (returns the element that was popped).

GitHub Link

pub struct SimpleLinkedList<T> 
 head: Option<Box<Node<T>>>,


struct Node<T> 
 data: T,
 next: Option<Box<Node<T>>>,


impl<T> Default for SimpleLinkedList<T> 
 fn default() -> Self 
 SimpleLinkedList head: None 
 


impl<T: Copy> Clone for SimpleLinkedList<T> 
 fn clone(&self) -> SimpleLinkedList<T> 
 let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
 let mut cur = &self.head;
 while let Some(node) = cur 
 cur = &node.next;
 out.push(node.data)
 
 out
 


impl<T> SimpleLinkedList<T> 
 pub fn new() -> Self 
 Default::default()
 

 pub fn len(&self) -> usize 
 let mut c = 0;
 let mut cur = &self.head;
 while let Some(node) = cur 
 cur = &node.next;
 c += 1;
 
 c
 

 pub fn is_empty(&self) -> bool 
 self.len() == 0
 

 pub fn push(&mut self, _element: T) 
 let mut cur = &mut self.head;
 match cur 
 Some(_) => 
 while let Some(node) = cur 
 cur = &mut node.next;
 
 
 None => (),
 
 *cur = Some(Box::from(Node 
 data: _element,
 next: None,
 ));
 

 pub fn pop(&mut self) -> Option<T>
 where
 T: Copy,
 
 let length = &self.len();
 let mut cur = &mut self.head;
 let mut out = None;
 match cur 
 Some(_) if *length > 1usize => 
 let mut c = 0usize;
 while let Some(node) = cur 
 cur = &mut node.next;
 if c >= length - 1 
 out = Some(node.data);
 break;
 
 c += 1;
 

 c = 0usize;
 cur = &mut self.head;
 while let Some(node) = cur 
 cur = &mut node.next;
 if c == length - 2 
 break;
 
 c += 1;
 
 
 Some(node) => out = Some(node.data),
 None => (),
 
 *cur = None;
 out
 

 pub fn peek(&self) -> Option<&T> 
 let cur = &self.head;
 match cur 
 Some(node) => Some(&node.data),
 None => None,
 
 


impl<T: Copy> SimpleLinkedList<T> 
 pub fn rev(&self) -> SimpleLinkedList<T> 
 let mut clone = self.clone();
 let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
 while let Some(val) = clone.pop() 
 out.push(val)
 
 out
 


impl<'a, T: Copy> From<&'a [T]> for SimpleLinkedList<T> 
 fn from(_item: &[T]) -> Self 
 let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
 for &e in _item.iter() 
 out.push(e);
 
 out
 


impl<T> Into<Vec<T>> for SimpleLinkedList<T> 
 fn into(self) -> Vec<T> 
 let mut out: Vec<T> = Vec::new();
 let mut cur = self.head;
 while let Some(node) = cur 
 cur = node.next;
 out.push(node.data)
 
 out
 

You can avoid re-traversing the list by keeping track of the last element you saw as you go (and then updating that at the end).

If you are naive about how you do that, you will run into trouble; your "previous" pointer retains ownership of the rest of the list and the borrow checker won't allow that. The trick is to break that link as you go - and to do that you can use the mem::replace function. Once you've done that, you have to put it back before you lose track of your previous node again.

Here's what that could look like in full (you'll have to forgive my liberal use of unwrap - I do think it makes things clearer):

pub fn pop(&mut self) -> Option<T>
 where T : Copy,

 use std::mem::replace;

 let curr = replace(&mut self.head, None);

 if curr.is_none() // list started off empty; nothing to pop
 return None;
 

 let mut curr = curr.unwrap(); // safe because of the check above

 if let None = curr.next // popped the last element
 return Some(curr.data);
 

 let mut prev_next = &mut self.head;

 while curr.next.is_some() 
 // Take ownership of the next element
 let nnext = replace(&mut curr.next, None).unwrap();

 // Update the previous element's "next" field
 *prev_next = Some(curr);

 // Progress to the next element
 curr = nnext;

 // Progress our pointer to the previous element's "next" field
 prev_next = &mut prev_next.as_mut().unwrap().next;

 

 return Some(curr.data);

As an aside, all this pointer shuffling simplifies a lot if you're willing to change the interface a little so that we return a "new" list each time (taking ownership in the pop function), or use a persistent datastructure, as they do in Learning Rust with entirely too many linked lists (already mentioned in a comment):

pub fn pop_replace(self) -> (Option<T>, Self) 
 // freely mutate self and all the nodes

Which you would use like:

let elem, list = list.pop();