Linked list in rust, Needed optimization

Question

I've implemented constructor, push , pop, drop and some macro.

I need to know if the drop implementation is correct and is drop is really necessary?

Meanwhile I still didn't check about std::rc::Rc and lifetime implementations.

use std::mem;
#[derive(Debug, PartialEq)]
pub struct LinkedList<T> {
 head: Option<Box<Node<T>>>,
}
#[derive(Debug, PartialEq, Clone)]
struct Node<T> {
 value: T,
 next: Option<Box<Node<T>>>,
}
impl<T> LinkedList<T> {
 pub fn new() -> LinkedList<T> {
 
 let new: LinkedList<T> = LinkedList {
 head: None,
 };
 new
 }
 pub fn push(&mut self, value: T) {
 let new_tail: Node<T> = Node { value, next: None };
 let mut ptr = &mut self.head;
 loop {
 match ptr {
 None => {
 *ptr = Some(Box::new(new_tail));
 break;
 }
 Some(node) => {
 ptr = &mut node.next;
 }
 }
 }
 }
 pub fn pop(&mut self) -> Option<T>
 where
 T: Copy,
 {
 let mut ptr = &mut self.head;
 loop {
 match ptr {
 None => {
 return None;
 }
 Some(node) if node.next.is_none() => {
 let val = node.value;
 *ptr = None;
 return Some(val);
 }
 Some(node) => {
 ptr = &mut node.next;
 }
 }
 }
 }
 pub fn drop(&mut self) {
 let mut ptr=mem::replace(&mut self.head, None);
 while let Some(mut node) = ptr {
 ptr=mem::replace(&mut node.next, None);
 }
 }
 pub fn get_tail(&mut self)-> Option<&mut Node<T>>{
 let mut ptr=&mut self.head;
 loop {
 
 
 match ptr.as_mut() {
 None=>{
 return None;
 },
 Some(node) if(node.next.is_none()) =>{
 return Some(node)
 
 },
 Some(node) =>{
 ptr=&mut node.next;
 }
 }
 }
 
 }
}
#[macro_export]
macro_rules! linkedlist {
 ( $( $x:expr ),* ) => {
 {
 let mut temp_vec = LinkedList::new();
 $(
 temp_vec.push($x);
 )*
 temp_vec
 }
 };
}
#[cfg(test)]
mod test {
 use super::*;
 #[test]
 fn create_test() {
 let new_linked_list: LinkedList<i32> = LinkedList::new();
 println!("{:?}", new_linked_list);
 }
 #[test]
 fn push() {
 let mut new_linked_list: LinkedList<i32> = LinkedList::new();
 new_linked_list.push(1);
 new_linked_list.push(2);
 new_linked_list.push(3);
 println!(" push {:?}", new_linked_list);
 let popped = new_linked_list.pop();
 println!("popped {:?} ", popped);
 println!("array {:?}", new_linked_list);
 }
 #[test]
 fn get_tail(){
 let mut new_linked_list: LinkedList<i32> = LinkedList::new();
 new_linked_list.push(1);
 new_linked_list.push(2);
 new_linked_list.push(3);
 println!("{:?}",new_linked_list.get_tail());
 }
 #[test]
 fn macro_test() {
 let ll=linkedlist!(5,6,7,8);
 println!("{:?}",ll);
 }
}

I just did this on a Sunday afternoon, and I'm surprised this even works. Hence, I need to know how can I better implement and optimize this code. Does my code cause any issues?

• Davislor: You could simplify this code by having only the node type. A separate type for the list would make sense if you made it a doubly-linked list (with weak references backwards).

Answer 1

The code already looks pretty good. Nonetheless here are some issues I have with it:

The code as given does not compile on my system. To compile a binary, there's a main() function missing. To compile a library, you have to make Node public, since you return it from a public function of a public struct.

This

 pub fn new() -> LinkedList<T> {
 
 let new: LinkedList<T> = LinkedList {
 head: None,
 };
 new
 }

can be written as

 pub fn new() -> Self {
 Self {
 head: None,
 }
 }

This way, you don't need to repeat the name of the struct in the return type and constructor call and you can also spare a local variable.

Also consider running rustfmt on your sources, so that your code has the recommended formatting to be easier to read for other Rust developers.

If I understand it correctly, the drop() function should free the memory of the LinkedList. This is not necessary, since all members of the involved structures use managed memory already. So just dropping the owner of the LinkedList out of scope will free all related memory automatically.