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.
• 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.

Example

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

let mut list = LinkedList::withexponentialgrowth(2, 1.5, MemoryUtilization::default());

// build linked list: x <-> a <-> b <-> c list.pushback('a'); list.pushback('b'); list.pushfront('x'); list.pushback('c');

asserteq!(Some('c'), list.popback()); asserteq!(Some('b'), list.popback()); asserteq!(Some('a'), list.popback()); asserteq!(Some('x'), list.popback()); asserteq!(None, list.popback()); asserteq!(None, list.popfront()); ```