2

Can any one explain me what is unrolled linked list. As per my knowledge its a linked list in which each node have array of elements. And of course this makes the searching faster.

In this diagram, adding the data 1,2,3 in that picture is clear, no complications… but why they added 4 in the second node? Why not in the 4th element of first node? what is the benefit of that? And what is the strategy they used there to split?

Kara
  • 6,115
  • 16
  • 50
  • 57
Prabhakaran
  • 23
  • 1
  • 6

3 Answers3

3

The benefit is, that they can insert data afterwards without moving every item in the list. Also it's up to you whether you want fragmenting or not. You could make the adding function check if the last node is 3/4 full and in that case create a new node. Or what they probably did:

If the array is already full, we first insert a new node either preceding or following the current one and move half of the elements in the current node into it. (http://en.wikipedia.org/wiki/Unrolled_linked_list)

Philip
  • 271
  • 1
  • 15
  • Thank you very much.... But how it is useful in cache memory??? We will use cache for fast retrieving right!!! den how this fast insertion will be helpful???? – Prabhakaran May 24 '13 at 12:36
  • In theory, unrolled linked lists are faster than "normal" linked lists because the nodes of a the latter could be more fragmented in memory which causes the processor to load more memory pages. Moreover, unrolled linked lists are smaller as they need not store pointers for each node. In fact, when you just want to store small objects or pointers/references in your list, consider using a dynamic array (vector) since it is by far the most efficient container, see: http://stackoverflow.com/questions/9764452/comprehensive-vector-vs-linked-list-benchmark-for-randomized-insertions-deletion – Philip May 25 '13 at 07:50
0

Number 4 is added to the 4th element of the first node. When 5 is added it then splits that node with 1, 2, 3 being in node one and 4, 5 in node two.

SpacedMonkey
  • 2,725
  • 1
  • 16
  • 17
  • But friend, why the left empty space?? whats the objective... Okay, As per philip dahen, it will be faster while insertion for data. but how it will be useful in cache. – Prabhakaran May 24 '13 at 12:42
0

Suppose you have elements no more than 'n' as of now (of course you can add elements in, later) and you want to create a linked list, the best way in terms of cache performance is to select Unrolled linked list. You create a blocks of size ceil square root on n and then start add elements in the block if its size is less than ceil of square root of n. Thus you have finally floor of square root on n blocks. This is useful in searching a kth node in linked list as its complexity has now been decreased from n to square root of n.

When the block is full, means if the block contains equal to square root of n elements, you have to make a shift operation such that the tail in that block becomes the head of the next block and the tail of that next block becomes the head of its next and so on till you hit NULL

In each block, circular linked list is maintained rather than simple linked list.

Hope this helps.. :)

phaigeim
  • 729
  • 13
  • 34