Introducing the Unrolled Linked List data structure – Arrays, collections and data structures

122. Introducing the Unrolled Linked List data structure

An Unrolled Linked List is a flavor of a linked list that stores arrays (multiple items). Each node of an Unrolled Linked List can store an array. Is like combining the powers of an array with the powers of a linked list. In other words, an Unrolled Linked List is a data structure with a low memory footprint and high performance of insertion and deletion.Insertion and deletion from an Unrolled Linked List have different implementations.For instance, you can insert arrays (insert(int[] arr)), which means that for each insertion we create a new node and insert that array into it.Deleting an item is equivalent to removing the item from the specified index in the proper array. If after deletion the array is empty then it is removed from the list as well.Another approach assumes that the Unrolled Linked List has a fixed capacity (each node holds an array of this capacity). Further, we insert items one by one by following a low-water mark of 50%. This means that if we insert an item that cannot be added to the current node (array) then we create a new node and insert into it half of the original node’s items plus this item.Deleting an item has reverse logic. If the number of items in a node drops below 50% then we move the items from the neighboring array over to get back a low-water mark above 50%. If the neighboring array also drops below 50% then we have to merge these two nodes.You can find both approaches in the bundled code. On the other hand, you can challenge yourself to provide an Unrolled Linked List implementation that extends the JVM collections API. You can start from any of the following two approaches:

public class UnrolledLinkedList<E>
       extends AbstractList<E>
       implements List<E>, Serializable { … }
public class UnrolledLinkedList<E>
       extends AbstractSequentialList<E>
       implements Deque<E>, Cloneable, Serializable { … }

Add this implementation to your GitHub portfolio and you’ll impress your interviewer.