In this tutorial you will learn about unrolled linked list data structure.
What is Unrolled Linked List?
|
1 2 3 4 5 6 7 |
#define SIZE 50 struct node { int count; int elements[SIZE]; struct node *next; }; |
Each node in the unrolled array contains a certain maximum number of elements. The number of elements are large enough to fill a single cache line. The position of the element in the list can be indicated either by reference or by position in the array. An unrolled linked list can be shown like following.
Insertion
First of all it is checked if the space is available in the list for inserting a new element. If the space is available, the element is just inserted. When the element is inserted in the array elements, the count variable is incremented by one. If array doesn’t have free space to have an element, we just create a new node, place it after the current node and move half of the elements to newly created node. It creates room/space for the new element.
When an element is deleted from the list it is simply removed from the array. If the number of elements in the array falls below N/2, we take the elements from a neighboring array to fill the array. If neighboring array
also has N/2 elements then we merge both of the arrays.
Advantages of Unrolled Linked List
1. Due to its cache behavior, the unrolled linked list performs the sequential traversal very rapidly.
2. It requires less storage space.
3. It performs the operations more quickly than ordinary linked list.
4. Indexing time O (N) is reduced to O (N/max), as we are able to process a whole node at a time instead of individual elements.
The overhead per node for references and elements count is considerably high.
