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;
    Node* 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;
    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
    Node* next; // reference to next node 
    int elements[MAX_SIZE]; // this array will contain noOfElements, however space is reserved for MAX_SIZE
};

Example of Unrolled Linked List

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?

  • We are already aware of the advantages that Linked List gives us over arrays but Unrolled Linked List combine the advantage of the array (small memory overhead) along with the advantage of linked lists like fast insertion and deletion.

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

Advantages

  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.

Disadvantage

  1. A fairly high overhead per node when compared to the singly linked list, since for every node it can store an array of elements.

Efficient Searching

Let us understand how it is providing efficient capability with the help of an example. Take an Example:

  • We have total 10 elements spread over 3 nodes and thus distribution can be 3 3 4 elements respectively in each node. Now, if we are required to find 8th element, we will traverse only the last block of the node. Thus searching can also be efficient in such a way.

This blog tried to introduce the audience to yet another type of linked list, which is called Unrolled Linked List. This is an essential concept from an interview point of view. If you want to solve more questions on Linked List, which our expert mentors curate at PrepBytes, you can follow this link [Linked List]().

Previous post Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
Next post Run Length Decoding in Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *