Repository files navigation

Anunrolled linked list 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.

The dependency can be found as following:unrolled-linked-list = 1.0.1

Example:

use unrolled_linked_list::UnrolledLinkedList;fnmain(){letmut list =UnrolledLinkedList::new();  list.insert(0,1);  list.push(2);  list.push(3);  list.insert(3,4);ifletSome(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 elin list.iter(){println!("elem {}",el);}}

For the details, see the folder benches.The numbers and results have the typical format for the librarycriterion.

The typical result example:

Benchmarking push/unrolled_linked_listBenchmarking push/unrolled_linked_list: Warming up for 3.0000 sBenchmarking push/unrolled_linked_list: Collecting 100 samples in estimated 5.0358 s (364k iterations)Benchmarking push/unrolled_linked_list: Analyzingpush/unrolled_linked_list                        time:   [14.078 us 14.776 us 15.527 us]                        change: [+3.9244% +7.5033% +11.271%] (p = 0.00 < 0.05)                        Performance has regressed.