Linked List in Rust

lib.rs

#![deny(missing_docs)]

//! A simple, mutable, single-linked list implementation,
//! following the tutorial [Learning Rust with entirely too many linked lists](http://cglab.ca/~abeinges/blah/too-many-lists/book/README.html),
//! updated for "modern" iterator implementation using traits

/// A mutable, singly linked list
#[derive(Default)]
pub struct List<T> {
    head: Link<T>
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>
}

/// Iterator for List
pub struct Iter<'a, T> {
    next_elem: Option<&'a Node<T>>
}

/// Mutable Iterator for list
pub struct MutIter<'a, T> {
    next_elem: Option<&'a mut Node<T>>
}

impl<'a, T> List<T> {
    /// creates a new, empty linked list
    pub fn new() -> Self {
        List { head: None }
    }

    /// pushes an element `e` onto the list
    pub fn push(&mut self, e: T) {
        let node = Box::new(Node {
            elem: e,
            next: self.head.take()
        });
        self.head = Some(node);
    }

    /// pops the list's head
    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            let node = *node;
            self.head = node.next;
            node.elem
        })
    }

    /// peeks the list
    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }

    /// peeks the list mutably
    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| &mut node.elem)
    }

    /// get Iterator for List
    pub fn iter(&self) -> Iter<T> {
        Iter { next_elem: self.head.as_ref().map(|node| &**node) }
    }

    /// get mut Iterator for List
    pub fn iter_mut(&mut self) -> MutIter<T> {
        MutIter { next_elem: self.head.as_mut().map(|node| &mut **node) }
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

impl<T> Iterator for List<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.pop()
    }
}

impl<'a, T> IntoIterator for &'a List<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next_elem.map(|node| {
            self.next_elem = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

impl<'a, T> Iterator for MutIter<'a, T> {
    type Item = &'a mut T;
    
    fn next(&mut self) -> Option<Self::Item> {
        self.next_elem.take().map(|node| {
            self.next_elem = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

#[cfg(test)]
mod tests {
    use super::List;

    #[test]
    fn basics() {
        let mut l = List::new();
        assert_eq!(l.pop(), None);

        l.push("a");
        l.push("b");
        assert_eq!(l.peek(), Some(&"b"));
        assert_eq!(l.peek_mut(), Some(&mut "b"));
        assert_eq!(l.pop(), Some("b"));
        assert_eq!(l.pop(), Some("a"));
        assert_eq!(l.peek(), None);
        assert_eq!(l.peek_mut(), None);

        l.push("c");
        assert_eq!(l.peek(), Some(&"c"));
        assert_eq!(l.pop(), Some("c"));
        assert_eq!(l.pop(), None);
    }

    #[test]
    fn iterators () {
        // setup
        let mut l = List::new();
        l.push(1);
        l.push(2);
        l.push(3);
        l.push(4);

        // plain vanilla & iter
        let inc: Vec<_> = l.iter().map(|e| e + 1).collect();
        assert_eq!(inc, vec![5,4,3,2]);

        // plain vanilla & iter, created through into_iter()
        let inc2: Vec<_> = (&l).into_iter().map(|e| e + 1).collect();
        assert_eq!(inc2, vec![5,4,3,2]);

        let mut l2 = List::new();
        l2.push("a".to_string());
        l2.push("b".to_string());
        l2.push("c".to_string());
        assert_eq!(l2.iter().collect::<Vec<_>>(), vec!["c", "b", "a"]);

        // &mut iter
        l2.iter_mut().for_each(|e| *e = "q".to_string());
        assert_eq!(l2.iter().collect::<Vec<_>>(), vec!["q", "q", "q"]);

        // into_iter() with &
        for e in &l2 {
            assert_eq!(e, "q");
        }

        // into_iter with &mut
        for e in &mut l2 {
            assert_eq!(e, "q");
        }

        // into_iter with move
        for e in l2 {
            assert_eq!(e, "q");
        }
    }
}

// Notes: If this was more complicated, we would have needed custom iterators for List, something like this:

// /// IntoIter for List
// pub struct IntoIter<T>(List<T>);

// impl<T> IntoIterator for List<T> {
//     type Item = T;
//     type IntoIter = IntoIter<T>;

//     fn into_iter(self) -> Self::IntoIter {
//         IntoIter(self)
//     }
// }

// impl<T> Iterator for IntoIter<T> {
//     type Item = T;

//     fn next(&mut self) -> Option<Self::Item> {
//         self.0.pop()
//     }
// }

// impl<'a, T> IntoIterator for &'a mut List<T> {
//     type Item = &'a mut T;
//     type IntoIter = MutIter<'a, T>;

//     fn into_iter(self) -> Self::IntoIter {
//         self.iter_mut()
//     }
// }