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
}
};

You can also try this code with Online C++ Compiler
Run Code
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;
}
}

You can also try this code with Online C++ Compiler
Run Code
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;
}
}

You can also try this code with Online C++ Compiler
Run Code
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();
};

You can also try this code with Online C++ Compiler
Run Code
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!