Doubly linked list in Rust

doubly_linked_list.rs

/// Doubly-linked list that, instead of pointers, uses handles, which are indices
/// into an object pool.
struct LinkedList<T> {
    head: Option<LinkedListNodeHandle>,
    tail: Option<LinkedListNodeHandle>,
    pool: ObjectPool<LinkedListNode<T>>,
}

struct LinkedListNode<T> {
    data: T,
    prev: Option<LinkedListNodeHandle>,
    next: Option<LinkedListNodeHandle>,
}

impl<T> LinkedListNode<T> {
    fn new(value: T) -> LinkedListNode<T> {
        LinkedListNode { data: value, prev: None, next: None, }
    }
}

type LinkedListNodeHandle = usize;

/// Object pool is just a wrapper around a vec + another vec of objects which are free
/// to reuse. Pool never resizes, meaning memory use is equal to the max number of live
/// objects at any given time.
struct ObjectPool<T> {
    /// All allocated memory
    objects: Vec<T>,
    /// Indices of unused objects in memory
    freed: Vec<LinkedListNodeHandle>
}

impl<T> ObjectPool<T> {
    fn new() -> ObjectPool<T> {
        ObjectPool { objects: Vec::new(), freed: Vec::new(), }
    }

    /// Move [value] into the object pool and return a handle
    fn allocate(&mut self, value: T) -> LinkedListNodeHandle {
        let handle = self.objects.len();
        self.objects.push(value);
        handle
    }

    /// Call when [handle] is no longer in use (honor system!)
    fn free(&mut self, handle: LinkedListNodeHandle) { self.freed.push(handle); }

    /// Return the first available handle, if any
    fn reuse_freed(&mut self) -> Option<LinkedListNodeHandle> { self.freed.pop() }
}

impl<T> LinkedList<T> {
    fn new() -> LinkedList<T> {
        LinkedList {
            head: None,
            tail: None,
            pool: ObjectPool::new(),
        }
    }

    /// Append an object to the end of the list
    fn push_back(&mut self, value: T) -> LinkedListNodeHandle {
        // Create or reuse a node from the pool
        let node_handle = match self.pool.reuse_freed() {
            Some(h) => {
                self.pool.objects[h].data = value;
                h
            },
            None => self.pool.allocate(LinkedListNode::new(value)),
        };

        // Either append to the tail or set the new node as the head and tail
        match self.tail {
            None => {
                self.head = Some(node_handle);
                self.tail = Some(node_handle);
            },
            Some(tail_node_handle) => {
                // Link with the current tail node
                self.pool.objects[node_handle].prev = Some(tail_node_handle);
                self.pool.objects[tail_node_handle].next = Some(node_handle);

                // Replace the tail handle in the list structure
                self.tail = Some(node_handle);
            }
        }

        // Return the handle so the caller can reference it
        node_handle
    }

    /// Remove a node from the list by its [handle]
    fn remove(&mut self, handle: LinkedListNodeHandle) {
        // Node the handle refers to
        let node = &self.pool.objects[handle];

        // Update the head and tail if necessary
        if self.head.expect("cannot remove from empty list") == handle {
            self.head = node.next;
        }
        if self.tail.expect("ditto") == handle {
            self.tail = node.prev;
        }

        // Unlink
        let (prev, next) = (node.prev, node.next);
        match prev {
            Some(h) => self.pool.objects[h].next = next,
            _ => (),
        }
        match next {
            Some(h) => self.pool.objects[h].prev = prev,
            _ => (),
        }

        // Free
        self.pool.objects[handle].next = None;
        self.pool.objects[handle].prev = None;
        self.pool.free(handle);
    }

    fn iter(&self) -> LinkedListIterator<T> {
        LinkedListIterator {
            list: self,
            node: self.head,
        }
    }
}

// I read this to figure out iterators: https://aloso.github.io/2021/03/09/creating-an-iterator
struct LinkedListIterator<'a, T> {
    list: &'a LinkedList<T>,
    node: Option<LinkedListNodeHandle>
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(node_handle) = self.node {
            self.node = self.list.pool.objects[node_handle].next;
            return Some(&self.list.pool.objects[node_handle].data);
        }
        None
    }
}

#[cfg(test)]
mod tests {
    use std::fmt::Error;
    use std::fmt::Write;
    use super::*;

    #[test]
    fn test_linked_list() -> Result<(), Error> {
        // Create a list with a few references types.
        let mut l: LinkedList<&str> = LinkedList::new();
        let _node1 = l.push_back("hi");
        let node2 = l.push_back("there");
        let _node3 = l.push_back("world");

        // Check that the list contains the words
        let mut out = String::new();
        for (i, &x) in l.iter().enumerate() {
            writeln!(out, "{}: {}", i, x)?;
        }
        assert_eq!(out, "0: hi\n1: there\n2: world\n");

        // Delete the middle word and check again
        l.remove(node2);
        let mut out = String::new();
        for (i, &x) in l.iter().enumerate() {
            writeln!(out, "{}: {}", i, x)?;
        }
        assert_eq!(out, "0: hi\n1: world\n");

        Ok(())
    }
}