Unrolled linked list

Shreya Deep
Last Updated: May 13, 2022

Introduction

An unrolled linked list is a linked list type linear data structure in which each node contains an array of integers instead of just an integer. It is also known as the cache-sensitive data structure. It has the advantages of both an array and a linked list. Therefore, it’s quite efficient. Just like an array, it takes less memory compared to a linked list, and like a linked list, it does the inserting and the deletion operations faster. 

Source: Wikipedia 

Why do we need unrolled linked lists?

The biggest requirement lies in the case of searching. We know that, in a linked list, searching an element takes O(n) time. To reduce this, we use an unrolled linked list. How does it optimize the search? Let’s see this using an example. Suppose we have eight elements spread over three nodes in the distribution form -> 3,3,2. So, if we need to find the 7th element, we know that we’ve to find it in the last node only. And the rest two nodes will get out of the search space. Thus, searching is efficient in the case when we know which element is to be searched.

Advantages of unrolled linked list

  • Traversal is faster due to its caching behavior.
  • Less storage space is required.
  • Insertion, deletion, and searching operations are faster

Disadvantages of unrolled linked list

  • High overhead per node, i.e., high memory is required per node storing an array for each node.

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 nodeWe 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.

Frequently asked questions

  1. 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.
     
  2. What is an unrolled linked list?
    An unrolled linked list is a linear data structure that stores an array at each node.
     
  3. 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. 
     
  4. 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.

Key Takeaways

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 double-ended linked list and circular linked list.

To learn more about such data structures, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy Coding!

Was this article helpful ?
0 upvotes