I'm reading about unrolled linked lists and have found two different ways to make one. The book I have implements one like this:
// Node
typedef struct node {
int data;
struct node *next;
} Node;
// Block of nodes
typedef struct linkedblock {
struct linkedblock *next;
Node *head;
int nodeCount;
} LinkedBlock;
however Wikipedia shows that instead of LinkedBlock
having a pointer to a Node
, it has an array. I think this might be so that the memory is contiguous and something about cache efficiency? Is there other advantages to doing it this way? Is the way my book implements it less optimized/worse? Does there happen to be a common or preferred way?
I'm trying to implement an unrolled linked list so I can learn how they work, but also in case I need to use one in the future (I strangely can't find any C implementations on GitHub or elsewhere). Basically I'd like to know which of the two ways would be more likely to be used in real applications. Also is this a data structure I shouldn't waste too much time learning? Because in my other algorithms book (CLRS) I don't even see it mentioned.
The book's implementation seems like it would be of not very much use, because it actually uses more memory than a standard linked list (to store those LinkedBlock
structures).
One of the main advantages of an unrolled linked list is so that you can store more data per node than an normal linked list. It's a balance between arrays, which only use a single integer of extra space to store the size (space efficient), and linked lists, which have efficient insertion and deletion given a pointer to some data (time efficient).
As for the value of learning about them: they have similar algorithmic properties to normal linked lists. Most of the benefit in making an unrolled linked list is if you were to have an existing application that needs speeding up or uses too much memory, since they would have the same interface as a regular linked list. If you've learned about asymptotic analysis (which is also discussed in CLRS), then you might be able to recognize that the memory usage and time efficiency of unrolled linked lists differs only by a constant factor, so asymptotically, they are the same.
My recommendation would be: be aware that they exist and that they can improve performance in real-world applications, but unless you have a specific application that you're trying to speed up, don't worry too much about them.