# Introduction to Unrolled Linked List ### Introduction

So till now, we have seen Linked List of type Singly Linked List and Doubly Linked List. In 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, unrolled linked list offers 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.