Introduction to Unrolled Linked List

Last Updated on November 28, 2022 by Prepbytes

An unrolled linked list is a type of linked list in which each node contains an array of integers instead of just an integer. Unrolled linked list is also known as the cache-sensitive data structure. So till now, we have seen Linked List of type Singly Linked List and Doubly Linked List. In the Single Linked List, we have the next pointer, and thus we can only move forward in the linked list. The structure of the node is similar to:

struct Node {
    int data;
    struct Node* next;

};

struct Node{
    int data;
    Node* next;
};

class Node 
{
    int data;
    Node next;
}

class Node:
    def __init__(self, data = None, next = None):
        self.data = data
        self.next = next

Whereas in Doubly Linked List, in addition to the next pointer, we also have the prev pointer, and thus we can have traversal in either direction of a node. The structure of the node is similar to:

struct Node{
    int data;
    struct Node* next;
    struct Node* prev;
};

struct Node{
    int data;
    Node* next;
    Node* prev;
};

class Node:
    def __init__(self, data = None, next = None, prev = None):
        self.data = data
        self.next = next
        self.prev = prev

class Node 
{
	int data;
	Node next;
	Node prev;
}

Now, another type of Linked List exists, where instead of storing just 1 element at each node, we can store an entire array at each node, which is called Unrolled Linked List.

Now I think from above; you must have got a little idea about Unrolled Linked List. In the next section, we will see it in depth.

What is Unrolled Linked List?

An Unrolled Linked List is a type of linked list that can store multiple elements at a single reference location, i.e., at each node, we can store multiple elements together.

Thus the structure of a typical Unrolled Linked List is like:

#define MAX_SIZE 50
struct Node{
    int noOfElements; // number of elements in this node, upto maximum elements
    struct Node* next; // reference to next node 
    int elements[MAX_SIZE]; // this array will contain noOfElements, however space is reserved for MAX_SIZE
};

#define MAX_SIZE 50
struct Node{
    int noOfElements; // number of elements in this node, upto maximum elements
    Node* next; // reference to next node 
    int elements[MAX_SIZE]; // this array will contain noOfElements, however space is reserved for MAX_SIZE
};

class Node 
{
    final int MAX_SIZE =50;
    //number of elements in this node, upto maximum elements
    int noOfElements;
    Node next; // reference to next node
    int []elements=new int[MAX_SIZE]; 
    // this array will contain noOfElements, however space is reserved for MAX_SZIE
}

class Node:
     
    def __init__(self, noOfElements = 0):
         
        self.noOfElements = noOfElements
        MAX_SIZE = 50
        self.array = [0 for i in range(MAX_SIZE)]
        self.next = None

Example of Unrolled Linked List

From this figure, we can observe that for every node of Unrolled Linked List can have any number of elements and the space reserved can be different.

For example, in the first node, we have space for 5 elements, but we have filled with only 3 elements i.e 1 2 3, and similarly in the next node also we have space for 5 elements, but we have filled with only 2 elements.

Now, the question must be arising in your mind that why do we need this type of Linked List?

Why do We Need Unrolled Linked List?

• We are already aware of the advantages that Linked List gives us over arrays but Unrolled Linked List combines the advantage of the array (small memory overhead) along with the advantage of linked lists like fast insertion and deletion.

• By storing multiple elements at each node, an unrolled linked list offers the advantage of linked list across multiple elements.

  • For example : If an unrolled linked list stores an array of 5 elements at each node, it will offer the same advantage (because of pointers) across those 5 elements. Thus it covers advantage of both arrays and linked list.

• Faster performance when you consider cache management.

Advantages of unrolled linked list

1. Faster Linear Search as compared to Original Linked List due to cache friendliness.
2. Requires less space for pointer as compared to original linked list.
3. Traversal, Insertion and Deletion is much faster as compared to original Linked List.

Disadvantage of unrolled linked list

1. A fairly high overhead per node when compared to the singly linked list, since for every node it can store an array of elements.

Efficient Searching

Let us understand how it is providing efficient capability with the help of an example. Take an Example:

• We have a total of 10 elements spread over 3 nodes and thus distribution can be 3 3 4 elements respectively in each node. Now, if we are required to find 8^th element, we will traverse only the last block of the node. Thus searching can also be efficient in such a way.

Conclusion

This blog tried to introduce the audience to yet another type of linked list, which is called Unrolled Linked List. This is an essential concept from an interview point of view. If you want to solve more questions on Linked List, which our expert mentors curate at PrepBytes, you can follow this link

FAQs related to unrolled linked list

1. What is an unrolled linked list?
An unrolled linked list is a type of linked list that stores an array at each node.

2. What are some use cases of unrolled linked lists?
An unrolled linked list is used in B-Tree, T-Tree, and hashed array tree.

3. Why do we need unrolled linked list?
We can do the searching operation faster with the help of an unrolled linked list. Therefore, we need an unrolled linked list where we need to perform some searching.