Unrolled Linked List

http://www.geeksforgeeks.org/unrolled-linked-list-set-1-introduction/
Like array and linked list, unrolled Linked List is also a linear data structure and is a variant of linked list. Unlike simple linked list, it stores multiple elements at each node. That is, instead of storing single element at a node, unrolled linked lists store an array of elements at a node. Unrolled linked list covers advantages of both array and linked list as it reduces the memory overhead in comparison to simple linked lists by storing multiple elements at each node and it also has the advantage of fast insertion and deletion as that of a linked list.

• Because of the Cache behavior, linear search is much faster in unrolled linked lists.
• In comparison to ordinary linked list, it requires less storage space for pointers/references.
• It performs operations like insertion, deletion and traversal more quickly than ordinary linked lists (because search is faster).

// Unrolled Linked List Node

struct Node

{

    int numElements;

    int array[maxElements];

    struct Node *next;

};

 

/* Function to traverse am unrolled linked list

   and print all the elements*/

void printUnrolledList(struct Node *n)

{

    while (n != NULL)

    {

        // Print elements in current node

        for (int i=0; i<n->numElements; i++)

            printf("%d ", n->array[i]);

 

        // Move to next node

        n = n->next;

    }

}