orx-linked-list

Implements a doubly-linked list.

As opposed to the note of std::collections::LinkedList, orx_linked_list::LinkedList provides the main theoretical benefits of a linked list; i.e.,

• efficient insertion and removal of elements,

while aiming to avoid the practical drawbacks related with allocations and CPU cache due to the following:

• LinkedList uses an ImpVec as the underlying data structure which allows for defining inter-element relationships by thin references; next and prev relationships are defined by thin & references:
  • without any additional heap allocations since smart pointers such as Box or Rc per element are not necessary;
  • or without the need to use plain index numbers to mimic references.
• All elements are stored in the underlying PinnedVec of the ImpVec; which might either be a FixedVec or SplitVec. In either case, the elements will be stored close to each other in a vec-like structure. Although the order of elements in this vector will not be in the correct order as expected in a linked list, they will be pointing to other elements of the same vector. Therefore, unlike classical implementations by arbitrary heap allocations, the LinkedList implementation provides better cache locality.

Usage

Basic usage of the linked list is demonstrated below.

```rust use orxlinkedlist::prelude::*;

let mut list = LinkedList::withdoublinggrowth(4);

list.pushback('y'); list.pushfront('x'); list.pushback('z'); asserteq!(vec!['x', 'y', 'z'], list.collect_vec());

asserteq!(list.popback(), Some('z')); asserteq!(list.popfront(), Some('x')); asserteq!(vec!['y'], list.collectvec());

list.pushfront('x'); list.pushback('z'); asserteq!(vec!['x', 'y', 'z'], list.collectvec());

list.insertat(1, '?'); asserteq!(vec!['x', '?', 'y', 'z'], list.collect_vec());

asserteq!(Some(&'?'), list.getat(1)); *list.getmutat(1).unwrap() = '!';

asserteq!('!', list.removeat(1)); asserteq!(vec!['x', 'y', 'z'], list.collectvec()); ```

Memory

LinkedList provides two ways to configure the memory strategy:

• the first configuration is inherited from the PinnedVec variants and defines how the underlying storage will be kept;
• the second is related with the tradeoff between memory utilization and laziness favouring faster operations.

Underlying Storage Variants

The complete signature of a LinkedList holding elements of type T is as follows:

rust ignore LinkedList<'a, T, P> where P: PinnedVec<LinkedListNode<'a, T>>

The choice of the underlying PinnedVec defines the dynamic allocations. See FixedVec or SplitVec for possible strategies.

The following type aliases are defined for convenience to simplify the type signatures:

```rust ignore pub type LinkedListFixed<'a, T> = LinkedList<'a, T, FixedVec>>;

pub type LinkedListLinear<'a, T> = LinkedList<'a, T, SplitVec, Linear>>;

pub type LinkedListDoubling<'a, T> = LinkedList<'a, T, SplitVec, Doubling>>;

pub type LinkedListExponential<'a, T> = LinkedList<'a, T, SplitVec, Exponential>>; ```

These variants can be constructed with corresponding associated functions:

rust ignore let list: LinkedListFixed<char> = LinkedList::with_fixed_capacity(100); let list: LinkedListLinear<char> = LinkedList::with_linear_growth(32); let list: LinkedListDoubling<char> = LinkedList::with_doubling_growth(4); let list: LinkedListExponential<char> = LinkedList::with_exponential_growth(4, 1.5);

Time Complexity vs Memory Utilization

LinkedList holds all elements close to each other in a PinnedVec aiming for better cache locality while using thin references rather than wide pointers and to reduce heap allocations. In order to achieve O(1) time complexity while avoiding smart pointers, remove and pop operations are designed to be semi-lazy.

In the lazy case; i.e., when the strategy is set to MemoryReclaimStrategy::Lazy, every pop_back, pop_front or remove_at operation leaves a gap in the underlying vector. Status of utilization of the underlying vector can be queried using the memory_status method and the gaps can completely be reclaimed by manually calling the memory_reclaim method which has a time complexity of O(n) where n is the length of the underlying vector.

Being able to be lazy and to reclaim the gaps, it is possible to define and use different automated strategies which would fit better in different situations:

• Lazy: memory_reclaim is never called automatically:
  • leads to the cheapest possible pop_back, pop_front or remove_at operations,
  • however, the utilization of the vector can be low especially when a large number of elements enter and exit the linked list.
  • might be a better fit where keeping the time complexity of these operations at O(1) is important; or when utilization is not expected to drop too low.
• Eager: every pop_back, pop_front or remove_at method call is automatically followed by a memory_reclaim call:
  • this strategy continuously keeps the vector without gaps at 100% utilization;
  • however, abovementioned operations require O(n) time complexity;
  • might be a better fit where memory is scarce and more important than the increased time-complexity of these methods.
• WithThreshold(threshold): pop_back, pop_front or remove_at method call is followed by an automatic memory_reclaim call only if the memory utilization drops below a pre-determined threshold:
  • it is a generalization of Lazy and Eager allowing to select the required threshold level between memory utilization and amortized time complexity of these methods. Note that setting the least memory utilization to a value lower than 1.0 would still least to a constant amortized time complexity.

Memory utilization stategy is defined by a field which can be modified any time.

rust ignore let list = list .with_memory_utilization(MemoryUtilization::Eager) .with_memory_utilization(MemoryUtilization::Lazy) .with_memory_utilization(MemoryUtilization::WithThreshold(0.5));