This crate provides a struct, IndexList<T>, which is a doubly-linked
list. However, unlike a traditional linked list, which heap allocates
each of its nodes individually, all nodes are stored in a vector. Rather
than provide pointers to nodes, an Index struct can be used to access
a particular element in the middle of the list.
This crate uses #![deny(unsafe_code)] to ensure everything is implemented
in 100% Safe Rust.
Index uses a generations scheme, so that if you hold an Index to a node,
and it's removed, and a new node is allocated in its place, you do not access
the new node.
In general, performance is quite good. Benchmarks against the standard library's
LinkedList<T> are provided. But some other details:
- The list keeps track of its head and tail for efficient insertion.
- The underlying vector only grows, never shrinks. When a node is removed, its entry is marked as free for future insertions.
- Free entries are themselves kept as a singly-linked list, meaning that they can be re-used efficiently.
Right now, I've only implemented a minimal number of features; there's iter
but no into_iter and iter_mut. This is on the to-do list. PRs welcome!