Crate unrolled_linked_list[][src]

Expand description

Unrolled linked list

An wiki is a linear data structure that is a variant on the linked list. Instead of just storing 1 element at each node, unrolled linked lists store an entire array at each node.

Unrolled linked lists combine the advantages of the array (small memory overhead) with the benefits of linked lists (fast insertion and deletion) to produce vastly better performance. By storing multiple elements at each node, unrolled linked lists effectively spread out the overhead of linked lists across multiple elements. So, if an unrolled linked list stores an array of 4 elements at each node, its spreading the linked list overhead (pointers) across those 4 elements.

The true benefits of the unrolled linked list come in the form of caching. The unrolled linked list takes advantage of this when it comes to indexing.

Example

Let’s suppose we have a following json:

 use unrolled_linked_list::UnrolledLinkedList;

fn main(){
  let mut list = UnrolledLinkedList::new();
  list.insert(0, 1);
  list.push(2);
  list.push(3);
  list.insert(3,4);
  if let Some(four) =  list.pop() { println!(" should be {}", four)}

  let one_opt = list.get(0);
  let one_mut_opt = list.get_mut(0);

  list.remove(0);

  for el in list.iter(){
    println!("elem {}",el);
  }

}

Modules

iters

Structs

UnrolledLinkedList

The unrolled linked list. The list that acts like a linked list but has the node structure inside.