array-linked-list 0.2.1

A data structure, which combines the advantages of dynamic arrays and linked lists
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# ArrayLinkedList

[![Crates.io](https://img.shields.io/crates/v/array-linked-list)](https://crates.io/crates/array-linked-list)
[![Docs.rs](https://docs.rs/array-linked-list/badge.svg)](https://docs.rs/array-linked-list)
[![CI](https://gitlab.com/porky11/array-linked-list/actions/workflows/rust.yml/badge.svg)](https://github.com/porky11/array-linked-list/actions)

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

| Operation          | `ArrayLinkedList` | `Vec` | `LinkedList` | `Vec<Option<T>>` |
|--------------------|-------------------|-------|--------------|------------------|
| Push/Pop Front     | O(1)              | O(n)* | O(1)         | O(1)†            |
| Push/Pop Back      | O(1)              | O(1)  | O(1)         | O(1)             |
| Remove by Index    | O(1)              | O(n)* | O(n)         | O(1)†            |
| Cache Locality     | ✅                | ✅    | ❌           | ✅               |
| Stable Indices     | ✅                | ❌    | ❌           | ❌               |

_*Amortized | †Requires slot reuse logic_

## Example

```rust
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]);
```