ArrayLinkedList

A hybrid data structure combining the benefits of arrays and linked lists, with O(1) indexed access, insertions, and deletions.

Features

• O(1) Operations: Insert/remove at ends, access by index, and replace elements
• Stable Indices: Indices remain valid after insertions/deletions
• Cache-Friendly: Contiguous memory layout for better performance
• Space Efficient: Reuses empty slots automatically
• Iterators: Bidirectional iteration with rev(), and partial iteration via iter_after()/iter_before()

Comparison

*Amortized | †Requires slot reuse logic

Example

use array_linked_list::ArrayLinkedList;

let mut list = ArrayLinkedList::new();

// Add elements
let idx1 = list.push_front(10); // Index 0
let idx2 = list.push_back(20); // Index 1
let idx3 = list.push_front(30); // Index 2

// Access by index
assert_eq!(list[idx1], Some(10));
assert_eq!(list[idx2], Some(20));
assert_eq!(list[idx3], Some(30));

// Iterate in logical order
let items: Vec<_> = list.iter().copied().collect();
assert_eq!(items, [30, 10, 20]);

// Replace elements while maintaining indices and moving the new element to the logical front
list.replace_front(idx2, 99).unwrap();
assert_eq!(list.iter().copied().collect::<Vec<_>>(), [99, 30, 10]);

// Iterate with indices
for (idx, val) in list.indexed() {
    println!("Index {idx}: {val}");
}

// Partial iteration
let after_30: Vec<_> = list.iter_before(idx1).copied().collect();
assert_eq!(after_30, vec![99, 30]);