Rust Uni-Directional Linked List Using Box<T> Not Rc<T>
modified: 2015-04-16 22:44:39

Scroll to the bottom for a commentary:

    extern crate core;

    use std::vec::Vec;
    use core::kinds::marker::NoCopy;

    struct LLItem<T> {
        child:      Option<Box<LLItem<T>>>,
        item:       T

    struct LinkList<T> {
        _root:       Option<Box<LLItem<T>>>

    enum AfterWhat<'lt, T: 'lt> {
        After(& 'lt mut LLItem<T>),
        AnyWhere(& 'lt mut LinkList<T>),

    impl<T> LLItem<T> {
        //LinkList::add(After(&mut **l.root.unwrap().child.as_mut().unwrap()), 3u);
        fn next_mut_ref(&mut self) -> &mut LLItem<T> {
            &mut **self.child.as_mut().unwrap()

    impl<T> LinkList<T> {
        fn new() -> LinkList<T> {
            LinkList { _root: None }
        fn root(&mut self) -> &mut LLItem<T> {
            &mut **self._root.as_mut().unwrap()

        fn add(after: AfterWhat<T>, item: T) {
            match after {
                AfterWhat::After(_after) => {
                    let mut nitem: LLItem<T> = LLItem { child: None, item: item };
                    std::mem::swap(&mut nitem.child, &mut _after.child);
                    _after.child = Some(box nitem);
                AfterWhat::AnyWhere(linklist) => {
                    if linklist._root.is_none() {
                        linklist._root = Some(box LLItem { child: None, item: item });
                    // it really does not matter what root is because the caller
                    // did to specify what to insert after so we insert as the
                    // root of the list and move the current root as it's child
                    let mut nitem: LLItem<T> = LLItem { child: None, item: item };
                    std::mem::swap(&mut linklist._root, &mut nitem.child);
                    linklist._root = Some(box nitem);

    fn main() {
        let mut l: LinkList<uint> = LinkList::new();
        LinkList::add(AfterWhat::AnyWhere(&mut l), 0u);
        LinkList::add(AfterWhat::AnyWhere(&mut l), 1u);
        LinkList::add(AfterWhat::AnyWhere(&mut l), 2u);
        LinkList::add(AfterWhat::After(l.root()), 3u);
        LinkList::add(AfterWhat::After(l.root().next_mut_ref()), 3u);

What is really nice is the easy ability to call the static method add with either the LinkList structure and have the item added anywhere, or add the new item after a specific element. Also, each link list item has the method next_mut_ref() which gives you the mutable reference to the next item which allows for easy passing into the AfterWhat enumeration which is passed into the static method add.