An Unrolled Linked List is a special type of Linked List in which each node stores an array of elements, unlike a simple linked list. Here we use an ArrayList and a constructor that initializes the size of the Unrolled Linked List. Elements are added to the first Node until it is filled and then a new Node is created with the same size.
The Node class has two methods namely
- A constructor
- An insert method which takes an integer as a parameter.
Implementation:
- Adding elements to the unrolled linked list
- Deleting elements from an unrolled linked list
Example 1: Adding elements to Unrolled Linked List
Java
// Java Program to implement Unrolled Linked List// Importing all input output classesimport java.io.*;// Importing all utility classes from// java.util packageimport java.util.*;// Class 1// Main classclass GFG { // Nested static class static class Node { // Member variables of static nested class int size; ArrayList<Integer> array; // Initializing next as NULL Node next = null; // Method 1 // Of nested static class // To compute over size Node(int size) { // This keyword refers to current object itself this.size = size; // Storing ArrayList in an array array = new ArrayList<>(); } // Method 2 // To insert element in an array void insert(int n) { // If array is having empty spaces if (array.size() < size) { // Add element from List to array array.add(n); } // If array is already full else { // Array size is zero if (next == null) { // Create a new Node and start inserting // elements next = new Node(size); next.insert(n); } // If array is defined else { // Directly start inserting elements next.insert(n); } } } } // Main driver method public static void main(String args[]) { // Creating an object of nested static class // inside the main() method // Maximum N elements will be printed in a row // N is passed as an parameter to the Node // N = 3 for illustration, do change and // observe how the output varies Node x = new Node(3); // Adding custom input elements // using the insert() method x.insert(10); x.insert(20); x.insert(30); x.insert(40); x.insert(50); x.insert(60); x.insert(70); // System.out.println(x.array); // System.out.println(x.next.array); // System.out.println(x.next.next.array); // If condition holds true // If there are elements left to be inserted while (x != null) { // Print and display the elements System.out.println(x.array); // Moving to next element x = x.next; } }} |
Output
[10, 20, 30] [40, 50, 60] [70]
Example 2: Deleting elements from an unrolled linked list
Java
// Java Program to implement Unrolled Linked List// Importing all input output classesimport java.io.*;// Importing all utility classes from// java.util packageimport java.util.*;// Class 1// Main classclass GFG { // Nested static class static class Node { // Member variables of nested class int size; ArrayList<Integer> array; // Initially next is pointing to head Node next = null; // Constructor of static nested class Node(int size) { // This keyword refers to current object itself this.size = size; // Assigning current List element // to an array array = new ArrayList<>(); } // Method 1 // Of static nested class void insert(int n) { // If there is space in an array if (array.size() < size) { // Add elements to an array array.add(n); } // Condition check over array else { // If no array exists, it means // head is still pointing to NULL if (next == null) { // Create a new node next = new Node(size); // Now, start inserting elements next.insert(n); } // If next is NOT-NULL else { // Start filling array directly next.insert(n); } } } // Method 2 // Of static nested class boolean delete(int n) { if (array.contains(n)) { array.remove(array.indexOf(n)); return true; } else { if (next == null) { return false; } else { next.delete(n); } return true; } } } // Mai driver method public static void main(String args[]) { // Creating an object of Nodetype where // 3 as an argument represents maximum elements // to be displayed in a row Node x = new Node(3); // Adding elements to the above object // Custom input entries x.insert(10); x.insert(20); x.insert(30); x.insert(40); x.insert(50); x.insert(60); x.insert(70); // System.out.println(x.array); // System.out.println(x.next.array); // System.out.println(x.next.next.array); // Display message System.out.println( "After Inserting all elements : "); // Creating an object of static nested class Node temp = x; while (temp != null) { System.out.println(temp.array); temp = temp.next; } // Display message System.out.println("Deleting 50 :"); // Deleting a random element from above added // Say it be 50 x.delete(50); // Using the temp variable so that // value is not lost temp = x; // Condition check // If temp viable is NOT-NULL while (temp != null) { // Print and display the temp array // be it one element or many System.out.println(temp.array); // Moving to the next node using // standard way 'next' in linkedList temp = temp.next; } }} |
Output
After Inserting all elements : [10, 20, 30] [40, 50, 60] [70] Deleting 50 : [10, 20, 30] [40, 60] [70]
