A C++ program for Unrolled List

In this tutorial, we will see how to implement an Unrolled Linked List in C++. Unrolled Linked List is a variation of the normal Linked List where more than one element is stored at each node. By storing multiple elements at each node, we can improve the cache performance and also decreases the storage requirements.

In C++, we can implement this by having an array at each node with a predefined maximum number of elements. Other than this change the rest of the implementation is very much similar to Linked Lists.

So now we shall see the C++ code for this List

Program for Unrolled Linked List

Since we are using an array at each node, the node structure will be similar to this:

#define maxlength 10
struct node
{
 int length;
 int arr[maxlength];
 node* next;
};

As we can see the array is created with a predefined length of 10 here. We also provide an integer variable at each node which indicates the number of elements at that node, which should be less than the maximum length of the array. Also, since it is a linked list we have the pointer for the next node too.

 

A C++ code example of the implementation of the Unrolled Linked List with Insertion and Display:

#include<iostream>
#include<cstdlib>
#include<conio.h>
using namespace std;
#define maxlength 10
//Node contents
struct node
{
 int length;
 int arr[maxlength];
 node* next;
};
//Class to demonstrate the linked list
class unrolled_list
{   node* first;
    node* last;
public:
    unrolled_list();
    void add_node();
    void display_list();
};
//Constructor which initiates the head and tail of the linked list as null 
unrolled_list::unrolled_list()
{
    first=nullptr;
    last=nullptr;
}
//Function to add a node to the linked list
void unrolled_list::add_node()
{   system("cls");
    int num;
    node* nod= new node;
    //If the pointer nod isn't created then it means that the machine has insufficient memory
    if(nod==nullptr)
    {
        cout<<"Memory Insufficient!";
        return;
    }
    cout<<"Enter the number of elements to be added to the node:";
    cout<<"( The number must be less than "<<maxlength<<" ) \n";
    cin>>nod->length;
    cout<<"Enter the elements:\n";
    for(int i=0;i<nod->length;i++)
        cin>>nod->arr[i];
    if(first==nullptr) //Case for the first node adition
    {
        first=nod;
        last=first;
        last->next=nullptr;
    }
    else              // Case for adding other nodes
    {
        last->next=nod;
        nod->next=nullptr;
        last=nod;
    }
}
//Function to dispaly the linked list items
void unrolled_list::display_list()
{   system("cls");

    int i=1;
    if(first==nullptr)   //To check if the list is empty
    {
        cout<<"Empty List!";
        getch();
        return;
    }
    node* nod=first;
    while(nod!=nullptr)
    {
        cout<<"Node "<<i<<":"<<endl;
        for(int j=0;j<nod->length;j++)
            cout<<nod->arr[j]<<" ";
        cout<<endl<<endl;
        i++;
        nod=nod->next;
    }
    getch();
}
//Main function to demonstrate the above functions
int main()
{unrolled_list uls;
 int ch,flag=1;
 while(flag)
 {   system("cls");
     cout<<"Enter the choice:\n";
     cout<<"1.ADD\n2.DISPALY\n3.EXIT\n";
     cin>>ch;
     switch(ch)
     {
         case 1: uls.add_node();
                 break;
         case 2: uls.display_list();
                 break;
         case 3: flag=0;
     }
 }
 return 0;
}

You can see that insertion and traversal operation of the linked list remain the same. The searching and removal part will be difficult as we need to search for multiple elements and remove an array at each node.

Leave a Reply