matthewdowney · April 5, 2025 21:33 · Apr 5, 2025
diff --git a/doubly_linked_list.rs b/doubly_linked_list.rs
@@ -0,0 +1,179 @@
+/// 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(())
+    }
+}