Insertion in Unrolled Linked List
An unrolled linked list is a linked list of small arrays, all of the same size where each is so small that the insertion or deletion is fast and quick, but large enough to fill the cache line. An iterator pointing into the list consists of both a pointer to a node and an index into that node containing an array. It is also a data structure and is another variant of Linked List. It is related to B-Tree. It can store an array of elements at a node unlike a normal linked list which stores single element at a node. It is combination of arrays and linked list fusion-ed into one. It increases cache performance and decreases the memory overhead associated with storing reference for metadata. Other major advantages and disadvantages are already mentioned in the previous article.
Prerequisite : Introduction to Unrolled Linked List
Below is the insertion and display operation of Unrolled Linked List.
Input : 72 76 80 94 90 70
capacity = 3
Output : Unrolled Linked List :
72 76
80 94
90 70
Explanation : The working is well shown in the
algorithm below. The nodes get broken at the
mentioned capacity i.e., 3 here, when 3rd element
is entered, the flow moves to another newly created
node. Every node contains an array of size
(int)[(capacity / 2) + 1]. Here it is 2.
Input : 49 47 62 51 77 17 71 71 35 76 36 54
capacity = 5
Output :
Unrolled Linked List :
49 47 62
51 77 17
71 71 35
76 36 54
Explanation : The working is well shown in the
algorithm below. The nodes get broken at the
mentioned capacity i.e., 5 here, when 5th element
is entered, the flow moves to another newly
created node. Every node contains an array of
size (int)[(capacity / 2) + 1]. Here it is 3.
Algorithm :
Insert (ElementToBeInserted)
if start_pos == NULL
Insert the first element into the first node
start_pos.numElement ++
end_pos = start_pos
If end_pos.numElements + 1 < node_size
end_pos.numElements.push(newElement)
end_pos.numElements ++
else
create a new Node new_node
move final half of end_pos.data into new_node.data
new_node.data.push(newElement)
end_pos.numElements = end_pos.data.size / 2 + 1
end_pos.next = new_node
end_pos = new_node
Implementation: Following is the Java implementation of the insertion and display operation. In the below code, the capacity is 5 and random numbers are input.
C++
// C++ program to show the insertion operation of Unrolled Linked List #include <iostream>#include <cstdlib>#include <ctime>using namespace std;// class for each nodeclass UnrollNode {public: UnrollNode* next; int num_elements; int* array; // Constructor UnrollNode(int n) { next = nullptr; num_elements = 0; array = new int[n]; }};// Operation of Unrolled Functionclass UnrollLinkList {private: UnrollNode* start_pos; UnrollNode* end_pos; int size_node; int nNode;public: // Parameterized Constructor UnrollLinkList(int capacity) { start_pos = nullptr; end_pos = nullptr; nNode = 0; size_node = capacity + 1; } // Insertion operation void Insert(int num) { nNode++; // Check if the list starts from NULL if (start_pos == nullptr) { start_pos = new UnrollNode(size_node); start_pos->array[0] = num; start_pos->num_elements++; end_pos = start_pos; return; } // Attaching the elements into nodes if (end_pos->num_elements + 1 < size_node) { end_pos->array[end_pos->num_elements] = num; end_pos->num_elements++; } // Creation of new Node else { UnrollNode* node_pointer = new UnrollNode(size_node); int j = 0; for (int i = end_pos->num_elements / 2 + 1; i < end_pos->num_elements; i++) node_pointer->array[j++] = end_pos->array[i]; node_pointer->array[j++] = num; node_pointer->num_elements = j; end_pos->num_elements = end_pos->num_elements / 2 + 1; end_pos->next = node_pointer; end_pos = node_pointer; } } // Display the Linked List void display() { cout << "\nUnrolled Linked List = " << endl; UnrollNode* pointer = start_pos; while (pointer != nullptr) { for (int i = 0; i < pointer->num_elements; i++) cout << pointer->array[i] << " "; cout << endl; pointer = pointer->next; } cout << endl; }};// Main Class int main(){ srand(time(0)); UnrollLinkList ull(5); // Perform Insertion Operation for (int i = 0; i < 12; i++) { // Generate random integers in range 0 to 99 int rand_int1 = rand() % 100; cout << "Entered Element is " << rand_int1 << endl; ull.Insert(rand_int1); ull.display(); } return 0;}// This code is contributed by Vikram_Shirsat |
Python3
# Python program to show the insertion operation of Unrolled Linked List import random# class for each nodeclass UnrollNode: def __init__(self, n): self.next = None self.num_elements = 0 self.array = [0] * n# Operation of Unrolled Functionclass UnrollLinkList: def __init__(self, capacity): self.start_pos = None self.end_pos = None self.nNode = 0 self.size_node = capacity + 1 # Insertion operation def Insert(self, num): self.nNode += 1 # Check if the list starts from NULL if self.start_pos is None: self.start_pos = UnrollNode(self.size_node) self.start_pos.array[0] = num self.start_pos.num_elements += 1 self.end_pos = self.start_pos return # Attaching the elements into nodes if self.end_pos.num_elements + 1 < self.size_node: self.end_pos.array[self.end_pos.num_elements] = num self.end_pos.num_elements += 1 # Creation of new Node else: node_pointer = UnrollNode(self.size_node) j = 0 for i in range(self.end_pos.num_elements // 2 + 1, self.end_pos.num_elements): node_pointer.array[j] = self.end_pos.array[i] j += 1 node_pointer.array[j] = num node_pointer.num_elements = j + 1 self.end_pos.num_elements = self.end_pos.num_elements // 2 + 1 self.end_pos.next = node_pointer self.end_pos = node_pointer # Display the Linked List def display(self): print("\nUnrolled Linked List = ") pointer = self.start_pos while pointer is not None: for i in range(pointer.num_elements): print(pointer.array[i], end=" ") print() pointer = pointer.next print()# Main functionif __name__ == "__main__": ull = UnrollLinkList(5) # Perform Insertion Operation for i in range(12): # Generate random integers in range 0 to 99 rand_int1 = random.randint(0, 99) print("Entered Element is ", rand_int1) ull.Insert(rand_int1) ull.display()# This code is contributed by Vikram_Shirsat |
C#
/* C# program to show the insertion operation* of Unrolled Linked List */using System;// class for each nodepublic class UnrollNode { public UnrollNode next; public int num_elements; public int[] array; // Constructor public UnrollNode(int n) { next = null; num_elements = 0; array = new int[n]; }}// Operation of Unrolled Functionpublic class UnrollLinkList { private UnrollNode start_pos; private UnrollNode end_pos; int size_node; int nNode; // Parameterized Constructor public UnrollLinkList(int capacity) { start_pos = null; end_pos = null; nNode = 0; size_node = capacity + 1; } // Insertion operation public void Insert(int num) { nNode++; // Check if the list starts from NULL if (start_pos == null) { start_pos = new UnrollNode(size_node); start_pos.array[0] = num; start_pos.num_elements++; end_pos = start_pos; return; } // Attaching the elements into nodes if (end_pos.num_elements + 1 < size_node) { end_pos.array[end_pos.num_elements] = num; end_pos.num_elements++; } // Creation of new Node else { UnrollNode node_pointer = new UnrollNode(size_node); int j = 0; for (int i = end_pos.num_elements / 2 + 1; i < end_pos.num_elements; i++) node_pointer.array[j++] = end_pos.array[i]; node_pointer.array[j++] = num; node_pointer.num_elements = j; end_pos.num_elements = end_pos.num_elements / 2 + 1; end_pos.next = node_pointer; end_pos = node_pointer; } } // Display the Linked List public void display() { Console.Write("\nUnrolled Linked List = "); Console.WriteLine(); UnrollNode pointer = start_pos; while (pointer != null) { for (int i = 0; i < pointer.num_elements; i++) Console.Write(pointer.array[i] + " "); Console.WriteLine(); pointer = pointer.next; } Console.WriteLine(); }}/* Main Class */public class UnrolledLinkedList_Check { // Driver code public static void Main(String[] args) { // create instance of Random class Random rand = new Random(); UnrollLinkList ull = new UnrollLinkList(5); // Perform Insertion Operation for (int i = 0; i < 12; i++) { // Generate random integers in range 0 to 99 int rand_int1 = rand.Next(100); Console.WriteLine("Entered Element is " + rand_int1); ull.Insert(rand_int1); ull.display(); } }}// This code has been contributed by 29AjayKumar |
Java
/* Java program to show the insertion operation* of Unrolled Linked List */import java.util.Scanner;import java.util.Random;// class for each nodeclass UnrollNode { UnrollNode next; int num_elements; int array[]; // Constructor public UnrollNode(int n) { next = null; num_elements = 0; array = new int[n]; }}// Operation of Unrolled Functionclass UnrollLinkList { private UnrollNode start_pos; private UnrollNode end_pos; int size_node; int nNode; // Parameterized Constructor UnrollLinkList(int capacity) { start_pos = null; end_pos = null; nNode = 0; size_node = capacity + 1; } // Insertion operation void Insert(int num) { nNode++; // Check if the list starts from NULL if (start_pos == null) { start_pos = new UnrollNode(size_node); start_pos.array[0] = num; start_pos.num_elements++; end_pos = start_pos; return; } // Attaching the elements into nodes if (end_pos.num_elements + 1 < size_node) { end_pos.array[end_pos.num_elements] = num; end_pos.num_elements++; } // Creation of new Node else { UnrollNode node_pointer = new UnrollNode(size_node); int j = 0; for (int i = end_pos.num_elements / 2 + 1; i < end_pos.num_elements; i++) node_pointer.array[j++] = end_pos.array[i]; node_pointer.array[j++] = num; node_pointer.num_elements = j; end_pos.num_elements = end_pos.num_elements / 2 + 1; end_pos.next = node_pointer; end_pos = node_pointer; } } // Display the Linked List void display() { System.out.print("\nUnrolled Linked List = "); System.out.println(); UnrollNode pointer = start_pos; while (pointer != null) { for (int i = 0; i < pointer.num_elements; i++) System.out.print(pointer.array[i] + " "); System.out.println(); pointer = pointer.next; } System.out.println(); }}/* Main Class */class UnrolledLinkedList_Check { // Driver code public static void main(String args[]) { Scanner sc = new Scanner(System.in); // create instance of Random class Random rand = new Random(); UnrollLinkList ull = new UnrollLinkList(5); // Perform Insertion Operation for (int i = 0; i < 12; i++) { // Generate random integers in range 0 to 99 int rand_int1 = rand.nextInt(100); System.out.println("Entered Element is " + rand_int1); ull.Insert(rand_int1); ull.display(); } }} |
Javascript
<script>/* Javascript program to show the insertion operation* of Unrolled Linked List */// class for each nodeclass UnrollNode { // Constructor constructor(n) { this.next = null; this.num_elements = 0; this.array = new Array(n); for(let i = 0; i < n; i++) { this.array[i] = 0; } }}// Operation of Unrolled Functionclass UnrollLinkList{ // Parameterized Constructor constructor(capacity) { this.start_pos = null; this.end_pos = null; this.nNode = 0; this.size_node = capacity + 1; } // Insertion operation Insert(num) { this.nNode++; // Check if the list starts from NULL if (this.start_pos == null) { this.start_pos = new UnrollNode(this.size_node); this.start_pos.array[0] = num; this.start_pos.num_elements++; this.end_pos = this.start_pos; return; } // Attaching the elements into nodes if (this.end_pos.num_elements + 1 < this.size_node) { this.end_pos.array[this.end_pos.num_elements] = num; this.end_pos.num_elements++; } // Creation of new Node else { let node_pointer = new UnrollNode(this.size_node); let j = 0; for (let i = Math.floor(this.end_pos.num_elements / 2 )+ 1; i < this.end_pos.num_elements; i++) node_pointer.array[j++] = this.end_pos.array[i]; node_pointer.array[j++] = num; node_pointer.num_elements = j; this.end_pos.num_elements = Math.floor(this.end_pos.num_elements / 2) + 1; this.end_pos.next = node_pointer; this.end_pos = node_pointer; } } // Display the Linked List display() { document.write("<br>Unrolled Linked List = "); document.write("<br>"); let pointer = this.start_pos; while (pointer != null) { for (let i = 0; i < pointer.num_elements; i++) document.write(pointer.array[i] + " "); document.write("<br>"); pointer = pointer.next; } document.write("<br>"); }}// Driver codelet ull = new UnrollLinkList(5); // Perform Insertion Operationfor (let i = 0; i < 12; i++){ // Generate random integers in range 0 to 99 let rand_int1 = Math.floor(Math.random()*(100)); document.write("Entered Element is " + rand_int1+"<br>"); ull.Insert(rand_int1); ull.display();}// This code is contributed by rag2127</script> |
Output
Entered Element is 67 Unrolled Linked List = 67 Entered Element is 69 Unrolled Linked List = 67 69 Entered Element is 50 Unrolled Linked List = 67 69 50 Entered Element is 60 Unrolled Linked List = 67 69 50 60 Entered Element is 18 Unrolled Linked List = 67 69 50 60 18 Entered Element is 15 Unrolled Linked List = 67 69 50 60 18 15 Entered Element is 41 Unrolled Linked List = 67 69 50 60 18 15 41 Entered Element is 79 Unrolled Linked List = 67 69 50 60 18 15 41 79 Entered Element is 12 Unrolled Linked List = 67 69 50 60 18 15 41 79 12 Entered Element is 95 Unrolled Linked List = 67 69 50 60 18 15 41 79 12 95 Entered Element is 37 Unrolled Linked List = 67 69 50 60 18 15 41 79 12 95 37 Entered Element is 13 Unrolled Linked List = 67 69 50 60 18 15 41 79 12 95 37 13
Time complexity : O(n)
Also, few real-world applications :
- It is used in B-Tree and T-Tree
- Used in Hashed Array Tree
- Used in Skip List
- Used in CDR Coding
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
