LinkedVector is a 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.
rust, ignore
[dependencies]
linked-vector = "0.1"
Items in a LinkedVector are directly accessible via the HNode struct. These
are returned by operations such as insert or push operations. If direct access
is required to any specific items, their handles can be stored for later use.
Internally, a handle is an index into the vector that holds the nodes. Care
should be taken to avoid using the handles from one LinkedVector with another
instance. For the debug builds, handles are checked to ensure they are "native"
to the LinkedVector they're passed to when calling its methods. This can help
catch errors in unit tests. This checking is not done when built in release
node.
For debug builds handles have a UUID field used to ensure the LinkedVector
they're used with belong to it. For release build, the UUID field is not present
and this checking isn't done. For release, handles are transparent usize
indexes.
```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.
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.
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.insertafter(h2, 42); lv.removenode(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 linked_vector::*; let lv = LinkedVector::from([1, 2, 3, 4, 5, 6, 7]); let mut cursor = lv.cursor();
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 vie 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)); ```