5
\$\begingroup\$

I am still learning Rust and I think I have a long way to go. This question is from exercism.io. I am posting here to get some more reviews and suggestions to improve my code.

Linked list aren't a good data structure but they help to learn a programming language better.

I know I can use recursive calls for linked lists but that wouldn't be ideal since Rust doesn't do tail call optimizations.

I see two problems in my code

  1. Repetitive - At places I think I can use functional style to remove duplication.

  2. Irresponsible borrows and references - Use of box, reference and indirection are not clean. I had to figure out to reach a compilable code but it makes me feel queasy. Can I make this cleaner.

pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>
}

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


impl<T> SimpleLinkedList<T> {
    pub fn new() -> Self {
        SimpleLinkedList { head: None }
    }

    pub fn len(&self) -> usize {
        match &self.head {
            None => 0,
            Some(node) => {
                let mut current: &Node<T> = node;

                let mut length: usize = 1;
                while current.next.is_some() {
                    current = current.next.as_ref().unwrap();
                    length = length + 1;
                };
                length
            }
        }
    }

    pub fn push(&mut self, _element: T) {
        let next: Option<Box<Node<T>>> = self.head.take();
        let new_node = Some(Box::new(Node { data: _element, next: next }));
        self.head = new_node;
    }

    pub fn pop(&mut self) -> Option<T> {
        let head: Option<Box<Node<T>>> = self.head.take();
        head.map(|x| {
            self.head = x.next;
            x.data
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.data)
    }
}

impl<'a, T: Clone> From<&'a [T]> for SimpleLinkedList<T> {
    fn from(_item: &[T]) -> Self {
        let mut v = SimpleLinkedList::new();
        _item.iter().for_each(|x| v.push(x.clone()));
        v
    }
}

impl<T: Clone> SimpleLinkedList<T> {
    pub fn rev(&self) -> SimpleLinkedList<T> {
        let mut ret_val = SimpleLinkedList::new();
        match &self.head {
            Some(node) => {
                let mut current: &Node<T> = node;

                ret_val.push(current.data.clone());
                while current.next.is_some() {
                    current = current.next.as_ref().unwrap();
                    ret_val.push(current.data.clone());
                };
                ret_val
            }
            _ => ret_val,
        }
    }
}

impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
    fn into(self) -> Vec<T> {
        match self.head {
            Some(node) => {
                let mut v = Vec::new();
                let mut current: Node<T> = *node;

                v.push(current.data);
                while current.next.is_some() {
                    current = *current.next.unwrap();
                    v.push(current.data);
                }

                v.reverse();
                v
            }
            None => vec![]
        }
    }
}
\$\endgroup\$
1

2 Answers 2

Reset to default
3
\$\begingroup\$

Suggestion: add an iterator. This both brings your container more into line with a standard rust container and could be used in many or your methods:

  1. len() could be implemented as self.iter().count()
  2. rev() could be implemented as a for loop over self.iter()
  3. into() could collect() the iter to create the Vec<>.
\$\endgroup\$
0
3
\$\begingroup\$

As Winston said, adding an iterator will enable you to add quite a lot of functionality to this list quite easily. and can be done by wrapping your list in a tuple struct and implementing the desired traits - the Linked List Guide as recommended by lucarlig is a great resource and shows you how to do this

A couple of other things to think about:

  1. Think about adding a length: usize property to your struct that you update privately as nodes are pushed and popped, this allows you to do a constant time lookup of your list length. Your current method of finding the length of the list requires you to iterate over the whole thing, resulting in \$O(n)\$ time complexity for your length function which is quite inefficient.

  2. You could add a peek_mut() method quite easily to increase the functionality of the list, which is almost identical to your peek() method

  3. Implementing the 3 iterators (into_iter() -> Option<T>, iter() -> Option<&T>, iter_mut() -> Option<&mut T>) will give you very concise implementations of things like nth nth_mut (effectively retrieving a value at index x - although arguably if you needed to do that you shouldn't be using a linked list). And as Winston said, will also allow you to convert from a List<T> -> Vec<T> in one line - self.into_iter().collect()

  4. Your current implementation doesn't define a Drop method, so will use the default recursive version that Rust derives for you (I believe). So theoretically it's possible to hit the recursive depth limit. It would be safer to drop the list iteratively by implementing the drop trait with something like:

impl<T> Drop for SimpleLinkedList<T> {
    fn drop(&mut self) {
        while self.pop().is_some() {}
    }
}

  1. Where you've used while x.is_some() {} loops, I think you could instead use a while let loop which is more idiomatic - while let Some(data) = var { /* do something */ }.

  2. You can either match or .map Options which can allow you to make your code slightly more concise, ie. your push and pop implementations can use the same logic you've applied to your peek implementation

  3. Just from a code readability standpoint, the compiler can (I think) infer all of the types you've used within your code blocks, so they don't need to be explicitly stated. However if you much prefer including them then type aliases could be useful - type Link<T> = Option<Box<Node<T>>>; for example.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.