Unrolled Linked List

There are two well-known types of linked lists; the singly linked list and the doubly linked list. In a singly linked list, we’ve got a linear structure with every node having one next pointer to maneuver forward, whereas in a doubly-linked list we have the same structure but each node also incorporates a previous pointer to maneuver backward. Below is the structure of both types of linked lists:

1
2
3
4
5
6
7
8
9
10
struct SinglyListNode {
  int val;
  SinglyListNode * next;
};

struct DoublyListNode {
  int data;
  DoublyListNode * next;
  DoublyListNode * prev;
};

In this article, we will define one more type of linked list which solves the O(n) linear complexity of insertion and search into a linked list to about O(√n).

What is an Unrolled Linked List?

An unrolled linked list is a variation of a linked list where one block contains a circular linked list of its own. If there are n elements in an unrolled linked list then all blocks except the last one should contain ⌈√n⌉ nodes.

Structure of an unrolled linked list:

1
2
3
4
5
struct UnrolledLinkedBlock {
  LinkedBlock * next;
  SinglyListNode * head;
  int count;
};

Below you can see an unrolled linked list representation with twelve nodes and each block containing four nodes:

Inserting into Unrolled Linked List

One important aspect when inserting into an unrolled linked list is maintaining its ⌈√n⌉ nodes per block property as it helps to search and perform other operations optimally.

Algorithm:

1. Insert a node at X after the ith node in the kth block.

2. Now to maintain the ⌈√n⌉ property, shift the nodes in the block, current, and next blocks towards the tail.

3. Make sure every block has exactly ⌈√n⌉ nodes.

4. If one node exceeds the ⌈√n⌉ space add one more block.

The node below with value twenty-five is inserted in the first block and now we shift node thirty-seven to the next block. Doing this maintains the ⌈√n⌉ property.

Searching in Unrolled Linked List

Here we will use the ⌈√n⌉ property to skip some blocks and search optimally.

Algorithm:

1. To search a kth element traverse the blocks to one containing kth block, that would be the ⌈k/√n⌉th block.

2. It will take a maximum of √n blocks.

3. Now in this block access the k%⌈√n⌉ th node in the circular linked list.

4. The above also takes a maximum of ⌈√n⌉ nodes.

Now let’s search the seventh node in our list below:
We first move to the ⌈7/4⌉th block, i.e first block, and access the ⌈7%4⌉th block, i.e third node, and you will find it.

Code implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>

using namespace std;

int size;

struct ListNode {
  ListNode * next;
  int value;
  ListNode(int val) {
    this - > next = NULL;
    this - > value = val;
  }
};

struct LinkedBlock {
  LinkedBlock * next;
  ListNode * head;
  int nodeCount;
  LinkedBlock() {
    this - > next = NULL;
    this - > head = NULL;
    this - > nodeCount = 0;
  }
};

LinkedBlock * blockHead;

void searchElement(int k, LinkedBlock ** block, ListNode ** node) {
  int j = (k + size - 1) / size;
  LinkedBlock * p = blockHead;

  while (--j)
    p = p - > next;
  * block = p;

  ListNode * q = p - > head;
  k = k % size;

  if (!k) k = size;
  k = p - > nodeCount + 1 - k;

  while (k--)
    q = q - > next;
  * node = q;
}

void shift(LinkedBlock * A) {
  LinkedBlock * B;
  ListNode * temp;

  while (A - > nodeCount > size) {
    if (A - > next == NULL) {
      A - > next = new LinkedBlock();
      B = A - > next;
      temp = A - > head - > next;
      A - > head - > next = A - > head - > next - > next;
      B - > head = temp;
      temp - > next = temp;
      A - > nodeCount--;
      B - > nodeCount++;
    } else {
      B = A - > next;
      temp = A - > head - > next;
      A - > head - > next = A - > head - > next - > next;
      temp - > next = B - > head - > next;
      B - > head - > next = temp;
      B - > head = temp;
      A - > nodeCount--;
      B - > nodeCount++;
    }
    A = B;
  }
}

void addElement(int k, int x) {
  ListNode * p, * q;
  LinkedBlock * r;

  if (!blockHead) {
    blockHead = new LinkedBlock();
    blockHead - > head = new ListNode(x);
    blockHead - > head - > next = blockHead - > head;
    blockHead - > nodeCount++;
  } else {
    if (k == 0) {
      p = blockHead - > head;
      q = p - > next;
      p - > next = new ListNode(x);
      p - > next - > next = q;
      blockHead - > head = p - > next;
      blockHead - > nodeCount++;
      shift(blockHead);
    } else {
      searchElement(k, & r, & p);
      q = p;
      while (q - > next != p) q = q - > next;
      q - > next = new ListNode(x);
      q - > next - > next = p;
      r - > nodeCount++;
      shift(r);
    }
  }
}

int searchElement(int k) {
  ListNode * p;
  LinkedBlock * q;
  searchElement(k, & q, & p);
  return p - > value;
}

void display() {
  ListNode * p;
  LinkedBlock * q = blockHead;
  int list = 0;
  while (q != NULL) {
    p = q - > head;
    cout << "Block " << list << ": ";
    list++;
    cout << p - > value << "<--";
    p = p - > next;
    while (p != q - > head) {
      if (p - > next != q - > head)
        cout << p - > value << "<--";
      else
        cout << p - > value;
      p = p - > next;
    }
    q = q - > next;
    cout << endl;
  }
}

int main() {
  int m, i, k, x;
  string type;
  cin >> m;
  size = (int)(sqrt(m - 0.001)) + 1;

  for (int i = 0; i < m; i++) {
    cin >> type;
    if (type == "add") {
      cin >> k >> x;
      addElement(k, x);
    } else {
      cin >> k;
      cout << searchElement(k) << endl;
    }
  }

  display();
}

Input:

12
add 0 2
add 0 7
add 0 8
add 0 9
add 2 17
add 0 5
add 0 3
add 0 6
search 5
search 1
search 6
search 7

Output:

8
6
17
7
Block 0: 6<–9<–5<–3
Block 1: 8<–2<–7<–17

We can improve our structure above by replacing the linked list with an array of size ⌈√n⌉, this makes the implementation easier.

#define size 4
struct UnrolledLinkedBlock{
LinkedBlock *next;
int nodes[size];
int count;
};

Complexity:

Insertion: O(⌈√n⌉), we have only ⌈√n⌉ blocks and ⌈√n⌉ nodes per block so a maximum of ⌈√n⌉ is traversed before adding.

Shifting: O(⌈√n⌉), shift operation included when we add or remove a node from the tail of the circular linked list which takes only O(1) and a maximum of O(⌈√n⌉) shift operation, as only one shift is required per block.

Searching: O(⌈√n⌉), we have only ⌈√n⌉ blocks and ⌈√n⌉ nodes per block so a maximum of ⌈√n⌉ are required before we find our element.

Advantages:

1. Operations like insertion, deletion, and searching are faster than a linked list.

2. Compared to the original linked list it requires less space for a pointer.

3. Provides faster performance when we consider cache management.

Disadvantages:

1. Unlike the original linked list, overhead per node is quite high in an unrolled linked list.