array_list

Struct ArrayList

Source 
pub struct ArrayList<T, const N: usize>
where
    [T; N]: Array,
    Usize<N>: NonZero + ConstCast<u16>,
{ /* private fields */ }
Expand description

A dynamic container that combines the characteristics of a Vec and a LinkedList, implemented as an unrolled linked list with chunked storage.

The ArrayList is backed by a XOR linked list, requiring only a single pointer for bidirectional traversal between nodes. This design is both memory-efficient and optimized for cache locality compared to traditional doubly linked lists.

§Type Parameters

  • T: The type of elements stored in the list.
  • N: The maximum number of elements that each node (or chunk) can hold. This determines the granularity of the unrolled linked list. Larger values reduce the number of nodes but increase the size of each node.

§Features

  • Chunked Storage: Each node can hold up to N elements, reducing the overhead of individual allocations compared to a traditional linked list.
  • Memory Efficiency: The XOR linked list design minimizes pointer storage requirements.
  • Bidirectional Traversal: Supports efficient iteration in both forward and backward directions.
  • Flexible Operations: Allows efficient insertions, deletions, and access at arbitrary positions.

§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));

§Applications

ArrayList is suitable for use cases where:

  • Frequent insertions or deletions occur in the middle of the list.
  • Memory efficiency and improved cache performance over plain LinkedList are priorities.
  • A hybrid structure that balances the strengths of Vec and LinkedList is needed.

§Note

The structure name ArrayList has no association with Java’s ArrayList.

Implementations§

Source§

impl<T, const N: usize> ArrayList<T, N>
where [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source

pub const fn new() -> Self

Creates a new, empty ArrayList.

This constructor initializes an ArrayList with no elements and no allocated nodes. It is a constant function, allowing the creation of ArrayList instances in compile-time contexts where applicable.

§Returns

A new, empty instance of ArrayList.

§Example
use array_list::ArrayList;

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

assert!(list.is_empty());
Source

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 node is full, a new node will be allocated to accommodate the element.

§Parameters
  • value: The element to add to the front of the ArrayList.
§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));
Source

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 node is full, a new node will be allocated to accommodate the element.

§Parameters
  • value: The element to add to the back of the ArrayList.
§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));
Source

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

Inserts an element at the specified index, shifting subsequent elements to the right.

§Arguments
  • index: The position at which to insert the new element.
  • value: The value to insert.
§Panics
  • Panics if the index is out of bounds (greater than the list’s current length).
§Behavior
  • Traverses the list to locate the appropriate node and index.
  • If the target node is full, the method splits the node, redistributes elements, and inserts the value.
§Complexity
  • O(n) for traversal to find the target node.
  • O(N) within the node for shifting elements, where N is the node’s capacity.
§Examples
use array_list::ArrayList;

let mut list: ArrayList<i64, 3> = 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));
Source

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

Moves all elements from other to the end of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

§Complexity
  • Time complexity: O(1)
  • Memory complexity: O(1)
§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));
Source

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

Removes and returns the first element of the ArrayList, if any.

This method removes the first element of the list and adjusts the head pointer and internal structure accordingly. If the list is empty, it returns None.

§Returns
  • Some(T) if the list contains elements, where T is the removed element.
  • None if the list is empty.
§Complexity
  • O(1) when the first element is removed and there are no structural changes (e.g., the head node has more elements).
  • O(1) amortized, including the occasional node removal and re-linking operations.
§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);
Source

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

Removes and returns the last element of the ArrayList, if any.

This method removes the last element of the list and adjusts the tail pointer and internal structure accordingly. If the list is empty, it returns None.

§Returns
  • Some(T) if the list contains elements, where T is the removed element.
  • None if the list is empty.
§Complexity
  • O(1) when the last element is removed and there are no structural changes (e.g., the tail node has more elements).
  • O(1) amortized, including the occasional node removal and re-linking operations.
§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);
Source

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

Removes and returns the element at the specified index, shifting subsequent elements left.

§Arguments
  • index: The position of the element to remove.
§Returns
  • The element removed from the list.
§Panics
  • Panics if the index is out of bounds.
§Behavior
  • The method traverses the list to locate the node containing the element at the given index.
  • The element is removed from the node, and subsequent elements within the node are shifted to the left.
  • If the node becomes empty after removal, it is removed from the list, and the links between nodes are updated.
§Complexity
  • O(n) to locate the target node.
  • O(N) within the node for shifting elements, where N is the node’s 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), 20);
assert_eq!(list.get(1), Some(&30));
assert_eq!(list.len(), 4);

// Attempting to remove out-of-bounds index will panic
// list.remove(10);
Source

pub fn clear(&mut self)

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

This method deallocates all nodes in the list and resets the head, tail, and length to their initial states. The method does not shrink the capacity of the list’s nodes.

§Complexity
  • Time complexity: O(n), where n is the total number of elements in the list.
§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);
Source

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

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

This method provides read-only access to the first element of the list without removing it.

§Returns
  • Some(&T) if the list contains elements, where &T is a reference to the first element.
  • None if the list is empty.
§Complexity
  • O(1), as it directly accesses the first element in the list.
§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);
Source

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

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

This method provides mutable access to the first element of the list without removing it.

§Returns
  • Some(&mut T) if the list contains elements, where &mut T is a mutable reference to the first element.
  • None if the list is empty.
§Complexity
  • O(1), as it directly accesses the first element in the list.
§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);
Source

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

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

This method provides read-only access to the last element of the list without removing it.

§Returns
  • Some(&T) if the list contains elements, where &T is a reference to the last element.
  • None if the list is empty.
§Complexity
  • O(1), as it directly accesses the last element in the list.
§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);
Source

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

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

This method provides mutable access to the last element of the list without removing it.

§Returns
  • Some(&mut T) if the list contains elements, where &mut T is a mutable reference to the last element.
  • None if the list is empty.
§Complexity
  • O(1), as it directly accesses the last element in the list.
§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);
Source

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

Returns a reference to the element at the specified index, if present.

§Arguments
  • index: The position of the element in the list.
§Returns
  • Some(&T) if the index is valid and the element exists.
  • None if the index is out of bounds.
§Complexity
  • O(n), where n is the number of nodes in the list, as nodes are traversed sequentially.
§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
Source

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

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

§Arguments
  • index: The position of the element in the list.
§Returns
  • Some(&mut T) if the index is valid and the element exists.
  • None if the index is out of bounds.
§Complexity
  • O(n), where n is the number of nodes in the list, as nodes are traversed sequentially.
§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
Source

pub const fn len(&self) -> usize

Returns the number of elements currently stored in the ArrayList.

§Returns

The total number of elements across all nodes 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);
Source

pub const fn is_empty(&self) -> bool

Checks if the ArrayList is empty.

§Returns

true if the ArrayList contains no elements, otherwise false.

§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());
Source

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

Provides an iterator over list’s elements.

§Examples
use array_list::ArrayList;

let mut list: ArrayList<_, 2> = 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);
Source

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

Provides a cursor at the front element.

The cursor is pointing to the “ghost” non-element if the list is empty.

Source

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

Provides a cursor at the back element.

The cursor is pointing to the “ghost” non-element if the list is empty.

Trait Implementations§

Source§

impl<T, const N: usize> Clone for ArrayList<T, N>
where T: Clone, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<T, const N: usize> Debug for ArrayList<T, N>
where T: Debug, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<T, const N: usize> Default for ArrayList<T, N>
where [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<T, const N: usize> Drop for ArrayList<T, N>
where [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

fn drop(&mut self)

Executes the destructor for this type. Read more
Source§

impl<'a, T, const N: usize> Extend<&'a T> for ArrayList<T, N>
where T: Clone, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

Extends a collection with the contents of an iterator. Read more
Source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
Source§

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. Read more
Source§

impl<T, const N: usize> Extend<T> for ArrayList<T, N>
where [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

Extends a collection with the contents of an iterator. Read more
Source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
Source§

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. Read more
Source§

impl<T, const N: usize, const M: usize> From<[T; M]> for ArrayList<T, N>
where [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

Converts to this type from the input type.
Source§

impl<T, const N: usize> FromIterator<T> for ArrayList<T, N>
where [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

Creates a value from an iterator. Read more
Source§

impl<T, const N: usize> Hash for ArrayList<T, N>
where T: Hash, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

Feeds this value into the given Hasher. Read more
1.3.0 · Source§

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

Feeds a slice of this type into the given Hasher. Read more
Source§

impl<'a, T, const N: usize> IntoIterator for &'a ArrayList<T, N>
where [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

type Item = &'a T

The type of the elements being iterated over.
Source§

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

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Iter<'a, T, N> ⓘ

Creates an iterator from a value. Read more
Source§

impl<T, const N: usize> Ord for ArrayList<T, N>
where T: Ord, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

This method returns an Ordering between self and other. Read more
1.21.0 · Source§

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

Compares and returns the maximum of two values. Read more
1.21.0 · Source§

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

Compares and returns the minimum of two values. Read more
1.50.0 · Source§

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

Restrict a value to a certain interval. Read more
Source§

impl<T, const N: usize> PartialEq for ArrayList<T, N>
where T: PartialEq, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

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

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

impl<T, const N: usize> PartialOrd for ArrayList<T, N>
where T: PartialOrd, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

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

This method returns an ordering between self and other values if one exists. Read more
1.0.0 · Source§

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

Tests less than (for self and other) and is used by the < operator. Read more
1.0.0 · Source§

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

Tests less than or equal to (for self and other) and is used by the <= operator. Read more
1.0.0 · Source§

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

Tests greater than (for self and other) and is used by the > operator. Read more
1.0.0 · Source§

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

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

impl<T, const N: usize> Eq for ArrayList<T, N>
where T: Eq, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

impl<T, const N: usize> Send for ArrayList<T, N>
where T: Send, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Source§

impl<T, const N: usize> Sync for ArrayList<T, N>
where T: Sync, [T; N]: Array, Usize<N>: NonZero + ConstCast<u16>,

Auto Trait Implementations§

§

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

§

impl<T, const N: usize> RefUnwindSafe for ArrayList<T, N>
where T: RefUnwindSafe,

§

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

§

impl<T, const N: usize> UnwindSafe for ArrayList<T, N>
where T: RefUnwindSafe + UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.