Expand description
§array_list
array_list is a Rust crate that implements an unrolled linked list with features that
combine the simplicity of a Vec and the flexibility of a LinkedList.
The underlying linked list is built using a XOR linked list. This design requires only a single pointer for bidirectional traversal, making it more memory-efficient compared to a traditional doubly linked list, which requires two pointers per node.
§Features
- Efficient traversal in both directions with minimal memory overhead.
- Chunked storage for elements (unrolled list), which improves cache locality and reduces pointer overhead compared to traditional linked lists.
- Dynamic growth, striking a balance between
VecandLinkedListperformance characteristics.
§Use Cases
array_list is ideal for scenarios where:
- You require frequent insertions and deletions in the middle of the list.
- Memory efficiency is crucial, and you want to minimize pointer overhead.
- Improved cache performance over a standard linked list is desired.
§Note
This crate is not related to Java’s ArrayList despite its name.
The design and functionality are entirely tailored to Rust’s ecosystem.
§Example
use array_list::ArrayList;
let mut list: ArrayList<i64, 6> = ArrayList::new();
list.push_back(1);
list.push_back(2);
list.push_front(0);
assert_eq!(list.pop_back(), Some(2));
assert_eq!(list.pop_front(), Some(0));