ArrayList

ArrayList is a Rust crate that implements an unrolled linked list powered by a XOR linked list as its underlying structure. It combines features of both a Vec and a LinkedList, offering efficient sequential access with reduced pointer overhead compared to a traditional doubly linked list.

This crate is designed to handle dynamic collections efficiently, particularly in scenarios where frequent insertions, deletions, or iterations are required.

Features

• Dynamic: Combines the benefits of a Vec (compact, cache-friendly storage) and a LinkedList (efficient insertions and deletions).
• Reduced pointer overhead: Implements a XOR linked list, requiring only a single pointer per node for bidirectional traversal.
• Customizable chunk size: The size of each chunk is determined at compile time via a const generic parameter up to 64 elements.
• Efficient memory operations: Splits and merges nodes dynamically, redistributing elements when necessary.
• Rich API: Provides functionality for:
  • Insertions, deletions and access at arbitrary positions.
  • Index-based access with get methods.
  • Access to front and back elements.

Strengths

• Sequential access: By grouping multiple elements in each node, it reduces the pointer-following overhead inherent in linked lists.
• Low allocation cost: Nodes store multiple elements in contiguous memory, minimizing allocation frequency.
• Customizable performance: The chunk size can be tuned to balance memory usage and cache performance.

Pitfalls

• Random access is slower than Vec: While ArrayList provides index-based access, it requires traversing the list, making it less efficient than Vec for frequent random access.
• Unsafe code: The implementation relies on unsafe code for managing memory and pointers. However, it is extensively tested.
• More complex than Vec or LinkedList: The additional logic for node splitting, merging, and XOR-linked traversal increases complexity compared to simpler collections.

Installation

Add array_list to your Cargo.toml:

cargo add array_list

or edit your Cargo.toml manually by adding:

[dependencies]
array_list = "0.2"

Example Usage

use array_list::ArrayList;

fn main() {
    let mut list: ArrayList<i32, 2> = ArrayList::new();

    // Insert elements
    list.push_back(1);
    list.push_back(3);
    list.push_front(0);
    list.insert(1, 2);

    // Access elements
    println!("front: {:?}", list.front()); // Some(0)
    println!("back: {:?}", list.back());   // Some(3)

    // Remove elements
    assert_eq!(list.pop_front(), Some(0));
    assert_eq!(list.pop_back(), Some(3));
}

Safety

This crate contains unsafe code to achieve optimal performance and memory management.

However:

• All code is tested under Miri to ensure memory safety.
• The code coverage is approximately 90%, providing strong confidence in correctness.
• You can generate the code coverage report using tarpaulin.

Contributing

Contributions are welcome! Whether it’s improving documentation, fixing bugs, or suggesting new features, feel free to open an issue or submit a pull request (PR).

When contributing, please ensure:

• Code is formatted with cargo fmt.
• Tests are added or updated as necessary.
• Safety is maintained for any unsafe code introduced.

By contributing, you agree that your contributions will be licensed under the terms of the MIT license.

License

This crate is licensed under the MIT License. You are free to use, modify, and distribute it under the terms of the license.