# An implementation of an unrolled 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

def __init__(self, capacity):
self.capacity = capacity #maximum capacity of an array in node
self.tail = None

#this method inserts the given value in the list
def insert(self, value):

elif self.tail.length + 1 <= self.capacity: #current node's capacity is not full
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):
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
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
```

Back to: Data Structure > Data Structure - Linked List