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