Crate indexlist[−][src]

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());

Structs

Index	A reference to an element in the list.
IndexList	A doubly linked list, backed by a vector.