Crate array_list 

array_list

array_list provides an ordered collection backed by fixed-capacity chunks. It offers sequence operations, iterators, and cursors while avoiding one allocation per element.

Features

• Ordered sequence with index-based element access.
• Chunked storage with less per-element pointer overhead than a traditional linked list.
• Shared, mutable, and owning iterators.
• Cursor and mutable cursor APIs for moving around the list and editing near the cursor.
• #![no_std] support with alloc.

Quick Start

use array_list::ArrayList;

let mut list: ArrayList<i32, 8> = ArrayList::from([1, 2, 4]);

list.insert(2, 3);
list.push_front(0);
list.push_back(5);

assert_eq!(list, [0, 1, 2, 3, 4, 5]);

for value in &mut list {
    *value *= 2;
}

assert_eq!(list.iter().copied().collect::<Vec<_>>(), [0, 2, 4, 6, 8, 10]);

When To Use It

array_list is useful when you want an ordered sequence that supports indexed access, stable iteration order, and cursor-local edits without allocating one node per element.

It is not a drop-in replacement for Vec. Index lookup may need to scan chunks when the list is not densely packed, and insertions/removals inside a chunk can move elements within that chunk.

Use Vec when you primarily push/pop at the back and need dense contiguous storage. Use ArrayList when cursor-local edits and chunked growth are a better fit than a single contiguous allocation. Use LinkedList only when its exact node-based semantics are required.

API Overview

• Build lists with ArrayList::new, ArrayList::from, collect, extend, or ArrayList::append.
• Edit at the ends with ArrayList::push_front, ArrayList::push_back, ArrayList::pop_front, and ArrayList::pop_back.
• Edit by index with ArrayList::insert, ArrayList::remove, ArrayList::get, and ArrayList::get_mut.
• Traverse with ArrayList::iter, ArrayList::iter_mut, IntoIter, or the IntoIterator implementations for ArrayList, &ArrayList, and &mut ArrayList.
• Navigate and edit near a position with Cursor and CursorMut.
• Inspect storage with ArrayList::capacity, ArrayList::spare_capacity, and ArrayList::shrink.

Storage Model

ArrayList<T, N> stores elements in chunks that can each hold up to N elements. The logical order is independent from internal chunk boundaries: iteration and indexing see one continuous sequence.

Middle insertions and removals can leave spare capacity inside chunks. After a middle removal that leaves the edited chunk non-empty, or after a middle insertion that splits a full chunk, the edited chunk is locally refilled up to half capacity from immediate sibling chunks when those siblings contain more than half capacity. Siblings at or below half capacity are left untouched, so edit-heavy workloads can still become fragmented. Use ArrayList::spare_capacity to inspect unused chunk slots and ArrayList::shrink to compact elements toward the front.

This is a local minimum-occupancy heuristic, not a global invariant. The minimum is N / 2 using integer division, so odd capacities round down. Refill only touches the edited chunk and its immediate siblings, preferring bounded local movement over globally dense storage. Inserting into a full middle chunk splits that chunk locally. Front/back pushes and pops keep their direct boundary behavior, so edge chunks may be less than half full.

Chunk Capacity

The second type parameter is the maximum number of elements per chunk. Capacity must be at least 4. Smaller chunk sizes are rejected at compile time by constructors and operations because this data structure is designed around multi-element chunks and a local half-full occupancy heuristic.

Chunk size has a large effect on performance. Small capacities reduce the maximum amount moved inside one chunk, but they also create many more chunks, more boundary crossings, more allocations, and more metadata to scan. Larger capacities improve locality and reduce chunk count, which is especially important for cursor-local edits, but middle insertions and removals can move more elements within the edited chunk and its immediate siblings.

Very small capacities are mostly useful for stress-testing chunk boundaries. For general use, prefer capacities large enough to amortize chunk overhead. Values in the 32-64 range are usually more representative than the minimum supported size; mutation-heavy workloads often benefit from the larger end of that range.

Keeping edited chunks at least half full where possible reduces the chance of many tiny chunks after repeated mutations. The tradeoff is that the list may contain more chunks than a fully compacted layout, so locating an indexed element can require scanning more chunk metadata until ArrayList::shrink is called.

Performance Notes

The exact cost depends on chunk occupancy and the chosen chunk capacity:

• ArrayList::len and ArrayList::is_empty are constant time.
• End pushes and pops usually touch only one edge chunk.
• ArrayList::get, ArrayList::get_mut, ArrayList::insert, and ArrayList::remove locate elements by scanning chunk metadata unless the list is densely packed.
• Middle insertion/removal may move elements within the edited chunk and its immediate siblings.
• Iteration is in logical order and does not expose chunk boundaries.

Call ArrayList::shrink after edit-heavy phases if a compact front-filled layout is more important than preserving spare chunk slots for future edits.

Example

use array_list::ArrayList;

let mut list: ArrayList<i64, 6> = ArrayList::new();
list.push_back(2);
list.push_front(0);
list.insert(1, 1);

assert_eq!(list.front(), Some(&0));
assert_eq!(list.get(1), Some(&1));
assert_eq!(list.back(), Some(&2));

assert_eq!(list.remove(1), Some(1));
assert_eq!(list.pop_back(), Some(2));
assert_eq!(list.pop_front(), Some(0));

Structs

ArrayList

A dynamic ordered sequence stored as fixed-capacity chunks.

Cursor

A read-only cursor over an ArrayList.

CursorMut

A mutable cursor over an ArrayList.

IntoIter

An owning iterator over the elements of an ArrayList.

Iter

A read-only iterator over an ArrayList.

IterMut

A mutable iterator over an ArrayList.