Expand description
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!
§Examples
Creating a list, appending nodes, and printing them out:
extern crate indexlist;
use indexlist::IndexList;
let mut list = IndexList::new();
list.push_back(5);
list.push_back(10);
list.push_back(15);
// This prints 5, 10, and then 15, each on its own line
for element in list.iter() {
println!("{}", element);
}Removing an item from the list:
extern crate indexlist;
use indexlist::IndexList;
let mut list = IndexList::new();
let five = list.push_back(5);
list.push_back(10);
list.remove(five);
// 5 is no longer in the list
assert!(list.get(five).is_none());Generational indexes:
extern crate indexlist;
use indexlist::IndexList;
let mut list = IndexList::new();
let five = list.push_back(5);
list.push_back(10);
list.remove(five);
// since we have a free spot, this will go where 5 was
list.push_back(15);
// our index is out of date, and so will not return 15 here
assert!(list.get(five).is_none());