Struct ArrayList 

pub struct ArrayList<T, const N: usize> { /* private fields */ }

A dynamic ordered sequence stored as fixed-capacity chunks.

Features

• Chunked storage: each chunk can hold up to N elements, reducing allocation overhead compared to a traditional linked list.
• Sequence operations: supports front, back, indexed, iterator, and cursor-based access.
• Local editing: mutable cursors can insert and remove near their current position while keeping track of the logical element when possible.

Type Parameters

• T: The type of elements stored in the list.
• N: The maximum number of elements that each chunk can hold.

N 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 is a performance tuning parameter. Small chunks reduce the maximum movement within any one chunk, but they increase chunk count, allocation count, boundary crossings, and indexed lookup metadata. Larger chunks reduce that overhead and can improve cursor-local mutation performance, at the cost of moving more elements within the edited chunk when a middle insertion or removal occurs. Capacities around 32-64 are usually a better starting point for real workloads than the minimum supported size.

Fragmentation

Middle insertions and removals may 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.

This is a local minimum-occupancy heuristic, not a global invariant. The minimum is N / 2 using integer division, so odd capacities round down. Front/back pushes and pops keep their direct boundary behavior, so edge chunks may be less than half full. Use shrink when explicit front compaction is useful.

Example

use array_list::ArrayList;

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

assert!(!list.is_empty());
assert_eq!(list.len(), 3);

assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_front(), Some(2));
assert_eq!(list.pop_front(), Some(3));

use array_list::ArrayList;

let mut list: ArrayList<i32, 3> = ArrayList::new();
list.push_back(1);

Implementations

impl<T, const N: usize> ArrayList<T, N>

pub const fn new() -> Self

Creates a new, empty ArrayList with no elements and no allocated chunks.

Example

use array_list::ArrayList;

let list: ArrayList<i64, 6> = ArrayList::new();

assert!(list.is_empty());

pub fn push_front(&mut self, value: T)

Adds an element to the front of the ArrayList.

The element is inserted at the beginning of the list, shifting existing elements forward if necessary. If the first chunk is full, a new one will be allocated to accommodate the element.

Example

use array_list::ArrayList;

let mut list: ArrayList<i64, 6> = ArrayList::new();
list.push_front(10);
list.push_front(20);

assert_eq!(list.len(), 2);

assert_eq!(list.pop_front(), Some(20));
assert_eq!(list.pop_front(), Some(10));

pub fn push_back(&mut self, value: T)

Adds an element to the back of the ArrayList.

The element is inserted at the end of the list. If the last chunk is full, a new one will be allocated to accommodate the element.

Example

use array_list::ArrayList;

let mut list: ArrayList<i64, 6> = ArrayList::new();
list.push_back(10);
list.push_back(20);

assert_eq!(list.len(), 2);

assert_eq!(list.pop_back(), Some(20));
assert_eq!(list.pop_back(), Some(10));

pub fn insert(&mut self, index: usize, value: T)

Inserts an element at index, shifting that element and all later elements to the right.

If the target chunk is full, insertion splits that chunk locally. When a middle insertion splits a full chunk, the edited chunk may be refilled up to half capacity from immediate sibling chunks that contain more than half capacity. Inserting at len is equivalent to push_back.

Panics

• Panics if the index is out of bounds (greater than the list’s current length).

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(30);
list.insert(1, 20);

assert_eq!(list.get(0), Some(&10));
assert_eq!(list.get(1), Some(&20));
assert_eq!(list.get(2), Some(&30));

pub fn append(&mut self, other: &mut Self)

Moves all elements from other to the back of this list.

This preserves the logical order of both lists. When the tail chunk of this list has spare capacity, elements are first drained from the head of other to fill that boundary chunk; remaining chunks are then moved wholesale. After this operation, other is empty.

Example

use array_list::ArrayList;

let mut list1: ArrayList<i32, 4> = ArrayList::new();
list1.push_back(1);
list1.push_back(2);

let mut list2: ArrayList<i32, 4> = ArrayList::new();
list2.push_back(3);
list2.push_back(4);

list1.append(&mut list2);

assert_eq!(list1.len(), 4);
assert_eq!(list1.get(0), Some(&1));
assert_eq!(list1.get(1), Some(&2));
assert_eq!(list1.get(2), Some(&3));
assert_eq!(list1.get(3), Some(&4));

pub fn pop_front(&mut self) -> Option<T>

Removes and returns the first element of the ArrayList, if any. If the list is empty, it returns None.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_front(10);
list.push_front(20);

assert_eq!(list.pop_front(), Some(20));
assert_eq!(list.pop_front(), Some(10));
assert_eq!(list.pop_front(), None);

pub fn pop_back(&mut self) -> Option<T>

Removes and returns the last element of the ArrayList, if any. If the list is empty, it returns None.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(20);

assert_eq!(list.pop_back(), Some(20));
assert_eq!(list.pop_back(), Some(10));
assert_eq!(list.pop_back(), None);

pub fn remove(&mut self, index: usize) -> Option<T>

Removes and returns the element at index.

Elements after index keep their relative order. After a middle removal that leaves the edited chunk non-empty, that chunk may be refilled up to half capacity from immediate sibling chunks that contain more than half capacity.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(20);
list.push_back(30);
list.push_back(40);
list.push_back(50);

assert_eq!(list.remove(1), Some(20));
assert_eq!(list.get(1), Some(&30));
assert_eq!(list.len(), 4);

assert_eq!(list.remove(10), None);

pub fn clear(&mut self)

Removes all elements from the ArrayList, effectively making it empty.

Example

use array_list::ArrayList;

let mut list: ArrayList<i32, 4> = ArrayList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

assert_eq!(list.len(), 3);

list.clear();

assert_eq!(list.len(), 0);
assert!(list.is_empty());
assert_eq!(list.front(), None);
assert_eq!(list.back(), None);

pub fn front(&self) -> Option<&T>

Returns a reference to the first element of the ArrayList, if any.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(20);

assert_eq!(list.front(), Some(&10));

list.pop_front();
assert_eq!(list.front(), Some(&20));

list.pop_front();
assert_eq!(list.front(), None);

pub fn front_mut(&mut self) -> Option<&mut T>

Returns a mutable reference to the first element of the ArrayList, if any.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(20);

assert_eq!(list.front_mut(), Some(&mut 10));

list.pop_front();
assert_eq!(list.front_mut(), Some(&mut 20));

list.pop_front();
assert_eq!(list.front_mut(), None);

pub fn back(&self) -> Option<&T>

Returns a reference to the last element of the ArrayList, if any.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(20);

assert_eq!(list.back(), Some(&20));

list.pop_back();
assert_eq!(list.back(), Some(&10));

list.pop_back();
assert_eq!(list.back(), None);

pub fn back_mut(&mut self) -> Option<&mut T>

Returns a mutable reference to the last element of the ArrayList, if any.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(20);

assert_eq!(list.back_mut(), Some(&mut 20));

list.pop_back();
assert_eq!(list.back_mut(), Some(&mut 10));

list.pop_back();
assert_eq!(list.back_mut(), None);

pub fn get(&self, index: usize) -> Option<&T>

Returns a reference to the element at index, if any.

Index lookup scans chunk metadata to find the chunk containing index. Fragmented lists may require scanning more chunks than compact lists.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(20);

assert_eq!(list.get(0), Some(&10));
assert_eq!(list.get(1), Some(&20));
assert_eq!(list.get(2), None); // Out of bounds

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to the element at index, if any.

Index lookup scans chunk metadata to find the chunk containing index. Fragmented lists may require scanning more chunks than compact lists.

Examples

use array_list::ArrayList;

let mut list: ArrayList<i64, 4> = ArrayList::new();
list.push_back(10);
list.push_back(20);

assert_eq!(list.get_mut(0), Some(&mut 10));
assert_eq!(list.get_mut(1), Some(&mut 20));
assert_eq!(list.get_mut(2), None); // Out of bounds

pub const fn len(&self) -> usize

Returns the number of elements currently stored in the ArrayList.

Example

use array_list::ArrayList;

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

assert_eq!(list.len(), 2);

pub fn capacity(&self) -> usize

Returns the total number of elements that can fit in the currently allocated chunks.

This is the sum of the capacity of every internal chunk. It is always at least len, but it may be larger after edits until the list is compacted with shrink.

Example

use array_list::ArrayList;

let mut list: ArrayList<i32, 4> = ArrayList::new();
assert_eq!(list.capacity(), 0);

list.push_back(1);
assert!(list.capacity() >= list.len());

pub fn spare_capacity(&self) -> usize

Returns the number of unused element slots in allocated chunks.

This is capacity minus len. A larger value means the list has more spare chunk storage, usually after middle edits, front-heavy insertions, or uneven appends.

Example

use array_list::ArrayList;

let mut list: ArrayList<i32, 4> = ArrayList::from([1, 2, 3, 4, 5]);
list.remove(1);

assert_eq!(list.spare_capacity(), list.capacity() - list.len());

pub fn shrink(&mut self)

Compacts elements toward the front of the list.

This preserves element order and length. It can reduce spare capacity after removals or uneven insertions by filling earlier chunks from later chunks and removing chunks that become empty. It does not guarantee that all allocation capacity held by the internal VecDeque is released.

Example

use array_list::ArrayList;

let mut list: ArrayList<i32, 4> = ArrayList::from([1, 2, 3]);
list.remove(1);
list.shrink();

assert_eq!(list, [1, 3]);

pub const fn is_empty(&self) -> bool

Checks if the ArrayList is empty.

Example

use array_list::ArrayList;

let mut list: ArrayList<i64, 6> = ArrayList::new();
assert!(list.is_empty());

list.push_back(1);
assert!(!list.is_empty());

pub fn iter(&self) -> Iter<'_, T, N>

Provides an iterator over the list’s elements.

Examples

use array_list::ArrayList;

let mut list: ArrayList<_, 4> = ArrayList::new();
list.push_back(0);
list.push_back(1);
list.push_back(2);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), None);

pub fn iter_mut(&mut self) -> IterMut<'_, T, N>

Provides a mutable iterator over the list’s elements.

Examples

use array_list::ArrayList;

let mut list: ArrayList<_, 4> = ArrayList::new();
list.push_back(0);
list.push_back(1);
list.push_back(2);

let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 0));
assert_eq!(iter.next(), Some(&mut 1));
assert_eq!(iter.next(), Some(&mut 2));
assert_eq!(iter.next(), None);

pub fn cursor_front(&self) -> Cursor<'_, T, N>

Provides a read-only cursor at the front element.

The cursor points to the ghost non-element if the list is empty.

Example

use array_list::ArrayList;

let list: ArrayList<i32, 4> = ArrayList::from([1, 2]);
let cursor = list.cursor_front();

assert_eq!(cursor.index(), Some(0));
assert_eq!(cursor.current(), Some(&1));

let empty: ArrayList<i32, 4> = ArrayList::new();
assert_eq!(empty.cursor_front().index(), None);

pub fn cursor_back(&self) -> Cursor<'_, T, N>

Provides a read-only cursor at the back element.

The cursor points to the ghost non-element if the list is empty.

Example

use array_list::ArrayList;

let list: ArrayList<i32, 4> = ArrayList::from([1, 2]);
let cursor = list.cursor_back();

assert_eq!(cursor.index(), Some(1));
assert_eq!(cursor.current(), Some(&2));

let empty: ArrayList<i32, 4> = ArrayList::new();
assert_eq!(empty.cursor_back().index(), None);

pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T, N>

Provides a mutable cursor at the front element.

The cursor points to the ghost non-element if the list is empty.

Example

use array_list::ArrayList;

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

assert_eq!(cursor.index(), Some(0));
assert_eq!(cursor.current(), Some(&mut 1));

let mut empty: ArrayList<i32, 4> = ArrayList::new();
assert_eq!(empty.cursor_front_mut().index(), None);

pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T, N>

Provides a mutable cursor at the back element.

The cursor points to the ghost non-element if the list is empty.

Example

use array_list::ArrayList;

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

assert_eq!(cursor.index(), Some(1));
assert_eq!(cursor.current(), Some(&mut 2));

let mut empty: ArrayList<i32, 4> = ArrayList::new();
assert_eq!(empty.cursor_back_mut().index(), None);

Trait Implementations

impl<T: Clone, const N: usize> Clone for ArrayList<T, N>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T, const N: usize> Debug for ArrayList<T, N>

where T: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, const N: usize> Default for ArrayList<T, N>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T, const N: usize> Extend<&'a T> for ArrayList<T, N>

where T: Clone,

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, const N: usize> Extend<T> for ArrayList<T, N>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, const N: usize, const M: usize> From<[T; M]> for ArrayList<T, N>

fn from(values: [T; M]) -> Self

Converts to this type from the input type.

impl<T, const N: usize> FromIterator<T> for ArrayList<T, N>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T, const N: usize> Hash for ArrayList<T, N>

where T: Hash,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<'a, T, const N: usize> IntoIterator for &'a ArrayList<T, N>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T, N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T, const N: usize> IntoIterator for &'a mut ArrayList<T, N>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T, N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const N: usize> IntoIterator for ArrayList<T, N>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const N: usize> Ord for ArrayList<T, N>

where T: Ord,

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T, const N: usize> PartialEq<&[T]> for ArrayList<T, N>

where T: PartialEq,

fn eq(&self, other: &&[T]) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, const N: usize> PartialEq<[T]> for ArrayList<T, N>

where T: PartialEq,

fn eq(&self, other: &[T]) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, const N: usize, const M: usize> PartialEq<[T; M]> for ArrayList<T, N>

where T: PartialEq,

fn eq(&self, other: &[T; M]) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, const N: usize> PartialEq for ArrayList<T, N>

where T: PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, const N: usize> PartialOrd for ArrayList<T, N>

where T: PartialOrd,

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T, const N: usize> Eq for ArrayList<T, N>

where T: Eq,