Table of Contents

In this article, we are going to implement an unrolled linked list. It is a linear data structure and a variant of the linked list. It stores multiple elements at a node, unlike a regular linked list that contains only a single value. In other words, it is a linked list that stores an array of elements. An unrolled linked list is a combination of an array and a linked list, and thus, it has the advantages of both data structures. It has a small memory overhead (a benefit of an array) and efficient insertion and deletion operations (benefits of a linked list).

**Unrolled Linked Lists** are observed to give better performance than singly-linked lists because of the cache behavior. However, the overhead per node is more as compared to the ordinary linked list.

## Implementation of unrolled Linked List

Each node in the unrolled linked list contains three types of information: an array containing values, array length, and the pointer to the next node.

Each array in a node can hold a certain number of elements. Let us call it the capacity. However, typically, it is not filled to its maximum capacity. Generally, the length of each array in a node is equal to the minimum threshold, i.e.,

`Minimum threshold = capacity/2 (integer division)`

Moreover, the unrolled linked list has two pointers: head and tail. Head points to the first node, and tail refers to the last node.

### Insertion

If the list is empty, i.e., **head = null**, then the value to be inserted is the first value. We create a node and add the given value to that node’s array. The array length gets increased by 1â€”both the head and the tail point to this node.

If the list is not empty, we check if the current node’s array can fit a new node. If it can, we append the given value to the current node’s array and increase its length by `1`

. Otherwise, we create a new node. We move half of the elements from the current node to the new node such that the length of the current node is equal to the minimum threshold. We add the given value to the new node and set its length. We also need to update the current node’s length. Moreover, we set the current node’s next pointer to refer to the new node and also update the tail to point to the new node.

### Deletion

The operation of the deletion is the opposite of insertion. First, we find the first appearance of the given value and remove it from the array. After the removal, if the current node’s length is less than 50% of the maximum capacity, we move elements from the next node to the current node till that condition is not satisfied. We also check if the next node’s length is less than 50% of the maximum capacity. If it is, then we merge the current node and the next node. If the value does not exist in the list, then we throw an error.

### Traversal

Here, we traverse through the unrolled linked list. We start at the head and move node by node. At each node, we iterate over the array and print its items.

The code of the unrolled linked list is given below.

class Node: def __init__(self): self.length = 0 self.array = [] self.next = None class UnrolledLinkedList: def __init__(self, capacity): self.capacity = capacity #maximum capacity of an array in node self.head = None self.tail = None #this method inserts the given value in the list def insert(self, value): if self.head == None: #unrolled linked is empty self.head = Node() self.head.array.append(value) #add the value self.head.length += 1 self.tail = self.head elif self.tail.length + 1 <= self.capacity: #current node's capacity is not full self.tail.array.append(value) #add the given value self.tail.length += 1 else: #current node's capacity is full new_node = Node() #create a new node #move final half of elements from the current node to the new node half_length = self.tail.length//2 new_node.array.extend(self.tail.array[half_length:]) new_node.array.append(value) #add the given value to the new node new_node.length = len(new_node.array) #set the length of the new node's array self.tail.length = half_length #update the length of the current node's array self.tail.next = new_node #make current node next pointer refer to the new node self.tail = new_node #update the tail #prints all the elements of the unrolled linked list def traversal(self): temp = self.head while temp: for i in range(0, temp.length): print(temp.array[i], end="\t") print() temp = temp.next #This method removes the first appearance of the given value def delete(self, value): #find the given value and delete it temp = self.head while temp: for i in range(0, temp.length): if temp.array[i] == value: temp.array.pop(i) #remove the given value from the array temp.array.append(None) temp.length -= 1 #decrease the length #if the current node's length is less than 50% then move elements from next node's array to the current one while temp.length < (self.capacity//2) and temp.next: temp.array[temp.length] = temp.next.array.pop(0) temp.length +=1 temp.next.length -= 1 #if the next node's length is less than 50% then merge the two halves if temp.next and temp.next.length < (self.capacity//2) : temp.array[temp.length:temp.length+temp.next.length] = temp.next.array[:temp.next.length] temp.length += temp.next.length deleted_node = temp.next temp.next = temp.next.next del deleted_node return temp = temp.next raise ValueError(f'Value {value} does not exist in the list') ull = UnrolledLinkedList(4) #maximum capacity is 4 #insert values ull.insert(1) ull.insert(2) ull.insert(3) ull.insert(4) ull.insert(5) ull.insert(6) ull.insert(7) ull.insert(8) print("Display all items") ull.traversal() ull.delete(3) print("Display all items after deleting value 3") ull.traversal() ull.delete(5) print("Display all items after deleting value 5") ull.traversal() ull.delete(6) print("Display all items after deleting value 6") ull.traversal()

**Output**

Display all items 1 2 3 4 5 6 7 8 Display all items after deleting value 3 1 2 4 5 6 7 8 Display all items after deleting value 5 1 2 4 6 7 8 Display all items after deleting value 6 1 2 4 7 8

Blog Hero