LinkedVector is a feature packed hybrid of a vector and linked list. Items are
accessible directly in O(1) time, and insertions and deletions also operate in
O(1) time. Internally, nodes exist within a vector, with each node holding
handles to its previous and next neighbors. So there's no shifting of data when
items are inserted or removed.
An example project that demonstrates
use of the linked-vector crate is available. The project is for a Least
Frequently Used Cache. LinkedVector's are used to implement its frequency
count queues.
The current release v1.1.0 is a backward compatible minor revision to
v1.0.0. More functionality is added to LinkedVector and minor changes to
Cursor have been implemented; see the change log link below for details.
Versioning Conventions: - MAJOR version indicates incompatible API changes with previous major version. - MINOR version indicates added functionality in a backwards-compatible manner. - PATCH version indicates backwards-compatible bug fixes.
Edit your Cargo.toml file to include:
rust, ignore
[dependencies]
linked-vector = "1.1"
Or run this on the command line from your project folder:
console, ignore
cargo add linked-vector
Items in a LinkedVector are directly accessible via handles, which are
instances of the HNode struct. These are returned by operations such as insert
or push, or other accessor methods. If direct access is required to any specific
items, their handles can be stored for later use. These handles lack the
performance overhead of smart pointers, while providing a flexible reference
model.
```rust use linked_vector::*; let mut lv = LinkedVector::new();
let handle1 = lv.pushback(1); let handle2 = lv.pushback(2);
*lv.getmut(handle1).unwrap() = 42; lv[handle_2] = 99;
asserteq!(lv[handle1], 42); asserteq!(lv[handle2], 99);
```
Nodes within LinkedVector are added to a recycling list when they're popped,
or otherwise removed. If a LinkedVector has any nodes in this list, one will
be used for the next insert or push operation. This strategy avoids segmenting
the vector with dead vector cells. When a node is added to the recycling list,
it isn't moved in the vector - its next and previous fields are updated to link
it into the recycling list.
For release builds, the checks described in this section are excluded to ensure
fast performance. In release, handles are simply transparent usize indexes
into the LinkedVector's internal vector.
When run with the debug build, handles have additional fields added: a UUID
field, and a generation ID. The UUID field is used to verify handles are native
to the LinkedVector they're passed to. And the generation ID is used to detect
expired handles.
These features should help ensure that projects that use this crate don't have elusive bugs in scenarios such as passing an old handle to a vector for a node that had been popped earlier, or obtaining a handle from one vector and accidentally passing it to another.
LinkedVector's struct is implemented in a minimalistic manner. It contains
only 4 fields: one for the internal vector, another that holds a handle to the
head node, another with a handle to the recycling list, and lastly the length
field.
There are no dummy nodes in the vector - all active nodes are data, and there's
no field in the LinkedVector struct for a tail handle, although the vector
does indeed have a tial node accessible in O(1) time.
Index<HNode> and Index<usize> are implemented, enabling
items to be accessed directly.O(n log n) time.Operations that alter the LinkedVector return handles that can be saved for
later use. These provide direct access to items in O(1) time.
```rust use linked_vector::*; let mut lv = LinkedVector::new();
let h1 = lv.pushback(1); let h2 = lv.pushback(2); let h3 = lv.pushback(3); let h4 = lv.insertafter(h1, 4);
lv.insert_after(h2, 42); lv.remove(h1);
asserteq!(lv.front(), Some(&4)); asserteq!(lv.to_vec(), vec![4, 2, 42, 3]);
```
A cursor can be requested from the LinkedVector to facilitate traversal of
nodes. Using a handle to specify starting position, cursors can be set to the
location within the vector accordingly. They can move one position at a time,
or several via forward(n_times) and backward(n_ntimes).
```rust use linkedvector::*; let lv = LinkedVector::from([1, 2, 3, 4, 5, 6, 7]); let hfront = lv.frontnode().unwrap();
let mut cursor = lv.cursor(hfront);
assert_eq!(cursor.get(), Some(&1));
cursor.move_next();
assert_eq!(cursor.get(), Some(&2));
let hend = cursor.movetoend().unwrap(); let hbak = cursor.backward(3).unwrap();
asserteq!(cursor.get(), Some(&4)); asserteq!(lv.get(hend), Some(&7)); assert_eq!(lv.get(hbak), Some(&4)); ```
LinkedVector implements the standard set of double-ended iterators. They can
be instantiated directly via methods such as iter(), or implicitly.
```rust use linked_vector::*; let mut lv1 = LinkedVector::from([1, 2, 3]);
lv1.itermut().zip(7..).foreach(|(a, b)| *a = b); lv1.iter().zip(7..).foreach(|(a, b)| asserteq!(a, &b));
for (v1, v2) in (10..).zip(&mut lv1) { *v2 = v1; } lv1.iter().zip(10..).foreach(|(a, b)| asserteq!(a, &b)); ```