yeah, it's a linked list with indices in a vector

vectorlinkedlist.rs

#[derive(Debug)]
pub struct IndexList<T> {
    contents: Vec<Option<Entry<T>>>,
}

#[derive(Debug)]
pub struct Entry<T> {
    item: T,
    next: Option<usize>,
    prev: Option<usize>,
}

impl<T> IndexList<T> {
    pub fn new() -> IndexList<T> {
        IndexList {
            contents: Vec::new(),
        }
    }

    pub fn push_back(&mut self, item: T) {
        let next_index = self.contents.len();

        let prev = if next_index == 0 {
            None
        } else {
            self.contents[next_index - 1]
                .as_mut()
                .map(|e| e.next = Some(next_index));

            Some(next_index - 1)
        };

        self.contents.push(Some(Entry {
            item,
            next: None,
            prev,
        }));
    }
}

impl<T> IndexList<T>
where
    T: PartialEq,
{
    pub fn contains(&self, value: &T) -> bool {
        self.get(value).is_some()
    }

    pub fn get(&self, value: &T) -> Option<&Entry<T>> {
        let f = self.contents.iter().find(|e| match e {
            Some(e) => &e.item == value,
            None => false,
        });

        match f {
            Some(e) => e.as_ref(),
            None => None,
        }
    }

    pub fn remove(&mut self, value: &T) -> Option<Entry<T>> {
        // we want to do just get, but then we run into borrowing issues.
        //
        // we could implement Entry, but... ugh. So let's fetch just the indexes for now.

        let (prev, index, next) = {
            let f = self.contents.iter().enumerate().find(|(_, e)| match e {
                Some(e) => &e.item == value,
                None => false,
            })?;

            let index = f.0;
            // if the item is None then we have serious problems, so blow up
            let entry = f.1.as_ref().unwrap();

            let prev = entry.prev;
            let next = entry.next;

            (prev, index, next)
        };

        // do we need to fix up the previous element?
        if let Some(index) = prev {
            // if the previous is None, we have a problem, so blow up
            let prev = self.contents[index].as_mut().unwrap();

            // do we have a next to fix it up with?
            if let Some(index) = next {
                prev.next = Some(index);
            }
        }

        // do we need to fix up the next element?
        if let Some(index) = next {
            // if the next is None, we have a problem, so blow up
            let next = self.contents[index].as_mut().unwrap();

            // do we have a prev to fix it up with?
            if let Some(index) = prev {
                next.prev = Some(index);
            }
        }

        // finally, remove the element
        self.contents[index] = None;

        None
    }
}

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

    #[test]
    fn create_list() {
        let _list: IndexList<i32> = IndexList::new();
    }

    #[test]
    fn push_back() {
        let mut list = IndexList::new();

        list.push_back(5);
    }

    #[test]
    fn contains() {
        let mut list = IndexList::new();

        list.push_back(5);

        assert!(list.contains(&5));
    }

    #[test]
    fn get() {
        let mut list = IndexList::new();

        list.push_back(5);

        let entry = list.get(&5);

        assert!(entry.is_some());

        let entry = entry.unwrap();

        assert_eq!(entry.item, 5);
        assert!(entry.next.is_none());
        assert!(entry.prev.is_none());
    }

    #[test]
    fn push_back_twice() {
        let mut list = IndexList::new();

        list.push_back(5);
        list.push_back(10);

        let five = list.get(&5).unwrap();

        assert!(five.next.is_some());

        let index = five.next.unwrap();
        assert_eq!(list.contents[index].as_ref().unwrap().item, 10);

        let ten = list.get(&10);

        assert!(ten.is_some());

        let ten = ten.unwrap();

        assert_eq!(ten.item, 10);
        assert!(ten.next.is_none());
        assert!(ten.prev.is_some());

        let index = ten.prev.unwrap();
        assert_eq!(list.contents[index].as_ref().unwrap().item, 5);
    }

    #[test]
    fn push_back_thrice() {
        let mut list = IndexList::new();

        list.push_back(5);
        list.push_back(10);
        list.push_back(15);

        let ten = list.get(&10).unwrap();

        assert!(ten.next.is_some());

        let index = ten.next.unwrap();
        assert_eq!(list.contents[index].as_ref().unwrap().item, 15);

        let fifteen = list.get(&15);

        assert!(fifteen.is_some());

        let fifteen = fifteen.unwrap();

        assert_eq!(fifteen.item, 15);
        assert!(fifteen.next.is_none());
        assert!(fifteen.prev.is_some());

        let index = fifteen.prev.unwrap();
        assert_eq!(list.contents[index].as_ref().unwrap().item, 10);
    }

    #[test]
    fn remove() {
        let mut list = IndexList::new();

        list.push_back(5);
        list.push_back(10);
        list.push_back(15);

        // we want to check that we removed ten, so we have to save its index
        // we get the index by checking the next of five
        let ten_index = list.get(&5).unwrap().next.unwrap();

        list.remove(&10);

        assert!(list.contents[ten_index].as_ref().is_none());

        let five = list.get(&5).unwrap();

        assert!(five.next.is_some());

        let index = five.next.unwrap();
        assert_eq!(list.contents[index].as_ref().unwrap().item, 15);

        let fifteen = list.get(&15).unwrap();

        assert!(fifteen.prev.is_some());

        let index = fifteen.prev.unwrap();
        assert_eq!(list.contents[index].as_ref().unwrap().item, 5);
    }

    #[test]
    fn remove_returns_none_when_not_there() {
        let mut list = IndexList::new();

        assert!(list.remove(&5).is_none());
    }
}