1 unstable release
Uses old Rust 2015
0.1.0 | Sep 14, 2018 |
---|
#4 in #middle
41KB
679 lines
indexlist
- A doubly linked list, backed by a vector.
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 elemnt in the middle of the list.
Safety
This crate uses #![deny(unsafe_code)]
to ensure everything is implemented
in 100% Safe Rust.
Generational indexes
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.
Performance
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.
Missing features
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!
No runtime deps
~180KB