1

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.

Austin
  • 6,921
  • 12
  • 73
  • 138
  • 2
    Seems like one of those ideas that looks good in theory, but is a pain-in-the-... in practice. The fact that you couldn't find any implementations is a good indication that unrolled lists have no practical value. – user3386109 Jul 16 '16 at 19:26
  • By "unrolled linked lists", do you mean "intrusive linked lists"? Because if so, such lists definitely *DO* have practical value. – Tim Čas Jul 16 '16 at 19:34
  • I haven't heard of "instrusive linked list", my book calls it "unrolled linked list". no idea if these are the same. In my book it looks like a linked list of large blocks with smaller nodes within each. I guess if it's not something I'd end up using in the future I'll just skim it and move on then rather than spend the rest of the day trying to implement it. – Austin Jul 16 '16 at 19:36
  • 1
    You checkd out http://stackoverflow.com/questions/2956928/data-structure-name-combination-array-linked-list? – a3f Jul 16 '16 at 20:22

1 Answers1

3

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.

MrCodeBlok
  • 146
  • 1
  • 3