## Implementation of unrolled linked list

### Definition of the unrolled linked list node

In C++, an unrolled linked list node class is defined as follows:

```
// class for a node
class Node {
public:
Node* next; // Pointer to the next of the current node
int num_elements; //Number of elements in the array at the current node
int array[]; // Array of the current node
// Constructor
Node(int n) // n is the size of the array
{
next = NULL; // Initialize next to NULL
num_elements = 0; // Initially, set the number of elements in the array to 0
array[n]; // Set the size of the array to n
}
};
```

### Insertion in the unrolled linked list

In **insertion**, first, we **check **if there is any **space left** in the last node. If yes, we insert the element there, and the **size **occupied in this array is **incremented by one**. If not, we go and create a **new node**. We **move **half of the elements from the **current** node **to **the **new **node such that the **length **of the current node is **equal** to the **minimum threshold**. We add the given value to the new node and set its length. We also need to **update **the current nodeâ€™s **length**. Moreover, we set the current nodeâ€™s **next pointer** to refer to the new node and also update the **tail **to point to the new node. Implementation of this idea is as follows:

```
// Function for insertion operation
void insert(int num){
tot_nodes++; // Increase the count of total number of nodes by 1
// Check if the list is empty
if (head == NULL) {
// If the list is already empty, we need to create a new node and
//set the head and tail to it
head = new Node(node_size);
head->array[0] = num; // In the created node, push the current number at the
//0th position of the array
head->num_elements++; // Increment the number of elements in this node by 1
tail = head;
return;
}
// If the list is not empty, check if we can add more elements to the last node or not
if (tail->num_elements + 1 < node_size) { // If we can add, push the current number to
// the tail's array
tail->array[tail->num_elements] = num;
tail->num_elements++; //Increment the number of elements in tail by 1
}
// If we can't add more elements to the last node, we have to create a new node
else {
Node *new_node = new Node(node_size);
int j = 0;
// We move half of the elements from the current node to the new node
//such that the length of the current node is equal to the minimum threshold.
for (int i = tail->num_elements / 2 + 1;i < tail->num_elements; i++)
new_node->array[j++] = tail->array[i];
// Update the tail to be equal to this newly created node
new_node->array[j++] = num;
new_node->num_elements = j;
tail->num_elements = tail->num_elements / 2 + 1;
tail->next = new_node;
tail = new_node;
}
}
```

### Printing the unrolled linked list

For **printing **the unrolled linked list, start off from the head node until you reach the end. For each node, **print all the elements** of the node one by one and then** move to the next** node. Implementation of the print function is as follows:

```
// function for printing the list
void print()
{
cout<<"Unrolled Linked List: "<<endl;
Node *temp = head;
// Start from the head node until yor reach the end
while (temp != NULL) {
// Print all the elements in the array of the node
for (int i = 0; i < temp->num_elements; i++)
cout<<(temp->array[i])<<" ";
cout<<endl;
// Move to the next node
temp = temp->next;
}
}
```

### Overall implementation

```
#include<bits/stdc++.h>
using namespace std;
// class for a node
class Node {
public:
Node* next; // Pointer to the next of the current node
int num_elements; //Number of elements in the array at the current node
int array[]; // Array of the current node
// Constructor
Node(int n) // n is the size of the array
{
next = NULL; // Initialize next to NULL
num_elements = 0; // Initially, set the number of elements in the array to 0
array[n]; // Set the size of the array to n
}
};
// Class of unrolled linked list
class UnrolledLinkedList {
public:
Node *head; // Head of the linked list
Node *tail; // Tail of the linked list
int node_size; // Size of the array of a node
int tot_nodes; // total number of nodes
// Parameterized Constructor for the unrolledLinkedList class. This will
// be used for setting the maximum capacity
UnrolledLinkedList(int capacity)
{
head = NULL; // Initialize the head and tail to NULL
tail = NULL;
tot_nodes = 0; // Initialize the number of nodes to 0
node_size = capacity + 1; //Set the node size to capacity +1
}
// Function for insertion operation
void insert(int num){
tot_nodes++; // Increase the count of total number of nodes by 1
// Check if the list is empty
if (head == NULL) {
// If the list is already empty, we need to create a new node and
//set the head and tail to it
head = new Node(node_size);
head->array[0] = num; // In the created node, push the current number at the
//0th position of the array
head->num_elements++; // Increment the number of elements in this node by 1
tail = head;
return;
}
// If the list is not empty, check if we can add more elements to the last node or not
if (tail->num_elements + 1 < node_size) { // If we can add, push the current number to
// the tail's array
tail->array[tail->num_elements] = num;
tail->num_elements++; //Increment the number of elements in tail by 1
}
// If we can't add more elements to the last node, we have to create a new node
else {
Node *new_node = new Node(node_size);
int j = 0;
// We move half of the elements from the current node to the new node
//such that the length of the current node is equal to the minimum threshold.
for (int i = tail->num_elements / 2 + 1;i < tail->num_elements; i++)
new_node->array[j++] = tail->array[i];
// Update the tail to be equal to this newly created node
new_node->array[j++] = num;
new_node->num_elements = j;
tail->num_elements = tail->num_elements / 2 + 1;
tail->next = new_node;
tail = new_node;
}
}
// function for printing the list
void print()
{
cout<<"Unrolled Linked List: "<<endl;
Node *temp = head;
// Start from the head node until yor reach the end
while (temp != NULL) {
// Print all the elements in the array of the node
for (int i = 0; i < temp->num_elements; i++)
cout<<(temp->array[i])<<" ";
cout<<endl;
// Move to the next node
temp = temp->next;
}
}
};
int main(){
// Create a new unrolled linked list of capacity 4
UnrolledLinkedList *list = new UnrolledLinkedList(4);
int n; // input the total number of elements
cin>>n;
// Insert elements one by one
for (int i = 0; i <n; i++) {
int x;
cin>>x; // Input the number to be inserted
list->insert(x);
}
//Print the unrolled linked list
list->print();
};
```

**Input**

```
12 //n
1 2 3 4 5 6 7 8 9 10 11 12
```

**Output**

```
Unrolled Linked List:
1 2 3
4 5 6
7 8 9
10 11 12
```

### Complexities

**Time complexity**

Insertion

**O(n)**, where n is the total number of elements in the unrolled linked list.

**Reason**: For inserting an element, in the worst case, we need to traverse the whole linked list. Thus, the time complexity is O(n).

Printing

**O(n)**, where n is the total number of elements in the unrolled linked list.

**Reason**: For printing the whole list, we need to traverse the whole linked list element by element. Thus, the time taken will be O(n).

**Space complexity**

**O(1)** for both insertion and printing

**Reason**: Only constant extra space is required for these operations.

Also read - __Merge sort in linked list__

## Frequently Asked Questions

### What is a linked list?

A linked list is a data structure in which elements are stored at random memory locations. Each element is called a node. A node contains the address of the next node.

### What is an unrolled linked list?

An unrolled linked list is a linear data structure that stores an array at each node.

### Why do we need an 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.

### What are some use cases of unrolled linked lists?

An unrolled linked list is used in B-Tree and T-Tree and Hashed array Tree.

## Conclusion

In this article, we gave you an introduction to the data structure called unrolled linked list. This was one type of linked list. You can read more about other types of linked lists, such as Doubly Linked List and circular linked list.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!