enum List<T> {
    Node (T, Box<List<T>>),
    End
}

impl<T> List<T> {
    fn new() -> List<T> {
        List::End
    }

    fn len(&self) -> usize {
        match *self {
            List::Node(_, ref next) => 1 + next.len(),
            List::End => 0,
        }
    }

    fn push(self, value: T) -> List<T> {
        List::Node(value, Box::new(self))
    }

    fn pop(self) -> (Option<T>, List<T>) {
        match self {
            List::Node(value, next) => (Some(value), *next),
            List::End => (None, List::End),
        }
    }

    fn get(&self, index: usize) -> Option<&T> {
        match (self, index) {
            (&List::Node(ref value, _), 0) => Some(value),
            (&List::Node(_, ref next), index) => next.get(index - 1),
            (&List::End, _) => None,
        }
    }

    fn set(&mut self, index: usize, new_value: T) -> Option<&T> {
        match (self, index) {
            (&mut List::Node(ref mut value, _), 0) => {
                *value = new_value;
                Some(value)
            },
            (&mut List::Node(_, ref mut next), index) => next.set(index - 1, new_value),
            (&mut List::End, _) => None,
        }
    }

    fn insert(self, index: usize, value: T) -> List<T> {
        match (self, index) {
            (tail, 0) => List::Node(value, Box::new(tail)),
            (List::Node(node_value, next), index) => {
                List::Node(
                    node_value,
                    Box::new(next.insert(index - 1, value))
                )
            },
            (List::End, _) => List::End,
        }
    }

    fn value(&self) -> Option<&T> {
        match *self {
            List::Node(ref value, _) => Some(value),
            List::End => None
        }
    }

}