Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# 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

```

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?

• 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`.

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.

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 8th 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.